Implement digraphs()

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Currently graphs() is an iterator that can be used to find an example of the smallest cardinality of a graph with given properties. It is unlogical that the same does not work for directed graphs.

There was no copy parameter for digraph generation. I added it and also made it a default, just like undirected graph generation already have. It is safer this way.

Also there was wrong indentation in the docstring.

CC: @dcoudert

Component: graph theory

Author: Jori Mäntysalo

Branch/Commit: 4a0bcbc

Reviewer: David Coudert

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

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Branch: u/jmantysalo/all-digraphs

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Description changed:

--- 
+++ 
@@ -1,3 +1,6 @@
-Currently `graphs()` is an iterator that can be used to found an example of the smallest cardinality of a graph with given properties.
+Currently `graphs()` is an iterator that can be used to find an example of the smallest cardinality of a graph with given properties. It is unlogical that the same does not work for directed graphs.

-It is unlogical that the same does not work for directed graphs.
+There was no `copy` parameter for digraph generation. I added it and also made it a default, just like undirected graph generation already have. It is safer this way.
+
+Also there was wrong indentation in the docstring.
+

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Author: Jori Mäntysalo

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Commit: 4a0bcbc

[f29946bc-ee7b-48cd-9abc-3445948c551d]

New commits:

4a0bcbc

Add digraphs() (without parameters) etc.

[dcoudert]

comment:3

What you did is correct and more than useful. Thanks. However, the generator is not working as expected. For instance:

sage: for d in digraphs(4, property=lambda x:x.is_strongly_connected()):
....:     print d.order(),d.edges()
....:     
sage: 

Also, the documentation of the canaug_traverse_vert and canaug_traverse_edge methods in graph_generators.py must be updated (many input parameters are not documented). You could do it in this patch.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:4

"If for any graph G satisfying the property, every subgraph, obtained from G by deleting one edge - -", says the documentation. That is, the generation works only for "hereditary" properties.

This is actually somewhat complicated area. An example:

Every graph can be dismantled by removing one vertex a time until the single vertex graph is left, so every graph can be built by adding one vertex a time. Now let's suppose you optimize and only add vertex i if the degree of it is at least the degree of vertex i-1. It works, but if you generate connected graphs, it wont, as there is one 6-vertex graph that will not be generated.

The input for canaug_traverse_* seems frightening... Not sure if I can handle it yet.

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:5

There are solution à la graphs.nauty_geng that can be used. On the webpage of nauty, http://pallini.di.uniroma1.it/, the user's guide indicate that directg generates small digraphs with given underlying graph, and that watercluster2 is a faster alternative to directg written by Gunnar Brinkmann. We might use such implementation do generate digraphs with non hereditary properties (nauty_geng can generate biconnected graphs). Of course, this is for another ticket.

I also propose to let the improvement of the documentations of canaug_traverse_* for another ticket.

Since the patch passes all tests and that the documentation is nicer, I give positive review.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:6

Replying to @dcoudert:

There are solution à la graphs.nauty_geng that can be used. On the webpage of nauty, http://pallini.di.uniroma1.it/, the user's guide indicate that directg generates small digraphs with given underlying graph, and that watercluster2 is a faster alternative to directg written by Gunnar Brinkmann. We might use such implementation do generate digraphs with non hereditary properties (nauty_geng can generate biconnected graphs).

Interesting. Can you summarize the main idea behind them? Orderly generation needs hereditary property by definition, but there may be other ways to do the augmentation. Adding a cycle when generating Eulerian graphs?

Since the patch passes all tests and that the documentation is nicer, I give positive review.

OK. Did you intend to do it already, or are you running tests?

[dcoudert]

comment:7

Interesting. Can you summarize the main idea behind them? Orderly generation needs hereditary property by definition, but there may be other ways to do the augmentation. Adding a cycle when generating Eulerian graphs?

I don't know how it's working.

Since the patch passes all tests and that the documentation is nicer, I give positive review.

OK. Did you intend to do it already, or are you running tests?

I have compiled the code, run tests, build doc and display the html.

[dcoudert]

comment:8

... and forgot to click the right button.

[vbraun]

Changed branch from u/jmantysalo/all-digraphs to 4a0bcbc