3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You might have a bug: if search(graph, i, ...): return i ==> the search() function might return something other than i, yet you are returning i. \$\endgroup\$ – Hai Vu Mar 31 '13 at 1:17
  • \$\begingroup\$ Not a bug, this should return the first step to the station. \$\endgroup\$ – fread2281 Mar 31 '13 at 1:18
4
\$\begingroup\$
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.

\$\endgroup\$
  • \$\begingroup\$ The first loop needs to be run on all litems and if none are station, it should search recursively \$\endgroup\$ – fread2281 Mar 30 '13 at 19:01
  • 2
    \$\begingroup\$ @fread2281, my bad... I didn't think of that. Actually, I think that makes your code wrong. Its implementing a DFS, so it wasn't neccesairlly find the closest "station" \$\endgroup\$ – Winston Ewert Mar 30 '13 at 19:32
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Good point, although it seems he couldn't do the max_depth with it... \$\endgroup\$ – Winston Ewert Mar 31 '13 at 1:06
  • \$\begingroup\$ I think max_depth is to prevent circular links in a graph. the bfs_tree() function ensures no circular references. \$\endgroup\$ – Hai Vu Mar 31 '13 at 1:12
  • \$\begingroup\$ Ah, you may well be right. \$\endgroup\$ – Winston Ewert Mar 31 '13 at 1:14
  • \$\begingroup\$ max_depth is to limit time. I need speed. \$\endgroup\$ – fread2281 Mar 31 '13 at 1:17
  • \$\begingroup\$ I reimplemented it using a custom BFS and thanks for the indirect pointer! \$\endgroup\$ – fread2281 Mar 31 '13 at 16:54
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ My code should be a simple breadth first search. \$\endgroup\$ – fread2281 May 10 '14 at 5:08
  • \$\begingroup\$ average edges per vertex? are you using this for wired or wireless? \$\endgroup\$ – Charles Chow May 10 '14 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.