ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 19 May 2017 07:40:07 -0500Iterate over acyclic subdigraphshttps://ask.sagemath.org/question/37611/iterate-over-acyclic-subdigraphs/I have a graph `D`, and would like to iterate over its (maximal) acyclic subdigraphs (not necessarily induced).
My current best bet is to iterate over all permutations of the vertex set of D and, for each one, create an acyclic digraph A by going through each edge of D in turn and adding to A only those edges `ij` where `i` is less than `j` in the current permutation.
But this seems awfully inefficient.
More precisely:
D = DiGraph()
D.add_edges([[0,1],[0,2],[1,2],[1,3],[2,3],[3,4],[4,5],[4,6],[5,6],[5,0],[6,0]])
n = D.num_verts()
for p in Permutations(n):
A = DiGraph()
for e in D.edges():
if p[e[0]] < p[e[1]]:
A.add_edge(p[e[0]] -1,p[e[1]] -1)
# Here A is a maximal acyclic subdigraph of D
do_stuff(A)
Any ideas would be greatly appreciated.Wed, 17 May 2017 10:34:11 -0500https://ask.sagemath.org/question/37611/iterate-over-acyclic-subdigraphs/Answer by David Coudert for <p>I have a graph <code>D</code>, and would like to iterate over its (maximal) acyclic subdigraphs (not necessarily induced).</p>
<p>My current best bet is to iterate over all permutations of the vertex set of D and, for each one, create an acyclic digraph A by going through each edge of D in turn and adding to A only those edges <code>ij</code> where <code>i</code> is less than <code>j</code> in the current permutation. </p>
<p>But this seems awfully inefficient.</p>
<p>More precisely:</p>
<pre><code>D = DiGraph()
D.add_edges([[0,1],[0,2],[1,2],[1,3],[2,3],[3,4],[4,5],[4,6],[5,6],[5,0],[6,0]])
n = D.num_verts()
for p in Permutations(n):
A = DiGraph()
for e in D.edges():
if p[e[0]] < p[e[1]]:
A.add_edge(p[e[0]] -1,p[e[1]] -1)
# Here A is a maximal acyclic subdigraph of D
do_stuff(A)
</code></pre>
<p>Any ideas would be greatly appreciated.</p>
https://ask.sagemath.org/question/37611/iterate-over-acyclic-subdigraphs/?answer=37628#post-id-37628This is certainly not an easy question and I have no better algorithm in mind.
I recommend to use `Permutations(D.vertices())` instead. This is safer for instance if you remove vertex `0`.
Furthermore, with your code you may generate multiple times the same acyclic orientation.
sage: D = DiGraph(graphs.PathGraph(3))
sage: print D.edges(labels=0)
[(0, 1), (1, 0), (1, 2), (2, 1)]
sage: for p in Permutations(D.vertices()):
....: A = DiGraph([(p[u],p[v]) for u,v in D.edges(labels=0) if p[u]<p[v]])
....: print A.edges(labels=0)
....:
[(0, 1), (1, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]
[(0, 1), (1, 2)]
One solution is to keep track of previous sets of edges, but this is certainly not scalable. I'm using type `Set` since it is hashable.
sage: D = DiGraph(graphs.PathGraph(3))
sage: orientations = set()
sage: for p in Permutations(D.vertices()):
....: E = [(p[u],p[v]) for u,v in D.edges(labels=0) if p[u]<p[v]]
....: SE = Set(E)
....: if SE in orientations:
....: continue
....: orientations.add(SE)
....: A = DiGraph(E)
....: print A.edges(labels=0)
....:
[(0, 1), (1, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]
For the example you gave, your code generates 5040 graphs while my code generates only 4055 graphs.
Fri, 19 May 2017 07:40:07 -0500https://ask.sagemath.org/question/37611/iterate-over-acyclic-subdigraphs/?answer=37628#post-id-37628