Graph6 string fails to be read in

[mtorpey]

@james-d-mitchell mentioned a problem in Issue #158. I now think it's unrelated to that issue, but it's definitely worth investigating.

He recently tried inputting the graph at:

https://math.stackexchange.com/questions/1561029/a-triangle-free-6-chromatic-graph-with-44-vertices

which claims to be in graph6 format but gives the error:

Error, Digraphs: DigraphFromGraph6String: usage,
the input string <s> is not in valid graph6 format, at /Users/jdm/gap/pkg/digraphs/gap/io.gi:780 called from
<function "unknown">( <arguments> )
 called from read-eval loop at *stdin*:48
type 'quit;' to quit to outer loop

when he tries to read it into Digraphs.

I should be able to have a look at this next Wednesday, if not before.

[mtorpey]

The string in question is

khdLA_gc?N_QQchPIS@Q_dH@GKA_W@OW?Fo???~{G??SgSoSgSQISIaQcQgD?\@?SASI?gGggC_[`??N_M??APNG?Qc?E?DIG?_?IS?B??IS?E??dH?C??H@_B??A_W?o??IB?E???Fo?O????F~O??????N~~{

The 62nd character is a backslash \ which needs to be escaped when entered into GAP. If I try running

gap> str := Concatenation("khdLA_gc?N_QQchPIS@Q_dH@GKA_W@OW?Fo???~{G??SgSoSgSQ",
                          "ISIaQcQgD?\@?SASI?gGggC_[`??N_M??APNG?Qc?E?DIG?_?IS",
                          "?B??IS?E??dH?C??H@_B??A_W?o??IB?E???Fo?O????F~O????",
                          "??N~~{");;
gap> gr := DigraphFromGraph6String(str);

then I get the same problem as James. But if I run

gap> str := Concatenation("""khdLA_gc?N_QQchPIS@Q_dH@GKA_W@OW?Fo???~{G??SgSoSgSQ""",
                          """ISIaQcQgD?\@?SASI?gGggC_[`??N_M??APNG?Qc?E?DIG?_?IS""",
                          """?B??IS?E??dH?C??H@_B??A_W?o??IB?E???Fo?O????F~O????""",
                          """??N~~{""");;
gap> gr := DigraphFromGraph6String(str);

using the """literal string""" notation, then it reads in fine, and I even get

gap> ChromaticNumber(gr);
6

as the article in question suggests.

If we read a file using ReadDigraphs, there's similarly no problem.

I've added this whole thing to test-extreme in 2c69052, since it seems a nice use of ChromaticNumber - it takes about one second.

[wilfwilson]

Thanks @mtorpey. Is there anything we can do to make this more robust in the future? Does that mean reading in (normally) any string produced by Graph6String or whatever that happens to contain \ will cause problems? Or is it not a problem?

[ChrisJefferson]

Can \ appear anywhere, or just before @? In the past we've discussed stopping gap treating things like (for example) "\q" as "q", but it turns out some packages have written things like this (accidentally) and would get broken if we changed it.

[mtorpey]

In my opinion, this package shouldn't worry about this – if the user manages to create the correct string in GAP, then the algorithms in the package work on that string just fine. Probably most of the time we're reading and writing files anyway, in which this issue doesn't arise at all.

In general, we might debate the way GAP should read strings between " signs, but I can't think of a solution that would fix this problem. A \ symbol could appear essentially anywhere in a graph6 string, and could easily be followed by an n or an r or any other character that might have a special meaning, so I can't see a sensible way to avoid this. In any case, users still have the option of """literal strings""" or reading from a file, both of which are foolproof with regards to this issue.

The most I might suggest would be adding a message somewhere in our doc pointing out that graph6 strings can include backslashes and to be careful typing them in – but I wonder how much use this would be.

[wilfwilson]

@mtorpey Thanks for the answer, I agree with you.