Splunk Search

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

rikinet
Explorer

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.

Labels (1)
0 Karma

ITWhisperer
SplunkTrust
SplunkTrust

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.

0 Karma
Get Updates on the Splunk Community!

Streamline Data Ingestion With Deployment Server Essentials

REGISTER NOW!Every day the list of sources Admins are responsible for gets bigger and bigger, often making the ...

Remediate Threats Faster and Simplify Investigations With Splunk Enterprise Security ...

REGISTER NOW!Join us for a Tech Talk around our latest release of Splunk Enterprise Security 7.2! We’ll walk ...

Introduction to Splunk AI

WATCH NOWHow are you using AI in Splunk? Whether you see AI as a threat or opportunity, AI is here to stay. ...