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\$
2
  • \$\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, 2013 at 1:17
  • \$\begingroup\$ Not a bug, this should return the first step to the station. \$\endgroup\$
    – fread2281
    Mar 31, 2013 at 1:18

3 Answers 3

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\$
2
  • \$\begingroup\$ The first loop needs to be run on all litems and if none are station, it should search recursively \$\endgroup\$
    – fread2281
    Mar 30, 2013 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\$ Mar 30, 2013 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\$
5
  • \$\begingroup\$ Good point, although it seems he couldn't do the max_depth with it... \$\endgroup\$ Mar 31, 2013 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, 2013 at 1:12
  • \$\begingroup\$ Ah, you may well be right. \$\endgroup\$ Mar 31, 2013 at 1:14
  • \$\begingroup\$ max_depth is to limit time. I need speed. \$\endgroup\$
    – fread2281
    Mar 31, 2013 at 1:17
  • \$\begingroup\$ I reimplemented it using a custom BFS and thanks for the indirect pointer! \$\endgroup\$
    – fread2281
    Mar 31, 2013 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\$
2
  • \$\begingroup\$ My code should be a simple breadth first search. \$\endgroup\$
    – fread2281
    May 10, 2014 at 5:08
  • \$\begingroup\$ average edges per vertex? are you using this for wired or wireless? \$\endgroup\$ May 10, 2014 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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