Support for digraph6 format?

[Jihoon Seo]

Hi

I generated some directed graphs using `geng` and `directg`, the utilities included in Nauty.

./geng 5 | ./directg

The generated graphs look like:

&D?????
&DA????
&DA??G?
&DAC???
&DA??C?
&D???K?
&DAC?G?
&DA??K?
&DAC?K?
&DACG??

And here is the description of `digraph6` format (from Nauty user's guide)

------------------------------

Data type:
simple directed graphs (allowing loops) of order 0 to 68719476735.
Optional Header:
>>digraph6<< (without end of line!)
File name extension:
.d6
One graph:
Suppose G has n vertices. Write the adjacency matrix of G
as a bit vector x of length n^2, row by row.
Then the graph is represented as '&' N(n) R(x).
The character '&' (decimal 38) appears as the first character.
Example:
Suppose n=5 and G has edges 0->2, 0->4, 3->1 and 3->4.
x = 00101 00000 00000 01001 00000
Then N(n) = 68 and
R(x) = R(00101 00000 00000 01001 00000) = 73 63 65 79 63.
So, the graph is 38 68 73 63 65 79 63.

But when I run this line in Sage:

G1 = Graph('&D?????')

Sage returns error:

RuntimeError: The string seems corrupt: valid characters are 
?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

How can I generate a directed graph object with `digraph6` format string, or some other format?

e.g. directg -T : use a simple text output format (nv ne edges) instead of digraph6

./geng 5 | ./directg -T

5 0
5 1 0 4
5 2 0 4 4 0
5 2 0 4 1 4
5 2 0 4 4 1
5 2 4 0 4 1
5 3 0 4 4 0 1 4
5 3 0 4 4 0 4 1
5 4 0 4 4 0 1 4 4 1
5 3 0 4 1 4 2 4

e.g. directg -G : like -T but includes group size as third item (if less than 10^10)

The group size does not include exchange of isolated vertices.

./geng 5 | ./directg -G
5 0 1
5 1 1 0 4
5 2 2 0 4 4 0
5 2 2 0 4 1 4
5 2 1 0 4 4 1
5 2 2 4 0 4 1
5 3 1 0 4 4 0 1 4
5 3 1 0 4 4 0 4 1
5 4 2 0 4 4 0 1 4 4 1
5 3 6 0 4 1 4 2 4

[Dima Pasechnik]

so & needs to be skipped.

 

Example:
Suppose n=5 and G has edges 0->2, 0->4, 3->1 and 3->4.
x = 00101 00000 00000 01001 00000
Then N(n) = 68 and
R(x) = R(00101 00000 00000 01001 00000) = 73 63 65 79 63.
So, the graph is 38 68 73 63 65 79 63.

But when I run this line in Sage:

G1 = Graph('&D?????')

try skipping &, and also you are making directed graphs (DiGraph in Sage)

G1 = DiGraph('D?????')

this seems to work.

[leif]

Dima Pasechnik wrote:
> On Tuesday, September 6, 2016 at 9:29:33 AM UTC, Jihoon Seo wrote:
> I generated some directed graphs using `geng` and `directg`, the

> utilities included in Nauty <http://pallini.di.uniroma1.it/>.

>
> ./geng 5 | ./directg
>
>
> The generated graphs look like:
>
> &D?????
> &DA????
> &DA??G?
> &DAC???
> &DA??C?
> &D???K?
> &DAC?G?
> &DA??K?
> &DAC?K?
> &DACG??
>
>
> And here is the description of `digraph6` format (from Nauty user's

> guide <http://pallini.di.uniroma1.it/nug26.pdf>)

> ------------------------------
>
> Data type:
> simple directed graphs (allowing loops) of order 0 to 68719476735.
> Optional Header:
> >>digraph6<< (without end of line!)
> File name extension:
> .d6
> One graph:
> Suppose G has n vertices. Write the adjacency matrix of G
> as a bit vector x of length n^2, row by row.
> Then the graph is represented as '&' N(n) R(x).
> The character '&' (decimal 38) appears as the first character.
>
>
> so & needs to be skipped.
>
>
> Example:
> Suppose n=5 and G has edges 0->2, 0->4, 3->1 and 3->4.
> x = 00101 00000 00000 01001 00000
> Then N(n) = 68 and
> R(x) = R(00101 00000 00000 01001 00000) = 73 63 65 79 63.
> So, the graph is 38 68 73 63 65 79 63.
>
>
> But when I run this line in Sage:
>
> G1 = Graph('&D?????')
>
>
> try skipping &, and also you are making directed graphs (DiGraph in Sage)

Looks like we missed some format changes when upgrading nauty; the code
in Sage partially dates back to 2007 (with only minor changes around
2014, and early 2015).

If skipping the ampersand is really enough (we still may want to change
*outputting* dig6 strings as well, probably with an optional parameter
for backwards compatibility), the patch is trivial:


--- a/src/sage/graphs/graph_input.py
+++ b/src/sage/graphs/graph_input.py
@@ -138,7 +140,7 @@ def from_dig6(G, dig6_string):
if n == -1:
n = len(dig6_string)
ss = dig6_string[:n]
- n, s = length_and_string_from_graph6(ss)
+ n, s = length_and_string_from_graph6(ss[1:] if ss[0]=='&' else ss)
m = binary_string_from_dig6(s, n)
expected = n**2
if len(m) > expected:


-leif

[Jihoon Seo]

Thank you. It works.

2016년 9월 6일 화요일 오후 10시 0분 1초 UTC+9, Dima Pasechnik 님의 말: