python - find first n edges,breadth first search -

python - find first n edges,breadth first search -

problem: find first n nearest edges(2000) given border object in directed cyclic graph.

data structure: link class , node class. link class has , node, points respective node objects. node object has incoming , outgoing list of link objects.

error: suffering runtimeerror: maximum recursion depth exceeded.could help me find way around this.let me know if there wrong logic or code needs optimized. believe follow bfs strategy of making queu out of objects related nodes traverse , see if it has been visited , seek recursion over.

def start_search(self,link_object,neighbour_links): buffer_links=[] link_object.visited_flag=1 neighbour_links.append(link_object) from_node=link_object.from_node to_node=link_object.to_node [buffer_links.append(link_object) link_object in from_node.incoming_links] [buffer_links.append(link_object) link_object in from_node.outgoing_links] [buffer_links.append(link_object) link_object in to_node.outgoing_links] [buffer_links.append(link_object) link_object in to_node.incoming_links] while len(buffer_links)>0 , len(neighbour_links)<1000: link_object=buffer_links.pop() if link_object.visited_flag==0: self.start_search(link_object,neighbour_links) homecoming neighbour_links

you can avoid using recursion using advancing wavefront algorithm (breadth first search) on nodes. here's outline of algorithm, it's little adaptation create work edges:

track topological distances using dictionary top_dist empty. let dist = 0 put initial nodes in set wavefront. set top_dist[node] = dist each node in wavefront. for each node adjacent wavefront not in top_dist, add together node set next_wavefront. increment dist set wavefront = next_wavefront repeat 4 until no farther nodes reachable.

if nodes remain unvisited, graph has multiple weak components.

if initial nodes in step 3 endpoints of initial edge, can utilize top_dist map on edge's nodes distances edges. think useful definition of distance border min(top_dist(e1), top_dist(e2)) + 1. have distance each edge, can grab closest 2000.

this algorithm o(|n|+|e|) -- linear on sum of number of edges , nodes.

python algorithm breadth-first-search directed-graph