1
\$\begingroup\$

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
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$
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

consider renaming your variable rather then using comments

        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.

\$\endgroup\$
3
  • \$\begingroup\$ 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? \$\endgroup\$
    – beoliver
    Commented Jun 17, 2012 at 0:55
  • \$\begingroup\$ one question: why are you creating a subgraph? if the graph contains 1000 keys, this is a bit pointless no? am i missing something? \$\endgroup\$
    – beoliver
    Commented Jun 17, 2012 at 1:16
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Jun 17, 2012 at 1:36
0
\$\begingroup\$

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)
\$\endgroup\$
1
  • \$\begingroup\$ 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? \$\endgroup\$
    – beoliver
    Commented Jun 17, 2012 at 0:24

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.