3
$\begingroup$

There seems to be a bug in Export for the "Sparse6" graph format, when the graph to be exported is a multigraph (i.e. has repeated edges). For example, take

g = Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 2}];

Then

ExportString[g, "Sparse6"]
(*">>sparse6<<:Ab~"*)

which only looks OK, because it cannot be imported back

ImportString[%, "Sparse6"]
(*$Failed*)

Notice that the bug is within Export and not Import, because the output produced by Mathematica is also not accepted by nauty programs (created by the same guy who defined the "Sparse6" format in the first place).

Any idea how one could access Mathematica's implementation of Export, to maybe correct this bug? The "Sparse6" format itself is simple enough for me to try to write a crude exporter myself (I realize I can just avoid using Export, but I'd like to make this as transparent a fix as possible)

$\endgroup$
9
  • $\begingroup$ I have a Sparse6 importer in my IGraph/M package and I would be happy to take a contribution for an exporter. $\endgroup$
    – Szabolcs
    Dec 7 '21 at 9:02
  • $\begingroup$ I don't have time to look into this now, but I'll note that my importer handles this fine. IGImportString[">>sparse6<<:Ab~", "Nauty"]. You can use IGraph/M to import it. Are you sure the representation is incorrect? Can you give an example where the nauty suite does not accept this yet it is expected to handle multigraphs? Link to format spec is here: users.cecs.anu.edu.au/~bdm/data/formats.html $\endgroup$
    – Szabolcs
    Dec 7 '21 at 9:05
  • $\begingroup$ I looked carefully at this representation, and I cannot tell what would be wrong with it, although I can see that listg -e does not produce the output we would expect. The first character, A, represents the number of vertices, ToCharacterCode["A"] - 63 == 2. This is fine. Then the sequence of b and x values is b=1, x=0, b=0, x=1 followed by all 1s. This induces the edge list (1,0) (1,0) which is correct. $\endgroup$
    – Szabolcs
    Dec 7 '21 at 14:58
  • $\begingroup$ What seems to be incorrect is the padding, i.e. the ~ character at the end. This seems to be unnecessary, but I don't quite see why it would be harmful. If you have further doubts about the correctness, I suggest writing to the nauty mailing list and asking Brendan. $\endgroup$
    – Szabolcs
    Dec 7 '21 at 15:03
  • $\begingroup$ Regarding the use of the bugs tag, please do not use this tag on your own questions. See the tag description for why. Please do help with adding this tag to others' questions when the issue has been confirmed to be a bug by the community. $\endgroup$
    – Szabolcs
    Dec 7 '21 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.