Ask Your Question

Counting paths in directed graph with multiedges

asked 2015-10-12 15:01:09 -0500

mthomas gravatar image

I would like to could paths in a directed graph with multiedges, where taking a different edge between a given pair of vertices is counted as a new path. For example:

A = DiGraph(multiedges=True)

returns [[1,2,3]]. I would like to have it return 2 paths, ideally listed by the edges instead of the vertices, e.g. [a,c] and [b,c]. Any recommendations?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2015-10-12 20:19:40 -0500

fidbc gravatar image

updated 2015-10-13 13:21:17 -0500

This does not appear to be implemented in sage. The code below may be an option to get that functionality

def all_paths(G,a,b):
    old_paths = G.all_paths( a, b ) # get all paths without edge multiplicity
    for p in old_paths: # we will traverse each path replacing each edge by a list of (multi) edges
        for i,u in enumerate(p):
            if i < len(p)-1:
                v = p[i+1]
                edges = G.edge_boundary([u], [v] )
        new_paths.extend( CartesianProduct(*multi_path )) # each sequence of (multi) edges will be a source of multiple paths
    return new_paths

Then you can use

print len(paths)
for p in paths:
    print p
edit flag offensive delete link more


This looks great, thank you! I just changed line 9 from A.edge_boundary... to G.edge_boundary.

mthomas gravatar imagemthomas ( 2015-10-13 10:28:49 -0500 )edit

Right, thanks for pointing that out!

fidbc gravatar imagefidbc ( 2015-10-13 13:20:46 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2015-10-12 15:01:09 -0500

Seen: 97 times

Last updated: Oct 13 '15