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.Mon, 18 Apr 2022 19:05:27 +0200Finding all digraphs up to isomorphism for a given undirected graph using Sagehttps://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/Given an undirected finite connected graph (without loops).
I have two questions:
1. Is there an easy way using Sage to obtain all ways to make it a directed graph (such that for each edge there is now one directed edge) up to isomorphism of graphs?
2. Is there an easy way using Sage to obtain all ways to make it a directed graph up to isomorphism of graphs and such that additionally the two opposite directed graphs get also identified?
Interesting examples might be graphs of Dynkin type such as E_8.
For $A_3$ for example in the first question there are 3 ways to make it into a directed graph.
In the second question there are two ways for $A_3$.
So the input should be a undirected finite connected graph and the output all possible orientations up to graph isomorphisms (and maybe up to taking the opposite graph as in question 2).Sat, 16 Apr 2022 19:05:57 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/Answer by David Coudert for <p>Given an undirected finite connected graph (without loops).
I have two questions:</p>
<ol>
<li><p>Is there an easy way using Sage to obtain all ways to make it a directed graph (such that for each edge there is now one directed edge) up to isomorphism of graphs?</p></li>
<li><p>Is there an easy way using Sage to obtain all ways to make it a directed graph up to isomorphism of graphs and such that additionally the two opposite directed graphs get also identified?</p></li>
</ol>
<p>Interesting examples might be graphs of Dynkin type such as E_8.</p>
<p>For $A_3$ for example in the first question there are 3 ways to make it into a directed graph.
In the second question there are two ways for $A_3$.</p>
<p>So the input should be a undirected finite connected graph and the output all possible orientations up to graph isomorphisms (and maybe up to taking the opposite graph as in question 2).</p>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?answer=62032#post-id-62032For the first question, you can use the iterator over all orientations of a graph
sage: def orientations_up_to_isomorphisms(G):
....: s = set()
....: for d in G.orientations():
....: c = d.canonical_label().copy(immutable=True)
....: s.add(c)
....: return s
....:
sage: D4 = Graph({1: [2], 2: [3,4]})
sage: len(orientations_up_to_isomorphisms(D4))
4
sage: E6 = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: len(orientations_up_to_isomorphisms(E6))
20
Mon, 18 Apr 2022 19:05:27 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?answer=62032#post-id-62032Answer by rburing for <p>Given an undirected finite connected graph (without loops).
I have two questions:</p>
<ol>
<li><p>Is there an easy way using Sage to obtain all ways to make it a directed graph (such that for each edge there is now one directed edge) up to isomorphism of graphs?</p></li>
<li><p>Is there an easy way using Sage to obtain all ways to make it a directed graph up to isomorphism of graphs and such that additionally the two opposite directed graphs get also identified?</p></li>
</ol>
<p>Interesting examples might be graphs of Dynkin type such as E_8.</p>
<p>For $A_3$ for example in the first question there are 3 ways to make it into a directed graph.
In the second question there are two ways for $A_3$.</p>
<p>So the input should be a undirected finite connected graph and the output all possible orientations up to graph isomorphisms (and maybe up to taking the opposite graph as in question 2).</p>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?answer=62017#post-id-62017An efficient way is to use `directg` from nauty, which is accessible in SageMath through `digraphs.nauty_directg`. The option `-o` serves to orient each edge in only one direction.
$D_4$ orientations up to isomorphism:
sage: G = Graph({1: [2], 2: [3,4]})
sage: [g.edges(labels=False) for g in digraphs.nauty_directg(G, options='-o')]
[[(0, 1), (1, 2), (1, 3)],
[(0, 1), (1, 2), (3, 1)],
[(0, 1), (2, 1), (3, 1)],
[(1, 0), (1, 2), (1, 3)]]
$E_6$ orientations up to isomorphism:
sage: G = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: [g.edges(labels=False) for g in digraphs.nauty_directg(G, options='-o')]
[[(0, 1), (1, 2), (2, 3), (2, 5), (3, 4)],
[(0, 1), (1, 2), (2, 3), (2, 5), (4, 3)],
[(0, 1), (1, 2), (2, 3), (3, 4), (5, 2)],
[(0, 1), (1, 2), (2, 3), (4, 3), (5, 2)],
[(0, 1), (1, 2), (2, 5), (3, 2), (3, 4)],
[(0, 1), (1, 2), (2, 5), (3, 2), (4, 3)],
[(0, 1), (1, 2), (3, 2), (3, 4), (5, 2)],
[(0, 1), (1, 2), (3, 2), (4, 3), (5, 2)],
[(0, 1), (2, 1), (2, 3), (2, 5), (3, 4)],
[(0, 1), (2, 1), (2, 3), (2, 5), (4, 3)],
[(0, 1), (2, 1), (2, 3), (3, 4), (5, 2)],
[(0, 1), (2, 1), (2, 3), (4, 3), (5, 2)],
[(0, 1), (2, 1), (2, 5), (3, 2), (3, 4)],
[(0, 1), (2, 1), (3, 2), (3, 4), (5, 2)],
[(1, 0), (1, 2), (2, 3), (2, 5), (3, 4)],
[(1, 0), (1, 2), (2, 3), (3, 4), (5, 2)],
[(1, 0), (1, 2), (2, 5), (3, 2), (3, 4)],
[(1, 0), (1, 2), (3, 2), (3, 4), (5, 2)],
[(1, 0), (2, 1), (2, 3), (2, 5), (3, 4)],
[(1, 0), (2, 1), (2, 3), (3, 4), (5, 2)]]
Here's how you could quotient by your equivalence relation:
def orientations_up_to_opposites(G):
results = []
for g in digraphs.nauty_directg(G, options='-o'):
g_canon = g.canonical_label()
g_opposite_canon = DiGraph([(b,a) for a,b in g.edges(labels=False)]).canonical_label()
if not (g_canon in results or g_opposite_canon in results):
results.append(g_canon)
return results
$D_4$ orientations up to isomorphism and opposites:
sage: G = Graph({1: [2], 2: [3,4]})
sage: [g.edges(labels=False) for g in orientations_up_to_opposites(G)]
[[(0, 3), (3, 1), (3, 2)], [(0, 3), (1, 3), (2, 3)]]
$E_6$ orientations up to isomorphism and opposites:
sage: G = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: [g.edges(labels=False) for g in orientations_up_to_opposites(G)]
[[(0, 4), (3, 2), (4, 5), (5, 1), (5, 3)],
[(0, 5), (1, 3), (3, 4), (4, 2), (4, 5)],
[(0, 5), (1, 4), (2, 3), (3, 5), (5, 4)],
[(0, 4), (1, 3), (1, 5), (4, 5), (5, 2)],
[(0, 4), (1, 3), (3, 5), (4, 5), (5, 2)],
[(0, 5), (1, 4), (2, 3), (2, 5), (4, 5)],
[(0, 5), (1, 4), (2, 3), (3, 5), (4, 5)],
[(0, 5), (1, 4), (2, 3), (2, 4), (2, 5)],
[(0, 5), (1, 4), (2, 3), (3, 4), (3, 5)],
[(0, 5), (1, 3), (1, 4), (4, 2), (4, 5)]]Sun, 17 Apr 2022 10:46:31 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?answer=62017#post-id-62017Comment by klaaa for <p>An efficient way is to use <code>directg</code> from nauty, which is accessible in SageMath through <code>digraphs.nauty_directg</code>. The option <code>-o</code> serves to orient each edge in only one direction.</p>
<p>$D_4$ orientations up to isomorphism:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3,4]})
sage: [g.edges(labels=False) for g in digraphs.nauty_directg(G, options='-o')]
[[(0, 1), (1, 2), (1, 3)],
[(0, 1), (1, 2), (3, 1)],
[(0, 1), (2, 1), (3, 1)],
[(1, 0), (1, 2), (1, 3)]]
</code></pre>
<p>$E_6$ orientations up to isomorphism:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: [g.edges(labels=False) for g in digraphs.nauty_directg(G, options='-o')]
[[(0, 1), (1, 2), (2, 3), (2, 5), (3, 4)],
[(0, 1), (1, 2), (2, 3), (2, 5), (4, 3)],
[(0, 1), (1, 2), (2, 3), (3, 4), (5, 2)],
[(0, 1), (1, 2), (2, 3), (4, 3), (5, 2)],
[(0, 1), (1, 2), (2, 5), (3, 2), (3, 4)],
[(0, 1), (1, 2), (2, 5), (3, 2), (4, 3)],
[(0, 1), (1, 2), (3, 2), (3, 4), (5, 2)],
[(0, 1), (1, 2), (3, 2), (4, 3), (5, 2)],
[(0, 1), (2, 1), (2, 3), (2, 5), (3, 4)],
[(0, 1), (2, 1), (2, 3), (2, 5), (4, 3)],
[(0, 1), (2, 1), (2, 3), (3, 4), (5, 2)],
[(0, 1), (2, 1), (2, 3), (4, 3), (5, 2)],
[(0, 1), (2, 1), (2, 5), (3, 2), (3, 4)],
[(0, 1), (2, 1), (3, 2), (3, 4), (5, 2)],
[(1, 0), (1, 2), (2, 3), (2, 5), (3, 4)],
[(1, 0), (1, 2), (2, 3), (3, 4), (5, 2)],
[(1, 0), (1, 2), (2, 5), (3, 2), (3, 4)],
[(1, 0), (1, 2), (3, 2), (3, 4), (5, 2)],
[(1, 0), (2, 1), (2, 3), (2, 5), (3, 4)],
[(1, 0), (2, 1), (2, 3), (3, 4), (5, 2)]]
</code></pre>
<p>Here's how you could quotient by your equivalence relation:</p>
<pre><code>def orientations_up_to_opposites(G):
results = []
for g in digraphs.nauty_directg(G, options='-o'):
g_canon = g.canonical_label()
g_opposite_canon = DiGraph([(b,a) for a,b in g.edges(labels=False)]).canonical_label()
if not (g_canon in results or g_opposite_canon in results):
results.append(g_canon)
return results
</code></pre>
<p>$D_4$ orientations up to isomorphism and opposites:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3,4]})
sage: [g.edges(labels=False) for g in orientations_up_to_opposites(G)]
[[(0, 3), (3, 1), (3, 2)], [(0, 3), (1, 3), (2, 3)]]
</code></pre>
<p>$E_6$ orientations up to isomorphism and opposites:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: [g.edges(labels=False) for g in orientations_up_to_opposites(G)]
[[(0, 4), (3, 2), (4, 5), (5, 1), (5, 3)],
[(0, 5), (1, 3), (3, 4), (4, 2), (4, 5)],
[(0, 5), (1, 4), (2, 3), (3, 5), (5, 4)],
[(0, 4), (1, 3), (1, 5), (4, 5), (5, 2)],
[(0, 4), (1, 3), (3, 5), (4, 5), (5, 2)],
[(0, 5), (1, 4), (2, 3), (2, 5), (4, 5)],
[(0, 5), (1, 4), (2, 3), (3, 5), (4, 5)],
[(0, 5), (1, 4), (2, 3), (2, 4), (2, 5)],
[(0, 5), (1, 4), (2, 3), (3, 4), (3, 5)],
[(0, 5), (1, 3), (1, 4), (4, 2), (4, 5)]]
</code></pre>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62021#post-id-62021Thank you very much again!Sun, 17 Apr 2022 11:07:18 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62021#post-id-62021Comment by rburing for <p>An efficient way is to use <code>directg</code> from nauty, which is accessible in SageMath through <code>digraphs.nauty_directg</code>. The option <code>-o</code> serves to orient each edge in only one direction.</p>
<p>$D_4$ orientations up to isomorphism:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3,4]})
sage: [g.edges(labels=False) for g in digraphs.nauty_directg(G, options='-o')]
[[(0, 1), (1, 2), (1, 3)],
[(0, 1), (1, 2), (3, 1)],
[(0, 1), (2, 1), (3, 1)],
[(1, 0), (1, 2), (1, 3)]]
</code></pre>
<p>$E_6$ orientations up to isomorphism:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: [g.edges(labels=False) for g in digraphs.nauty_directg(G, options='-o')]
[[(0, 1), (1, 2), (2, 3), (2, 5), (3, 4)],
[(0, 1), (1, 2), (2, 3), (2, 5), (4, 3)],
[(0, 1), (1, 2), (2, 3), (3, 4), (5, 2)],
[(0, 1), (1, 2), (2, 3), (4, 3), (5, 2)],
[(0, 1), (1, 2), (2, 5), (3, 2), (3, 4)],
[(0, 1), (1, 2), (2, 5), (3, 2), (4, 3)],
[(0, 1), (1, 2), (3, 2), (3, 4), (5, 2)],
[(0, 1), (1, 2), (3, 2), (4, 3), (5, 2)],
[(0, 1), (2, 1), (2, 3), (2, 5), (3, 4)],
[(0, 1), (2, 1), (2, 3), (2, 5), (4, 3)],
[(0, 1), (2, 1), (2, 3), (3, 4), (5, 2)],
[(0, 1), (2, 1), (2, 3), (4, 3), (5, 2)],
[(0, 1), (2, 1), (2, 5), (3, 2), (3, 4)],
[(0, 1), (2, 1), (3, 2), (3, 4), (5, 2)],
[(1, 0), (1, 2), (2, 3), (2, 5), (3, 4)],
[(1, 0), (1, 2), (2, 3), (3, 4), (5, 2)],
[(1, 0), (1, 2), (2, 5), (3, 2), (3, 4)],
[(1, 0), (1, 2), (3, 2), (3, 4), (5, 2)],
[(1, 0), (2, 1), (2, 3), (2, 5), (3, 4)],
[(1, 0), (2, 1), (2, 3), (3, 4), (5, 2)]]
</code></pre>
<p>Here's how you could quotient by your equivalence relation:</p>
<pre><code>def orientations_up_to_opposites(G):
results = []
for g in digraphs.nauty_directg(G, options='-o'):
g_canon = g.canonical_label()
g_opposite_canon = DiGraph([(b,a) for a,b in g.edges(labels=False)]).canonical_label()
if not (g_canon in results or g_opposite_canon in results):
results.append(g_canon)
return results
</code></pre>
<p>$D_4$ orientations up to isomorphism and opposites:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3,4]})
sage: [g.edges(labels=False) for g in orientations_up_to_opposites(G)]
[[(0, 3), (3, 1), (3, 2)], [(0, 3), (1, 3), (2, 3)]]
</code></pre>
<p>$E_6$ orientations up to isomorphism and opposites:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: [g.edges(labels=False) for g in orientations_up_to_opposites(G)]
[[(0, 4), (3, 2), (4, 5), (5, 1), (5, 3)],
[(0, 5), (1, 3), (3, 4), (4, 2), (4, 5)],
[(0, 5), (1, 4), (2, 3), (3, 5), (5, 4)],
[(0, 4), (1, 3), (1, 5), (4, 5), (5, 2)],
[(0, 4), (1, 3), (3, 5), (4, 5), (5, 2)],
[(0, 5), (1, 4), (2, 3), (2, 5), (4, 5)],
[(0, 5), (1, 4), (2, 3), (3, 5), (4, 5)],
[(0, 5), (1, 4), (2, 3), (2, 4), (2, 5)],
[(0, 5), (1, 4), (2, 3), (3, 4), (3, 5)],
[(0, 5), (1, 3), (1, 4), (4, 2), (4, 5)]]
</code></pre>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62020#post-id-62020I've updated the answer to address the second part of the question.Sun, 17 Apr 2022 11:03:29 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62020#post-id-62020Comment by klaaa for <p>An efficient way is to use <code>directg</code> from nauty, which is accessible in SageMath through <code>digraphs.nauty_directg</code>. The option <code>-o</code> serves to orient each edge in only one direction.</p>
<p>$D_4$ orientations up to isomorphism:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3,4]})
sage: [g.edges(labels=False) for g in digraphs.nauty_directg(G, options='-o')]
[[(0, 1), (1, 2), (1, 3)],
[(0, 1), (1, 2), (3, 1)],
[(0, 1), (2, 1), (3, 1)],
[(1, 0), (1, 2), (1, 3)]]
</code></pre>
<p>$E_6$ orientations up to isomorphism:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: [g.edges(labels=False) for g in digraphs.nauty_directg(G, options='-o')]
[[(0, 1), (1, 2), (2, 3), (2, 5), (3, 4)],
[(0, 1), (1, 2), (2, 3), (2, 5), (4, 3)],
[(0, 1), (1, 2), (2, 3), (3, 4), (5, 2)],
[(0, 1), (1, 2), (2, 3), (4, 3), (5, 2)],
[(0, 1), (1, 2), (2, 5), (3, 2), (3, 4)],
[(0, 1), (1, 2), (2, 5), (3, 2), (4, 3)],
[(0, 1), (1, 2), (3, 2), (3, 4), (5, 2)],
[(0, 1), (1, 2), (3, 2), (4, 3), (5, 2)],
[(0, 1), (2, 1), (2, 3), (2, 5), (3, 4)],
[(0, 1), (2, 1), (2, 3), (2, 5), (4, 3)],
[(0, 1), (2, 1), (2, 3), (3, 4), (5, 2)],
[(0, 1), (2, 1), (2, 3), (4, 3), (5, 2)],
[(0, 1), (2, 1), (2, 5), (3, 2), (3, 4)],
[(0, 1), (2, 1), (3, 2), (3, 4), (5, 2)],
[(1, 0), (1, 2), (2, 3), (2, 5), (3, 4)],
[(1, 0), (1, 2), (2, 3), (3, 4), (5, 2)],
[(1, 0), (1, 2), (2, 5), (3, 2), (3, 4)],
[(1, 0), (1, 2), (3, 2), (3, 4), (5, 2)],
[(1, 0), (2, 1), (2, 3), (2, 5), (3, 4)],
[(1, 0), (2, 1), (2, 3), (3, 4), (5, 2)]]
</code></pre>
<p>Here's how you could quotient by your equivalence relation:</p>
<pre><code>def orientations_up_to_opposites(G):
results = []
for g in digraphs.nauty_directg(G, options='-o'):
g_canon = g.canonical_label()
g_opposite_canon = DiGraph([(b,a) for a,b in g.edges(labels=False)]).canonical_label()
if not (g_canon in results or g_opposite_canon in results):
results.append(g_canon)
return results
</code></pre>
<p>$D_4$ orientations up to isomorphism and opposites:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3,4]})
sage: [g.edges(labels=False) for g in orientations_up_to_opposites(G)]
[[(0, 3), (3, 1), (3, 2)], [(0, 3), (1, 3), (2, 3)]]
</code></pre>
<p>$E_6$ orientations up to isomorphism and opposites:</p>
<pre><code>sage: G = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: [g.edges(labels=False) for g in orientations_up_to_opposites(G)]
[[(0, 4), (3, 2), (4, 5), (5, 1), (5, 3)],
[(0, 5), (1, 3), (3, 4), (4, 2), (4, 5)],
[(0, 5), (1, 4), (2, 3), (3, 5), (5, 4)],
[(0, 4), (1, 3), (1, 5), (4, 5), (5, 2)],
[(0, 4), (1, 3), (3, 5), (4, 5), (5, 2)],
[(0, 5), (1, 4), (2, 3), (2, 5), (4, 5)],
[(0, 5), (1, 4), (2, 3), (3, 5), (4, 5)],
[(0, 5), (1, 4), (2, 3), (2, 4), (2, 5)],
[(0, 5), (1, 4), (2, 3), (3, 4), (3, 5)],
[(0, 5), (1, 3), (1, 4), (4, 2), (4, 5)]]
</code></pre>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62019#post-id-62019Thanks, this looks like a very elegant solution. Is there a trick to also obtain the directed graphs up to isomorphism and opposite orientation as in question 2?Sun, 17 Apr 2022 10:58:16 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62019#post-id-62019Answer by Emmanuel Charpentier for <p>Given an undirected finite connected graph (without loops).
I have two questions:</p>
<ol>
<li><p>Is there an easy way using Sage to obtain all ways to make it a directed graph (such that for each edge there is now one directed edge) up to isomorphism of graphs?</p></li>
<li><p>Is there an easy way using Sage to obtain all ways to make it a directed graph up to isomorphism of graphs and such that additionally the two opposite directed graphs get also identified?</p></li>
</ol>
<p>Interesting examples might be graphs of Dynkin type such as E_8.</p>
<p>For $A_3$ for example in the first question there are 3 ways to make it into a directed graph.
In the second question there are two ways for $A_3$.</p>
<p>So the input should be a undirected finite connected graph and the output all possible orientations up to graph isomorphisms (and maybe up to taking the opposite graph as in question 2).</p>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?answer=62008#post-id-62008Ignoring edge labels (what to do with them ?), weights (ditto) and possible loops, a crude brute-force approach is :
def directify(G):
# Finding all digraphs up to isomorphism for a given undirected
# graph using Sage.
# Returns the *set* of such digraphs.
# Left to the reader : managing loops and edge labels
# Left to the reader : checking G
Edges=[tuple(u[:2]) for u in G.edges()]
L=set()
for C in powerset(Edges):
l=[]
for e in Edges:
l+=[tuple([e[1], e[0]])] if e in C else [e]
c=DiGraph(l, immutable=True)
if any([c.is_isomorphic(u) for u in L]): break
L|=set([c])
return L
Micro-tests :
sage: [u.edges() for u in directify(Graph([(a, b), (a, c)]))]
[[(b, a, None), (c, a, None)], [(a, b, None), (c, a, None)]]
sage: [u.edges() for u in directify(Graph([(a, b), (a, c), (b, c)]))]
[[(b, a, None), (c, b, None), (c, a, None)]]
As all brute-force approaches, this is probably highly ameliorable...
HTH,Sat, 16 Apr 2022 22:31:19 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?answer=62008#post-id-62008Comment by klaaa for <p>Ignoring edge labels (what to do with them ?), weights (ditto) and possible loops, a crude brute-force approach is :</p>
<pre><code>def directify(G):
# Finding all digraphs up to isomorphism for a given undirected
# graph using Sage.
# Returns the *set* of such digraphs.
# Left to the reader : managing loops and edge labels
# Left to the reader : checking G
Edges=[tuple(u[:2]) for u in G.edges()]
L=set()
for C in powerset(Edges):
l=[]
for e in Edges:
l+=[tuple([e[1], e[0]])] if e in C else [e]
c=DiGraph(l, immutable=True)
if any([c.is_isomorphic(u) for u in L]): break
L|=set([c])
return L
</code></pre>
<p>Micro-tests :</p>
<pre><code>sage: [u.edges() for u in directify(Graph([(a, b), (a, c)]))]
[[(b, a, None), (c, a, None)], [(a, b, None), (c, a, None)]]
sage: [u.edges() for u in directify(Graph([(a, b), (a, c), (b, c)]))]
[[(b, a, None), (c, b, None), (c, a, None)]]
</code></pre>
<p>As all brute-force approaches, this is probably highly ameliorable...</p>
<p>HTH,</p>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62018#post-id-62018Thank you very much to both of you again. After the modification of rburing, it seems that it gives better results. At least for $D_4$ the result is now 4 which seems to be correct. For $E_6$ the number is now 20, does anyone know if that is correct ? My feeling is that it is correct.
And is there an easy modification of the code for question 2 so that two directed graphs get identified if they have opposite orientation?Sun, 17 Apr 2022 10:46:50 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62018#post-id-62018Comment by rburing for <p>Ignoring edge labels (what to do with them ?), weights (ditto) and possible loops, a crude brute-force approach is :</p>
<pre><code>def directify(G):
# Finding all digraphs up to isomorphism for a given undirected
# graph using Sage.
# Returns the *set* of such digraphs.
# Left to the reader : managing loops and edge labels
# Left to the reader : checking G
Edges=[tuple(u[:2]) for u in G.edges()]
L=set()
for C in powerset(Edges):
l=[]
for e in Edges:
l+=[tuple([e[1], e[0]])] if e in C else [e]
c=DiGraph(l, immutable=True)
if any([c.is_isomorphic(u) for u in L]): break
L|=set([c])
return L
</code></pre>
<p>Micro-tests :</p>
<pre><code>sage: [u.edges() for u in directify(Graph([(a, b), (a, c)]))]
[[(b, a, None), (c, a, None)], [(a, b, None), (c, a, None)]]
sage: [u.edges() for u in directify(Graph([(a, b), (a, c), (b, c)]))]
[[(b, a, None), (c, b, None), (c, a, None)]]
</code></pre>
<p>As all brute-force approaches, this is probably highly ameliorable...</p>
<p>HTH,</p>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62016#post-id-62016The `break` in the code should be `continue` instead.Sun, 17 Apr 2022 10:31:53 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62016#post-id-62016Comment by Emmanuel Charpentier for <p>Ignoring edge labels (what to do with them ?), weights (ditto) and possible loops, a crude brute-force approach is :</p>
<pre><code>def directify(G):
# Finding all digraphs up to isomorphism for a given undirected
# graph using Sage.
# Returns the *set* of such digraphs.
# Left to the reader : managing loops and edge labels
# Left to the reader : checking G
Edges=[tuple(u[:2]) for u in G.edges()]
L=set()
for C in powerset(Edges):
l=[]
for e in Edges:
l+=[tuple([e[1], e[0]])] if e in C else [e]
c=DiGraph(l, immutable=True)
if any([c.is_isomorphic(u) for u in L]): break
L|=set([c])
return L
</code></pre>
<p>Micro-tests :</p>
<pre><code>sage: [u.edges() for u in directify(Graph([(a, b), (a, c)]))]
[[(b, a, None), (c, a, None)], [(a, b, None), (c, a, None)]]
sage: [u.edges() for u in directify(Graph([(a, b), (a, c), (b, c)]))]
[[(b, a, None), (c, b, None), (c, a, None)]]
</code></pre>
<p>As all brute-force approaches, this is probably highly ameliorable...</p>
<p>HTH,</p>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62015#post-id-62015Your definition of "isomorphic" may not match Sage's definition embodied in `DiGraph.is_isomorphic()` :
sage: DiGraph([(0, 1), (1, 2), (2, 0)]).is_isomorphic(DiGraph([(1, 0), (2, 1), (0, 2)]))
TrueSun, 17 Apr 2022 10:11:20 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62015#post-id-62015Comment by klaaa for <p>Ignoring edge labels (what to do with them ?), weights (ditto) and possible loops, a crude brute-force approach is :</p>
<pre><code>def directify(G):
# Finding all digraphs up to isomorphism for a given undirected
# graph using Sage.
# Returns the *set* of such digraphs.
# Left to the reader : managing loops and edge labels
# Left to the reader : checking G
Edges=[tuple(u[:2]) for u in G.edges()]
L=set()
for C in powerset(Edges):
l=[]
for e in Edges:
l+=[tuple([e[1], e[0]])] if e in C else [e]
c=DiGraph(l, immutable=True)
if any([c.is_isomorphic(u) for u in L]): break
L|=set([c])
return L
</code></pre>
<p>Micro-tests :</p>
<pre><code>sage: [u.edges() for u in directify(Graph([(a, b), (a, c)]))]
[[(b, a, None), (c, a, None)], [(a, b, None), (c, a, None)]]
sage: [u.edges() for u in directify(Graph([(a, b), (a, c), (b, c)]))]
[[(b, a, None), (c, b, None), (c, a, None)]]
</code></pre>
<p>As all brute-force approaches, this is probably highly ameliorable...</p>
<p>HTH,</p>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62011#post-id-62011Another example: Dynkin type $D_4$:
d = {1: [2], 2: [3,4]}
There are 3 isomorphism types according to your code (I would think there are 4). It seems the directed graph where all arrows point away from 2 and the directed graph where all arrows point towards 2 are isomorphic according to your code, but I think this is not true, or do I have a big thinking error?Sat, 16 Apr 2022 23:15:12 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62011#post-id-62011Comment by klaaa for <p>Ignoring edge labels (what to do with them ?), weights (ditto) and possible loops, a crude brute-force approach is :</p>
<pre><code>def directify(G):
# Finding all digraphs up to isomorphism for a given undirected
# graph using Sage.
# Returns the *set* of such digraphs.
# Left to the reader : managing loops and edge labels
# Left to the reader : checking G
Edges=[tuple(u[:2]) for u in G.edges()]
L=set()
for C in powerset(Edges):
l=[]
for e in Edges:
l+=[tuple([e[1], e[0]])] if e in C else [e]
c=DiGraph(l, immutable=True)
if any([c.is_isomorphic(u) for u in L]): break
L|=set([c])
return L
</code></pre>
<p>Micro-tests :</p>
<pre><code>sage: [u.edges() for u in directify(Graph([(a, b), (a, c)]))]
[[(b, a, None), (c, a, None)], [(a, b, None), (c, a, None)]]
sage: [u.edges() for u in directify(Graph([(a, b), (a, c), (b, c)]))]
[[(b, a, None), (c, b, None), (c, a, None)]]
</code></pre>
<p>As all brute-force approaches, this is probably highly ameliorable...</p>
<p>HTH,</p>
https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62009#post-id-62009Thank you very much! I tested it for Dynkin type $E_6$ and the result is that there should be 7 isomorphism types using your code:
d = {1: [2], 2: [3], 3: [4,6], 4: [5]}
G = Graph(d); G
GG=directify(G)
GG2=list(GG)
display(GG2)
display(len(GG2))
Can this be really true? In all 7 cases the arrow points from 3 to 6, which makes me feel like that there are isomorphism types missing (you addressed the first case of the question, so that opposite isomorphism types do not get identified right?)Sat, 16 Apr 2022 22:44:37 +0200https://ask.sagemath.org/question/62006/finding-all-digraphs-up-to-isomorphism-for-a-given-undirected-graph-using-sage/?comment=62009#post-id-62009