Getting the sum of weights while traversing a graph on python

Question

How should I proceed on doing this? This IS a homework, and I'm having a huge problem with it. Now, the issue is that I must not use libs.

I have a graph like:

{'A': {'C': 2, 'B': 10}, 'C': {'B': 7, 'D': 2}, 'B': {}, 'D': {'A': 5, 'B': 4}}

using dictionaries, taken from a file.

I am using the algorithm at http://www.python.org/doc/essays/graphs/ to find all the paths, so there is no problem there.

But now that I have all the paths from one point to another, I need to sum the weights and get the complete cost on it.

If you could help me, and direct me on some good ways to approach it, I would appreciate it.

Answer 1

gr = {'A': {'C': 2, 'B': 10},
      'C': {'B': 7, 'D': 2},
      'B': {'E': 2},
      'D': {'A': 5, 'B': 4, 'E': 3}
      'E': {}}

def paths(gr, frm, to, path_len=0, visited=None):

    if frm == to:
        return [[to, path_len]]

    visited = visited or []
    result = []
    for point, length in gr[frm].iteritems():
        if point in visited:
            continue
        visited.append(point)
        for sub_path in paths(gr, point, to, path_len + length, visited[:]):
            result.append([frm] + sub_path)

    return result

>>> print paths(gr, 'A', 'E')
[['A', 'C', 'B', 'E', 11], ['A', 'C', 'D', 'E', 7], ['A', 'B', 'E', 12]]

Answer 2

Look at networkx - which is a very good Python graph library. Read its docs and you'll find there's an easy solution -- as it's homework I won't comment more until you find a coding problem.

Answer 3

Well you've done the hard part of finding the path. Now just go through the path and sum those weights. I would use a loop.

int sum=0;
for(int i=0;i<path.size()-1;i++)
    sum+= node.at(i).getWeightFor(node.at(i+1))

where getWeightFor(node) would return the cost to go from that node to another. So if you did A.getWeightFor(C), it would return 2. There are probably better ways to do it, but that is my quick answer to do it. You'd have to make that getWeightFor function, but that should be quite simple. Like I said, the hard part is done. Don't overthink this last bit.