find first n edges,breadth first search

Question

Problem: To find first n nearest edges(2000) given an edge object in a directed cyclic graph.

Data Structure: Link class and Node class. The link class has a from and to node, which points to respective node objects. The node object has an incoming and outgoing list of link objects.

Error: I am suffering from a RuntimeError: maximum recursion depth exceeded.Could you help me find a way around this.Let me know if there is something wrong with the logic or the code needs to be optimized. I believe I follow the BFS strategy of making a queu out of objects related nodes that i could traverse and see if it it has been visited and try 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) for link_object in from_node.incoming_links]
    [buffer_links.append(link_object) for link_object in from_node.outgoing_links]
    [buffer_links.append(link_object) for link_object in to_node.outgoing_links]
    [buffer_links.append(link_object) for link_object in to_node.incoming_links]
    while len(buffer_links)>0 and len(neighbour_links)<1000:
        link_object=buffer_links.pop()
        if link_object.visited_flag==0:
           self.start_search(link_object,neighbour_links)
    return neighbour_links

Answer 1

You can avoid using recursion using an advancing wavefront algorithm (breadth first search) on the nodes. Here's an outline of the algorithm, it's a small adaptation to make it work for edges:

1. Track topological distances using a dictionary top_dist which is initially empty.
2. Let dist = 0
3. Put the initial nodes in set wavefront.
4. Set top_dist[node] = dist for each node in wavefront.
5. For each node adjacent to wavefront that is not in top_dist, add that node to set next_wavefront.
6. Increment dist
7. Set wavefront = next_wavefront
8. Repeat from 4 until no further nodes are reachable.

If some nodes remain unvisited, the graph has multiple weak components.

If the initial nodes in step 3 are the endpoints of your initial edge, then you can use the top_dist map on the edge's nodes to get distances to the edges. I think a useful definition of distance to an edge is min(top_dist(e1), top_dist(e2)) + 1. Now that you have a distance to each edge, you can grab the closest 2000.

This algorithm is O(|N|+|E|) -- linear on the sum of the number of edges and nodes.

Answer 2

Using a DAG represented as a dictionary of nodes mapped to their successors, you can loop over nodes as you discover them:

>>> def bfs(dag, start, maximum):
        'Breadth-first search up to a given maximum number of nearest nodes'
        nearest = [start]
        seen = {start}
        for pred in nearest:
            for succ in dag.get(pred, ()):
                if succ not in seen:
                    seen.add(succ)
                    nearest.append(succ)
                    if len(nearest) == maximum:
                        return nearest
        return nearest
>>> dag = {'start': ['a', 'b', 'c'],
           'b': ['m', 'n'],
           'c': ['n', 'z'],
           'n': ['z'],
          }
>>> bfs(dag, 'start', 5)
['start', 'a', 'c', 'b', 'z']