Add interface to nauty-genbg (generator of bipartite graphs with given bipartition)

[maxale]

We add missing interface to nauty-genbg, a generator of bipartite graphs.

Nauty's genbg was already compiled and accessible but the interface was missing.

Depends on #33366

CC: @tscrim

Component: graph theory

Author: David Coudert

Branch: 695a667

Reviewer: Travis Scrimshaw

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

[dcoudert]

Commit: 804b062

[dcoudert]

Dependencies: #33366

[dcoudert]

New commits:

3603be3	Create bipartite graph from graph6 string
2175d09	Change Alist file check, Add docs
12a598c	Change alist file check
6d70523	Remove docstring newline
8090e50	trac #33365: merged #33366 with 9.6.beta7
804b062	trac #33365: add interface to nauty genbg

[dcoudert]

Description changed:

--- 
+++ 
@@ -1 +1,4 @@
-Sage provides interface to `nauty-geng` tool via `graph.nauty_geng()`, but interface for `nauty-genbg` tool is missing. 
+We add missing interface to `nauty-genbg`, a generator of bipartite graphs.
+
+Nauty's genbg was already compiled and accessible but the interface was missing. 
+

[dcoudert]

Branch: public/graphs/33365_genbg

[dcoudert]

Author: David Coudert

[maxale]

comment:3

I see that the resulting graphs are created via

         G = BipartiteGraph(s[:-1], format='graph6')

Please notice that graph6 format does not bear bipartition information, and the bipartition produced by BipartiteGraph() may be different from the requested one (via parameters n1 and n2), especially for non-connected ones, where multiple bipartitions may exist. I believe genbg produces the graph under assumption that left and right partite sets are formed by vertices (0..n1-1) and (n1..n1+n2-1), respectively. This needs to be enforced for the resulting graphs like:

         G = BipartiteGraph(s[:-1], format='graph6', partition=(set(0..n1-1),set(n1..n1+n2-1)))

I did not test this, but I hope the idea is clear.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e57e456

trac #33365: ensure that the partition respects the requirement

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 804b062 to e57e456

[dcoudert]

comment:5

You are right. Not easy when n1 and n2 are somewhere in the options string...

I'm not particularly proud of my solution of parsing the auxiliary output, but it's working for as long as the user don't pass option -q (which suppress the auxiliary output).

[dcoudert]

comment:6

green bot, please review.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:8

More of a nitpick: I think (-s, -a) and, e.g., ">M" should be code-formatted.

I agree that it is not that elegant, but it seems to work. If issues arise down the road, we can fix them then.

Whether or not you include my above nitpick, you can set a positive review on my behalf.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e57e456 to 695a667

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1e80907	trac #33365: Merged with 9.7.beta2
695a667	trac #33365: formatting

[dcoudert]

comment:10

I'm not sure to understand what you asked for... I changed to (``-s``, ``-a``).

I prefer to avoid mentioning ">M". It can effectively be used to count graphs, but it's not documented and does not even appear in the source code of genbg.

[dcoudert]

comment:11

As proposed, I set this ticket to positive review.

Thanks.

[tscrim]

comment:12

Replying to @dcoudert:

I'm not sure to understand what you asked for... I changed to (``-s``, ``-a``).

Yes, that’s right: code formatting is ``.

I prefer to avoid mentioning ">M". It can effectively be used to count graphs, but it's not documented and does not even appear in the source code of genbg.

Those kind of things were included in the doc though. Anyways, not so important.

Thank you.

[vbraun]

Changed branch from public/graphs/33365_genbg to 695a667

[maxale]

Changed commit from 695a667 to none

[maxale]

comment:14

Please notice that nauty-genbg has the following restrictions on n1 and n2:

$ nauty-genbg 5 28
>E genbg: must have n1=1..24, n1+n2=1..32

Should these restrictions be checked by the interface and an appropriate error be raised?

[dcoudert]

comment:15

Yes, and these restrictions should be properly documented. Can you open a ticket ?

[maxale]

comment:16

Added as ticket #34179.