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.Sun, 21 Jul 2024 15:24:19 +0200The canonical labels in SageMath are different from those in nauty.https://ask.sagemath.org/question/78357/the-canonical-labels-in-sagemath-are-different-from-those-in-nauty/Here are the canonical labels obtained from SageMath:
sage: g=Graph('E{EG').canonical_label()
sage: for vertex in g.vertices():
....: neighbors = g.neighbors(vertex)
....: print(f"Vertex {vertex}: {neighbors}")
Vertex 5: [1, 2, 3, 4]
Vertex 1: [5, 2]
Vertex 2: [5, 1]
Vertex 3: [5, 0]
Vertex 0: [3, 4]
Vertex 4: [5, 0]
However, for the same graph, the canonical labels I obtained using [nauty](https://www.mankier.com/1/nauty-labelg) are as follows.
echo 'E{EG' |labelg |showg
Graph 1, order 6.
0 : 4 5;
1 : 4 5;
2 : 3 5;
3 : 2 5;
4 : 0 1;
5 : 0 1 2 3;
As we see, the canonical labels in SageMath are different from those in nauty. Consequently, the graph6 strings they produce are also different.
Nauty: E@ro (by running `echo 'E{EG' |labelg`)
Sage: EK\`w (by running `Graph('E{EG').canonical_label().graph6_string()`)
Is it a bug? I would like to ask if there is a command in SageMath to make it consistent with the software nauty .Sun, 21 Jul 2024 14:18:50 +0200https://ask.sagemath.org/question/78357/the-canonical-labels-in-sagemath-are-different-from-those-in-nauty/Answer by rburing for <p>Here are the canonical labels obtained from SageMath:</p>
<pre><code> sage: g=Graph('E{EG').canonical_label()
sage: for vertex in g.vertices():
....: neighbors = g.neighbors(vertex)
....: print(f"Vertex {vertex}: {neighbors}")
Vertex 5: [1, 2, 3, 4]
Vertex 1: [5, 2]
Vertex 2: [5, 1]
Vertex 3: [5, 0]
Vertex 0: [3, 4]
Vertex 4: [5, 0]
</code></pre>
<p>However, for the same graph, the canonical labels I obtained using <a href="https://www.mankier.com/1/nauty-labelg">nauty</a> are as follows. </p>
<pre><code>echo 'E{EG' |labelg |showg
Graph 1, order 6.
0 : 4 5;
1 : 4 5;
2 : 3 5;
3 : 2 5;
4 : 0 1;
5 : 0 1 2 3;
</code></pre>
<p>As we see, the canonical labels in SageMath are different from those in nauty. Consequently, the graph6 strings they produce are also different. </p>
<p>Nauty: E@ro (by running <code>echo 'E{EG' |labelg</code>)</p>
<p>Sage: EK`w (by running <code>Graph('E{EG').canonical_label().graph6_string()</code>)</p>
<p>Is it a bug? I would like to ask if there is a command in SageMath to make it consistent with the software nauty .</p>
https://ask.sagemath.org/question/78357/the-canonical-labels-in-sagemath-are-different-from-those-in-nauty/?answer=78361#post-id-78361Yes they are different, the [documentation of `canonical_label`](https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.canonical_label) states that it takes an `algorithm` parameter, and the default is to use `bliss` if it is available. There is no `nauty` option because SageMath currently has only a very limited integration of nauty, only using some of its executables to generate graphs.
Relevant:
- [Issue 30271: nauty: Switch to autotoolized fork so that shared libraries can be built](https://github.com/sagemath/sage/issues/30271)
- [Issue 25506: Nauty interface for isomorphism checking and automorphism group computing](https://github.com/sagemath/sage/issues/25506)
Here is a workaround, using the `labelg` executable (assuming SageMath has `nauty` installed):
def nauty_canonical_label(g):
from sage.env import SAGE_NAUTY_BINS_PREFIX
import subprocess
labelg = subprocess.run([SAGE_NAUTY_BINS_PREFIX + 'labelg', '-q'], input=g.graph6_string(), encoding='ascii', capture_output=True)
return labelg.stdout.strip()
Example:
sage: nauty_canonical_label(Graph('E{EG'))
'E@ro'Sun, 21 Jul 2024 15:24:19 +0200https://ask.sagemath.org/question/78357/the-canonical-labels-in-sagemath-are-different-from-those-in-nauty/?answer=78361#post-id-78361