# Counting paths in directed graph with multiedges

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)
A.graphplot(edge_labels=True).show()
A.all_paths(1,3)


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 close merge delete

Sort by » oldest newest most voted 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
new_paths=[]
for p in old_paths: # we will traverse each path replacing each edge by a list of (multi) edges
multi_path=[]
for i,u in enumerate(p):
if i < len(p)-1:
v = p[i+1]
edges = G.edge_boundary([u], [v] )
multi_path.append(edges)
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

paths=all_paths(A,1,3)
print len(paths)
for p in paths:
print p

more

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