baxy77bax has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

I have a question which is not Perl exclusive but I think people using programing languages for text processing might have encountered it, and since a large fraction of Perl comunity uses Perl do exactly that I thought someone might know the answer.
So, I have a text file containg integers (The file does not necessary need to sontain integers). Integers are placed into two columns such that integer from the first column is a parent integer to the integer in the second column. Example: 

1  2
1  5
1  7
2  6
2  8
3  1
3  2
...

[download]
So basically a tree structure encoded as a two column table. My question is: Is there a proper term for files in which the information is ordered in such a manner? Is there a proper termn for such order?

Thank you

Replies are listed 'Best First'.
Re: Data type name required [not Perl exclusive question]
by BrowserUk (Patriarch) on Mar 11, 2015 at 13:59 UTC

    It's an "Adjacency List".

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
    In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]
Re: Data type name required [not Perl exclusive question]
by karlgoethebier (Abbot) on Mar 11, 2015 at 15:39 UTC
[reply]
Re: Data type name required [not Perl exclusive question]
by Anonymous Monk on Mar 11, 2015 at 15:06 UTC

    Hm. Tree traversal might also be relevant. (Though it is hard to tell: your question is somewhat vague, Dr. Rorschach.)

[reply]
Re: Data type name required [not Perl exclusive question]
by Anonymous Monk on Mar 11, 2015 at 14:42 UTC

    Graph edges, links? Sorting the set of edges does not change the elephant.

[reply]
Re: Data type name required [not Perl exclusive question]
by ww (Archbishop) on Mar 11, 2015 at 18:15 UTC

    Would you please explain for the terminology and arithmeticly challenged (to say nothing of a bit slow on the uptake in general; i.e., /me) how the the 3s (in rows 6 and 7) are the "parent interger(s)" of 1 and 2?


    ++$anecdote ne $data


[reply]
[d/l]
      AFAICS, this has not much to do with arithmetics. Adjacency lists just describe nodes of a graph or a tree. The numbers at the left are just nodes which are predecessors of nodes represented by the right-hand side integers in an oriented graph.

      Update: If you want to represent the graph of this list: 

      1  2
1  5
1  7
2  6
2  8
3  1
3  2

      [download]
      Making some quite plausible assumptions on what exactly this list is supposed to represent, you might first draw a circle and name it 1 (write 1 in the middle of the circle) to represent the first node. This first node has three successors, 2, 5 and 7. So you just draw 3 other circles, with a 2, 5 and 7 in the middle, and draw an arrow from node 1 to nodes 2, 5 and 7. Then, from node 2 you draw two outbound arrows to the two new nodes, 6 and 8. Then you create node 3, and draw two arrows from it to existing nodes 1 and 2.

      This is just one of the classical ways to represent graphs in a computer, there are some others.

      In Perl, this graph could be implemented as an array of two-element arrays (([1, 2], [1, 5], [1, 7], ... [3, 2]), but, depending on what this graph is going to be used for, that might not be a very practical implementation to use. It could also be implemented as a hash of arrays: (1 => [2, 5, 7], 2 => [6, 8], 3 => [1, 2]), which might be more practical to use for some types of processing. For other types of calculations, you might want to reverse the representation and use the successor nodes as keys and predecessors (or lists of predecessors) as values or lists of values. It really depends on the data structure and the processing that needs to be done on it.

      Je suis Charlie.
[reply]
[d/l]
[select]
[reply]
[d/l]

Back to Seekers of Perl Wisdom