Python Iterative Depth First Search from table

Question

I have the following data table:

child_pid   parent_pid
       1        -1
       2         1
       6        -1
       7         6
       8         7
       9         8
       21       -1
       22       21
       24       -1
       25       24
       26       25
       27       26
       28       27
       29       28
       99        6
       107      99
       108      -1
       109      108
       222      109
       1000      7
       1001     1000

I want to write a python iterative depth-first search that generates the following result:

('final: ',
   [[u'1', u'2'],
   [u'6', u'7', u'8', u'9'],
   [u'6', u'7', u'1000', u'1001'],
   [u'6', u'99', u'107'],
   [u'21', u'22'],
   [u'24', u'25', u'26', u'27', u'28', u'29'],
   [u'108', u'109', u'222']])

The above output was generated using a recursive approach. We can see that all the child/parent relationships are preserved appropriately.

I've utilized the following logic from another tutorial in my attempt to derive an iterative approach:

def dfs_iterative(graph, start):
    stack, path = [start], []

    while stack:
        vertex = stack.pop()
        if vertex in path:
            continue
        path.append(vertex)
        for neighbor in graph[vertex]:
            stack.append(neighbor)

    return path

which results in:

('final: ',
   [[u'1', u'2'],
   [u'6', u'99', u'107', u'7', u'1000', u'1001', u'8', u'9'],
   [u'21', u'22'],
   [u'24', u'25', u'26', u'27', u'28', u'29'],
   [u'108', u'109', u'222']])

We can see that the results are almost identical except for when a node has more than one child. Specifically, node 6 has the following relationships:

6->7->8->9
6->7->1000->1001
6->99->107

In the recursive output above, we see that node 6 is appropriately broken out into its proper path relationships. In my iterative attempt, all of node 6's "descendants" are grouped together into one list. Looking for way to generate the recursive output, but with an iterative approach in python. Thoughts? I appreciate the help!

Minimal, complete, verifiable example applies here. We cannot effectively help you until you post your MCVE code. We need at least the driver program (data set-up and call sequence). The code fragment you posted produces no output. let alone what you provided. — Prune

Prune Prune · Accepted Answer · 2017-08-29T16:07:07

The problem here is that your iterative "equivalent" is not: your algorithm finds graph closure. The result you want is to find individual paths in a tree. When you use the wrong tool, you get a different result.

Your approach appears to start at a given node (ostensibly one of the root nodes), and accumulates individual nodes in an undefined order of neighbors. Instead, try this

pop the top partial_path from stack
vertex <= last element of partial_path
if vertex has no children:
- append partial_path to result.
else
- for each child of vertex
- add (append or push) [partial_path + child] to stack

Does that handle your problem?

Python Iterative Depth First Search from table

1 Answers