Find path between nodes in a table representing a hierarchical tree?

[rikinet]

I have a table with columns "from" and "to", in which each row represents an edge between "from" and "to" nodes within a hierarchical tree. In this tree, any node can have any number of children, and arbitrary depth. The table rows are in no specific order. In my case, the tree contains ~50 nodes at max.

We define P(X) as the path between the root node and node X, where X doesn't have to be a leaf node.

Question: Using SPL language, how can I determine P(X) from the tabular data?

The result would preferably be represented in the same tabular format, but containing only the edges on P(X). Any other representation is also fine, such as a string, mv field, table containing the nodes on the path, etc.


Example:

This tree with 12 edges...

A
+--B
|  +--E
|  +--F
|  |  +--K
|  |  +--L
|  +--G
+--C
|  +--H
+--D
   +--I
   +--J
      +--M

... would be represented by the table:

from	to
A	B
A	C
A	D
B	E
B	F
B	G
F	K
F	L
C	H
D	I
D	J
J	M

(Note that the rows can be in any order)

If we are looking for P(F), the resulting path would be "A-B-F", i.e. the following subset of above table:

from	to
B	F
A	B

(Again, the order of the rows doesn't matter.)

I would normally consider recursive tree searches (DFS, BFS) or at least loops, but these are not SPL-like approaches.

[ITWhisperer]

You are right, SPL does not do recursion or loops particularly well. However, if you know the maximum depth, you could use repetition

| makeresults
| fields - _time
| eval _raw="from	to
A	B
A	C
A	D
B	E
B	F
B	G
F	K
F	L
C	H
D	I
D	J
J	M"
| multikv forceheader=1 
| table from to
| eval path=from."-".to
| eventstats values(path) as paths
| foreach mode=multivalue paths
    [| eval path=if(mvindex(split(<<ITEM>>,"-"),-1)==from,<<ITEM>>."-".to,path)]
| eventstats values(path) as paths
| foreach mode=multivalue paths
    [| eval path=if(mvindex(split(<<ITEM>>,"-"),-1)==from,<<ITEM>>."-".to,path)]
| eventstats values(path) as paths
| foreach mode=multivalue paths
    [| eval path=if(mvindex(split(<<ITEM>>,"-"),-1)==from,<<ITEM>>."-".to,path)]

The last two lines are repeated sufficient times to resolve all paths.