data transfer - Trying to iterate through a graph breadth first in Python -

in code, trying create implementation of data flow network. although particularities of how going doing aren't particularly important, need make program go through graph in breadth first fashion. when code:

def traverse(self):     source = self._nodelist[0]     self.sand_pile(source)     return  def sand_pile(self, start):     sink in start._sinks:         //algorithm sending data here     s in start._sinks:         self.sand_pile(s)     return 

the compiler correctly goes through first node , sinks breadth first, when goes on repeat process sinks, starts go depth first.

another way of explaining following: if source of graph has 2 or 3 sinks, each of have 2 or 3 of own sinks, compiler print them out , pass value them successfully, proceed go depth first rest of nodes until reaches end. going wrong in logic?

p.s. if not explaining well, please leave comment can clarify.

you mixing bfs (breadth first search) , dfs (depth first search) in approach.

when sending data in sand_pile method, iterate horizontally through children of current node, approach of implementing bfs. first level of children (or sinks in case) done, perform recursion step on each of child nodes. results in schema this:

• start sand_pile on node on level 0 (root node)
• distribute data children on level 1
• start sand_pile on first children of level 1
• distribute data of children on level 2
• ... keep on going dfs out-of-line data distribution

the flaw is, employ recursion bfs.

you can use recursive descent (i.e. stack-like iteration) dfs, bfs, should create buffer contains nodes in desired order (i.e. queue-like iteration)

the steps can following

1. get maximum depth of tree
2. for each depth level, put nodes reside on level list
3. concatenate lists obtain [lvl0_node0, lvl1_node0, lvl1_node1, lvl1_node2, lvl2_node_0, ..., lvln_nodem]
4. iterate on queue