ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 13 Oct 2015 20:20:46 +0200Counting paths in directed graph with multiedgeshttps://ask.sagemath.org/question/29949/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.add_edge(1,2,'a')
A.add_edge(1,2,'b')
A.add_edge(2,3,'c')
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?Mon, 12 Oct 2015 22:01:09 +0200https://ask.sagemath.org/question/29949/counting-paths-in-directed-graph-with-multiedges/Answer by fidbc for <p>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:</p>
<pre><code>A = DiGraph(multiedges=True)
A.add_edge(1,2,'a')
A.add_edge(1,2,'b')
A.add_edge(2,3,'c')
A.graphplot(edge_labels=True).show()
A.all_paths(1,3)
</code></pre>
<p>returns <code>[[1,2,3]]</code>. I would like to have it return 2 paths, ideally listed by the edges instead of the vertices, e.g. <code>[a,c]</code> and <code>[b,c]</code>. Any recommendations?</p>
https://ask.sagemath.org/question/29949/counting-paths-in-directed-graph-with-multiedges/?answer=29953#post-id-29953This 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
Tue, 13 Oct 2015 03:19:40 +0200https://ask.sagemath.org/question/29949/counting-paths-in-directed-graph-with-multiedges/?answer=29953#post-id-29953Comment by mthomas for <p>This does not appear to be implemented in sage. The code below may be an option to get that functionality</p>
<pre><code>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
</code></pre>
<p>Then you can use</p>
<pre><code>paths=all_paths(A,1,3)
print len(paths)
for p in paths:
print p
</code></pre>
https://ask.sagemath.org/question/29949/counting-paths-in-directed-graph-with-multiedges/?comment=29972#post-id-29972This looks great, thank you! I just changed line 9 from A.edge_boundary... to G.edge_boundary.Tue, 13 Oct 2015 17:28:49 +0200https://ask.sagemath.org/question/29949/counting-paths-in-directed-graph-with-multiedges/?comment=29972#post-id-29972Comment by fidbc for <p>This does not appear to be implemented in sage. The code below may be an option to get that functionality</p>
<pre><code>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
</code></pre>
<p>Then you can use</p>
<pre><code>paths=all_paths(A,1,3)
print len(paths)
for p in paths:
print p
</code></pre>
https://ask.sagemath.org/question/29949/counting-paths-in-directed-graph-with-multiedges/?comment=29977#post-id-29977Right, thanks for pointing that out!Tue, 13 Oct 2015 20:20:46 +0200https://ask.sagemath.org/question/29949/counting-paths-in-directed-graph-with-multiedges/?comment=29977#post-id-29977