Finding the closest node

Question

I have a function that I need to optimize:

def search(graph, node, maxdepth = 10, depth = 0):
    nodes = []
    for neighbor in graph.neighbors_iter(node):
        if graph.node[neighbor].get('station', False):
            return neighbor
        nodes.append(neighbor)
    for i in nodes:
        if depth+1 > maxdepth:
            return False
        if search(graph, i, maxdepth, depth+1):
            return i
   return False

graph should be a networkx graph object. How can I optimize this? This should find the closest node in the network with 'station' attribute to True.

Answer 1

def search(graph, node, maxdepth = 10, depth = 0):
    nodes = []
    for neighbor in graph.neighbors_iter(node):
        if graph.node[neighbor].get('station', False):
            return neighbor
        nodes.append(neighbor)

Why store the neighbor in the list? Instead of putting it in a list, just combine your two loops.

for i in nodes:

i typically stands for index. I suggest using neighbor to make your code easier to follow

    if depth+1 > maxdepth:
        return False

This doesn't relate to this individual node. What is it doing inside this loop?

        if search(graph, i, maxdepth, depth+1):
            return i
   return False

Failure to find is better reported using None rather than False.

Answer 2

Is there any reason that you are shy from using networkx's functions such as breadth-first search bfs_tree() or depth-first search dfs_tree()? Here is an example of breadth-first search:

import networkx as nx
...
for visiting_node in nx.bfs_tree(graph, node):
    if graph.node[visiting_node].get('station', False):
        print 'Found it' # Do something with visiting_node

Answer 3

Are you implementing some routing protocol? Can you give me more details?

If your networking is based on equal weight (length) of each edges (let's say wired network or wireless network with backbone base station), than you can use breadth first search (fastest searching algorithm which takes \$O(|V|+|E|)\$ times). If you want to find closest nodes base on geometry distance(it could be wireless networks or MANET ad-hoc network), than you need a greedy algorithm.

There are two ways to optimize your func:

• Searching algorithm: If you are looking for the shortest path or closest node in geometry distance, than you'd better to use greedy approach, BFS return shortest path only when edges have equal weight (cost, length, etc..). You probably know Dijkstra algorithm because it's widely used in network routings. So use a greedy algorithm would make your network links more stable and robust. You can choose Best first search, Dijkstra algorithm, A* algorithm(if you have information of target nodes).

  Although Breadth first search and depth first search are available to use in python, but they have some limitations: BFS tree is based on the entry of your neighbor list, it's won't guarantee to find shortest path (it's not a greedy algorithm). Same to DFS and your algorithm.

• choose a proper data structure to build your graph: A good data structure is always the easiest way to make your program faster. If you have more edges then vertexes (\$E > V^2\$) than use a neighbor matrix. Because in this scenario, if you are using a neighbor list, it will take a considerable time to find out each edge whether belong to your graph or not.

  As a side effect, the memory overhead is huge for neighbor matrix.