Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

share|improve this question
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. – Hai Vu Mar 31 at 1:17
Not a bug, this should return the first step to the station. – fread2281 Mar 31 at 1:18

2 Answers

up vote 2 down vote accepted 
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 repoted using None than False.

share|improve this answer
The first loop needs to be run on all litems and if none are station, it should search recursively – fread2281 Mar 30 at 19:01
1  
@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" – Winston Ewert♦ Mar 30 at 19:32
up vote 4 down vote

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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