Interface nauty's directg command with sage

[vinklein]

Allow to call nauty's directg command from sage.

This is implemented as a DiGraph generator (file: digraph_generators.py).

Note to reviewers: Any idea for useful examples in documentation is welcome.

CC: @dcoudert @videlec

Component: graph theory

Keywords: thursdaysbdx

Author: Vincent Klein

Branch: ccc2cd3

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/27231

[vinklein]

Branch: u/vklein/27231

[vinklein]

Commit: a538ebc

[vinklein]

New commits:

a538ebc

Trac #27231: Add a digraph generator using ...

[sagetrac-git]

Changed commit from a538ebc to 90b6be7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

90b6be7

Trac #27231: Add a digraph generator using ...

[dcoudert]

comment:5

This is a nice addition. Thank you. Below are some comments.

• You are not returning a list but an iterator.

-        Returns a list which creates digraphs from nauty's directg program.
+        Return an iterator yielding digraphs using nauty's ``directg`` program.

• Could you document the role of parameter graphs. It is not completely obvious.

-        - ``graphs`` (iterable) -- A :class:`Graph` or an iterable containing
-          :class:`Graph`.
+        - ``graphs`` -- a :class:`Graph` or an iterable containing :class:`Graph`

• Also, add an empty line between parameters.

• As for graphs.nauty_geng, you could add parameter debug.

• I don't know which is best between the loop for l in out.split('\n'): and the while loop of graphs.nauty_geng. Are the programs different ?

-            if l != '' and l[0] == '&':
+            if l and l[0] == '&':

• Have you tried watercluster2 ? according to the documentation of nauty http://pallini.di.uniroma1.it/nug26.pdf, it is a faster alternative to directg.

• directg and watercluster2 generate all possible orientations of the input graphs, include both directions. Currently, we have a tools for iterating over all possible orientations of a graph:

  • orientations return an iterator over orientations
  • strong_orientations_iterator return an iterator over all strong orientations of a graph G
    You can add a test to show that 1) directg/watercluster2 generates more graphs than what we get with orientations, and 2) that each digraph obtained with orientations is in the set of digraphs obtained with directg.

[vinklein]

comment:6

Replying to @dcoudert:

This is a nice addition. Thank you. Below are some comments.

• You are not returning a list but an iterator.

-        Returns a list which creates digraphs from nauty's directg program.
+        Return an iterator yielding digraphs using nauty's ``directg`` program.

Yes my mistake ! It's a generator to be accurate. My first version used to return a list.

Thanks for noticing that.

• I don't know which is best between the loop for l in out.split('\n'): and the while loop of graphs.nauty_geng. Are the programs different ?

The impacting difference between geng and directg is that directg need an input file and geng work with command parameter only.

That's why i use Popen.communicate as it allow to give an input "file" to directg

The drawback is, if i am right, that with communicate reading stdout is in one go where we can read line by line for geng. I will try a line by line read with the communicate output, just in case i am wrong.

• Have you tried watercluster2 ? according to the documentation of nauty http://pallini.di.uniroma1.it/nug26.pdf, it is a faster alternative to directg.

No i was unaware of that.
I implemented this ticket for a sage user needing directg. I will look at watercluster2 and modify my ticket with it if it works well.

Thanks for your comments.

[vinklein]

comment:8

Comparison watercluster2 and directg

1 - For generating/counting digraph without generating output watercluster2 is way faster.

(sage-sh) vklein@tuono:sage$ time geng -c 7 | directg -o -u
>A geng -cd1D6 n=7 e=6-21
>Z 853 graphs generated in 0.00 sec
>A directg -ou
>Z 853 graphs read from stdin; 2120098 digraphs generated; 1.71 sec

real    0m1.734s
user    0m1.716s
sys 0m0.000s
(sage-sh) vklein@tuono:sage$ time geng -c 7 | watercluster2 S
>A geng -cd1D6 n=7 e=6-21
>Z 853 graphs generated in 0.00 sec
Number of directed graphs: 2120098 

real    0m0.233s
user    0m0.234s
sys 0m0.000s

If you take the time to generate output into account the result is less clear.

watercluster2 has two output format T-code (option T) or a custom binary format (option B).

For the tests below the two functions used just read the command output.

sage: time out = digraphs.nauty_watercluster2(graphs.nauty_geng("-c 9 9:12"), op
....: tions="B S")
CPU times: user 2.42 s, sys: 571 ms, total: 2.99 s
Wall time: 7.12 s
sage: time out = digraphs.nauty_watercluster2(graphs.nauty_geng("-c 9 9:12"), op
....: tions="T S")
CPU times: user 5.65 s, sys: 1.9 s, total: 7.55 s
Wall time: 33.9 s
sage: time out = digraphs.nauty_directg(graphs.nauty_geng("-c 9 9:12"), options=
....: "-o")
CPU times: user 2.02 s, sys: 591 ms, total: 2.61 s
Wall time: 10.3 s

watercluster2 is slower than directg with T-code output and slightly faster with binary output.

My current problem with the binary output is that what i get is not consistent with the specifications (Which are in watercluster2 source code) and therefore i don't know how to build DiGraph with that.

2 - Command options.

directg and watercluster2 have options with no equivalent :

directg's options:

   -e# | -e#:#  specify a value or range of the total number of arcs
   -f#  Use only the subgroup that fixes the first # vertices setwise
    -s#/#  Make only a fraction of the orientations: The first integer is
            the part number (first is 0) and the second is the number of
            parts. Splitting is done per input graph independently.

watercluster2's options:

The option ix restricts the maximum indegree to x.
The option oy restricts the maximum outdegree to y.

I don't know what is the most useful set of options between these two.

I guess we should stick with directg for now.

[dcoudert]

comment:9

Thanks for the benchmark.

I agree to stay with directg. You can add a .. TODO::`` block explaining that a future task is to interface watercluster2`.

Also, can you do

-                yield DiGraph(l[1:])
+                yield DiGraph(l[1:], format='dig6')

and add tests like if not graphs: ..., if not input: ..., if not g: ... to avoid computations when the input graph/list of graphs is empty.

[vinklein]

comment:10

Replying to @dcoudert:

You can add a test to show that 1) directg/watercluster2 generates more graphs than what we get with orientations, and 2) that each digraph obtained with orientations is in the set of digraphs obtained with directg.

Well my results are :

sage: len(list(digraphs.nauty_directg(graphs.PetersenGraph())))
121545
sage: len(list(graphs.PetersenGraph().orientations()))
32768
sage: K5 = graphs.CompleteGraph(5)
sage: len(list(digraphs.nauty_directg(K5)))
582
sage: len(list(K5.orientations()))
1024

For K5 directg give me less digraphs than orientations. Is it an inconsistency ?

[sagetrac-git]

Changed commit from 90b6be7 to 8080a06

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

8080a06

Trac #27231: Implement reviewer's comments:

[vinklein]

comment:12

Reviewer's comments implemented apart from comparison with orientations's set (see comment:10).

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ada4dcb

Trac #27231: add nauty_directg method ...

[sagetrac-git]

Changed commit from 8080a06 to ada4dcb

[dcoudert]

comment:15

• Missing empty line

-        Return an iterator yielding digraphs using nauty's ``directg`` program.
-        Description from directg --help:
+        Return an iterator yielding digraphs using nauty's ``directg`` program.
+
+        Description from directg --help:

• One small details for the test if not graphs:. If graphs = Graph(), then the test will be true and nothing is returned. If it is what you expect, this is fine. But if you expect that the method return DiGraph(), then an extra test like if isinstance(graphs, Graph):... is needed. I let you decide which is best.

• Concerning the test with `orientations, I plotted graphs generated with a smaller example

sage: sum(1 for _ in digraphs.nauty_directg(graphs.CompleteGraph(3)))
7
sage: sum(1 for _ in graphs.CompleteGraph(3).orientations())
8
sage: for d in digraphs.nauty_directg(graphs.CompleteGraph(3)):
....:     d.show()
sage: for d in graphs.CompleteGraph(3).orientations():
....:     d.show()

It appears that the digraphs generated with directg are non-isomorphic orientations of the graph, while orientations generates isomorphic digraphs. For instance [(0, 1), (0, 2), (1, 2)] and [(1, 0), (2, 0), (2, 1)] are different digraphs obtained with orientations but are isomorphic, so only the first one is produced by directg.
So the test I proposed is not relevant.

However, you could add a .. SEEALSO: block with pointers to orientations and strong_orientations.

• I have successfully tested this ticket with Python3 ;)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4846590

Trac #27231: support single input of empty Graph

[sagetrac-git]

Changed commit from ada4dcb to 4846590

[vinklein]

comment:17

All comments implemented.

The case with graphs == Graph() was really a bug because directg manage the input of empty graphs (graph6 string ?) and return an empty digraph.

Note that to stick with this generator description i prefer to let directg do this job rather than doing a yield DiGraph() manually.

Thank you for your comments.

[sagetrac-git]

Changed commit from 4846590 to 9289f5f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9289f5f

Trac #27231: support single input of empty Graph

[dcoudert]

comment:19

Some more comments (should be the last one)

• To be consistent, you must change in the top table:

-    :meth:`~DiGraphGenerators.nauty_directg`       | Returns a digraph generator using Nauty's directg command.
+    :meth:`~DiGraphGenerators.nauty_directg`       | Return an iterator yielding digraphs using nauty's ``directg`` program.

• In the tests, I don't understand why the error is raised only after next(g) and not directly during the call to digraphs.nauty_directg. Is it normal ?

• may be you should do the test on not graphs after the tests on input parameters ? Otherwise, a call to digraphs.nauty_directg([], options="-o -G") will not raise an error.

• 80 column mode for comments

-            # digraph6 specifications: http://users.cecs.anu.edu.au/~bdm/data/formats.txt
+            # digraph6 specifications: 
+            # http://users.cecs.anu.edu.au/~bdm/data/formats.txt

[vinklein]

comment:20

Replying to @dcoudert:

Some more comments (should be the last one)

• In the tests, I don't understand why the error is raised only after next(g) and not directly during the call to digraphs.nauty_directg. Is it normal ?

Yes that's how python's generators works. Calling the generator's function create the generator object but don't begin to execute the code inside the function:

>>> def generator():
	print('hey')
	yield 1

	
>>> g = generator()
>>> g
<generator object generator at 0x00000198B7D22CF0>
>>> next(g)
hey
1

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:21

I didn't know that. Thanks.

So you just have to include my last comments.

[sagetrac-git]

Changed commit from 9289f5f to ccc2cd3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1969a6a	Trac #27231: Add a digraph generator using ...
7f94176	Trac #27231: Implement reviewer's comments:
8e302c6	Trac #27231: add nauty_directg method ...
18d1ea3	Trac #27231: support single input of empty Graph
ccc2cd3	Trac #27231: Implements last reviewer's comments

[vinklein]

comment:23

Rebase on sage8.7.beta3 and implement last reviewer's comments.

[dcoudert]

comment:24

LGTM. Tested on py2 and py3.

[vbraun]

Changed branch from u/vklein/27231 to ccc2cd3

[slel]

comment:26

Thanks. There is user demand for this, see

• Ask Sage question 46220.

Follow-up ticket at #27686 for a documentation issue raised in that Ask Sage question.

[slel]

Changed commit from ccc2cd3 to none