# Finding node paths

I am wondering if anyone has any ideas for improving the following. Personally I am 'happy' with it, apart from the first for loop. I was thinking of another way of writing this, but perhaps it is ok.

def findnodepaths(nodepaths, graph, *nodes):

# nodepaths == list()
# graph == defaultdict(set)
# *nodes == 'foo','bar',... possible items in the graph

nodeset = set(nodes) & set(graph.keys())

# nodeset == nodes that are in the graph ... avoids try / if

nodepaths = [(nodeA,weight,nodeB) for nodeA in nodeset for (nodeB,weight) in graph[nodeA]]

for path in nodepaths:
# for every item in list
*xs, nodeA = path
# nodeA == last value added, xs == all the rest
for (nodeB,weight) in graph[nodeA]:
# search again ... just like we all ready have
if nodeB not in xs:
# if new val not in the triple / quadruple ...
nodepaths.append( path + (weight,nodeB) )
# add new item to list based on its match
# repeat until no new paths can be found

return nodeset, nodepaths
# return nodes that were found + all of their paths


def findnodepaths(nodepaths, graph, *nodes):


By python convention, you should really separate the words with underscores. i.e. find_node_paths. I'd also wonder if it makes sense to take *nodes, rather then expecting a list to be sent in.

# nodepaths == list()


Its not clear why you pass this in, rather then just make it here

# graph == defaultdict(set)
# *nodes == 'foo','bar',... possible items in the graph


This sort of documentation should be in a doctoring, not comments

    nodeset = set(nodes) & set(graph.keys())


set(graph.keys()) == set(graph), although you may prefer to be explicit.

# nodeset == nodes that are in the graph ... avoids try / if

nodepaths = [(nodeA,weight,nodeB) for nodeA in nodeset for (nodeB,weight) in graph[nodeA]]


I'd store a path as a list, not a tuple.

    for path in nodepaths:
# for every item in list


That's not a very helpful comment, the syntax already told me that.

        *xs, nodeA = path
# nodeA == last value added, xs == all the rest


        for (nodeB,weight) in graph[nodeA]:


Parens are unnecessary

# search again ... just like we all ready have


Again, noisy comment

            if nodeB not in xs:
# if new val not in the triple / quadruple ...
nodepaths.append( path + (weight,nodeB) )


You shouldn't be modifying lists currently having a for loop operating on them. Its considered bad style

# add new item to list based on its match
# repeat until no new paths can be found

return nodeset, nodepaths
# return nodes that were found + all of their paths


I'd write this as a recursive function:

def _findnodepaths(graph, path, weights):
for node, weight in graph[path[-1]]:
if node not in path:
yield _findnodepaths(graph, path + [node], weights + [node])
yield path

def findnodepaths(graph, nodes):
nodeset = set(nodes) & set(graph)
subgraph = dict( (key, value) for key, value in graph.items())

nodepaths = []
for key in graph:
nodepaths.extend(_findnodepaths(subgraph, [key], [])
return nodeset, node paths


Whether that's better or not is subjective, I think it shows the algorithm better.

• thanks for the break down. I must admit the documentation was only for this site. I'm interested in your comment about modifying lists while working on them. That part made me happy :) ... is it a purely stylistic guide? Agree about the list being passed in. I have changed that already. Thank you for the re-write. It is fascinating seeing how others would approach a problem. Algorithm wise, does it seem ok though? Commented Jun 17, 2012 at 0:55
• one question: why are you creating a subgraph? if the graph contains 1000 keys, this is a bit pointless no? am i missing something? Commented Jun 17, 2012 at 1:16
• @user969617, adding to the list works in the current implementation, but I believe no guarantees are made that it will always work. I figured the subgraph might simplify the code a bit, but it didn't really work out that way. Commented Jun 17, 2012 at 1:36

I have no way to test this, but is this what you are looking for?

def findnodepaths(nodepaths, graph, *nodes):

nodeset = set(nodes) & set(graph.keys())
nodepaths = [(nodeA,weight,nodeB) for nodeA in nodeset
for (nodeB,weight) in graph[nodeA]]

newnp = [path + (weight,nodeB) for path in nodepaths
for (nodeB,weight) in graph[nodeA] if nodeB not in path[::-1][1:]]

return nodeset, (nodepaths + newnp)

• Very nearly. The for loop that I use for path in nodepaths effectively creates a loop, that constantly updates the nodepaths until it can not find any more links in the graph (a dictionary). I was wondering how if this for loop could be written any other way? Commented Jun 17, 2012 at 0:24