# The path from root node to all leaves in a tree (or directed acyclic graph)

2020-12-07 14:21:06

problem ： Suppose there's a tree now , Note that the trees here are not necessarily binary trees （ In other words, it can be a multi branch tree ）, We want to enumerate the paths from the root node to each leaf node , How to implement this algorithm ？

The following example mainly uses Python To achieve . To make it easier to build a tree （ And then there's the digraph ）, I'm going to use it directly here Python in NetworkX package （NetworkX It's a use. Python Graph theory and complex network modeling tools for language development ）. First introduce the necessary packages .

``````import copy
import networkx as nx
from collections import deque

import matplotlib.pyplot as plt
%matplotlib inline``````

Building a multi fork tree T：

``````T = nx.DiGraph()

nx.draw(T, with_labels=True)
plt.show()``````

Execute the above code , The results are shown in the figure below （ Be careful , Trees can also be seen as a special kind of directed graph . the NetworkX It is mainly used to deal with graphs , So the trees are not as hierarchical as we usually see , But essentially they are consistent ）：

obviously , From the root node a To the leaf node e、g、h、i There are [a->b->c->d->e]、[a->b->f->g]、[a->b->f->h]、[a->b->i].

Specifically （ Non recursive ） The design idea of the algorithm can be inspired from the depth first traversal of the tree . The only thing to notice is that , If there is a bifurcation at a node , We need to maintain an additional stack structure to hold the path that has been obtained in front of the fork . The specific implementation code is given below , Note that this is a non recursive implementation ：

``````majorStack = deque([])
minorStack = deque([])

listoflists = []
a_list = []

entry_node = 'a'

def find_all_paths():
max_times = 0

minorStack.append(entry_node)

popCount = {}

while minorStack:
minLast = minorStack.pop()
majorStack.append(minLast)
a_list.append(minLast)

current_s_nodes = list(T.successors(minLast))
if current_s_nodes:
for element in current_s_nodes:
minorStack.append(element)

majLast = majorStack[-1]
#Loop condition：tos is a leaf OR all children of tos have been accessed
while( not list(T.successors(majLast)) or
( popCount.get(majLast, -1) == len(list(T.successors(majLast))))):
last = majorStack.pop()

if majorStack:
majLast = majorStack[-1]
else: # if majorStack is empty, then finish
return

if popCount.get(majLast, -1) == -1:
popCount[majLast]=1
else:
popCount[majLast]=popCount[majLast]+1

# if last is a leaf, then find a path from the root to a leaf
if not list(T.successors(last)):
listoflists.append(copy.deepcopy(a_list))

a_list.pop()

find_all_paths()

print(listoflists)``````

Execute the above code , The results are as follows ：

``[['a', 'b', 'i'], ['a', 'b', 'f', 'h'], ['a', 'b', 'f', 'g'], ['a', 'b', 'c', 'd', 'e']]``

so , Our algorithm successfully finds the path from the root node to all the leaf nodes .

below , We want to expand the problem , Suppose you want to find all the paths from the entry point to the exit point from a directed graph ？ Be careful , The digraph here is limited to acyclic . for example , Here's an example based on NetworkX Examples of generated directed acyclic graphs ：

``````G = nx.DiGraph()

nx.draw(G, with_labels=True)
plt.show()``````

Execute the above code , The results are shown in the figure below . From the entry node a To the exit node e、g、i、l There are [a->b->c->d->e]、[a->b->f->g]、[a->b->f->h->i]、[a->b->f->h->k->l]、[a->b->j->h->i]、[a->b->j->h->k->l].

Based on the algorithm given above to search the path in the tree , It is very simple to implement similar functions in directed acyclic graphs , We just need to add a line of code ：

``````majorStack = deque([])
minorStack = deque([])

listoflists = []
a_list = []

entry_node = 'a'

def find_all_paths():
max_times = 0

minorStack.append(entry_node)

popCount = {}

while minorStack:
minLast = minorStack.pop()
majorStack.append(minLast)
a_list.append(minLast)

current_s_nodes = list(G.successors(minLast))
if current_s_nodes:
for element in current_s_nodes:
minorStack.append(element)
popCount[element]= -1

majLast = majorStack[-1]
#Loop condition：tos is a leaf OR all children of tos have been accessed
while( not list(G.successors(majLast)) or
( popCount.get(majLast, -1) == len(list(G.successors(majLast))))):
last = majorStack.pop()

if majorStack:
majLast = majorStack[-1]
else: # if majorStack is empty, then finish
return

if popCount.get(majLast, -1) == -1:
popCount[majLast]=1
else:
popCount[majLast]=popCount[majLast]+1

# if last is a leaf, then find a path from the root to a leaf
if not list(G.successors(last)):
listoflists.append(copy.deepcopy(a_list))

a_list.pop()

find_all_paths()
print(listoflists)``````

Execute the above code , The results are as follows ：

``[['a', 'b', 'j', 'h', 'i'], ['a', 'b', 'j', 'h', 'k', 'l'], ['a', 'b', 'f', 'h', 'i'], ['a', 'b', 'f', 'h', 'k', 'l'], ['a', 'b', 'f', 'g'], ['a', 'b', 'c', 'd', 'e']]``

It can be seen that the results obtained are consistent with our expectations .

【 The end of this paper 】

https://chowdera.com/2020/12/20201207141706992i.html