Random regular bipartite graph generator and bipartite graph embeddings

[dcoudert]

Add a generator of random regular bipartite graph, RandomRegularBipartite.

This ticket also unifies the graph embedding method of CompleteBipartiteGraph, RandomRegularBipartite and RandomBipartite by using method _line_embedding from graph_plot.py.

Component: graph theory

Author: David Coudert

Branch/Commit: 5c7a97d

Reviewer: Bryan Gin-ge Chen

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

[dcoudert]

Branch: public/25403_random_regular_bipartite

[dcoudert]

Commit: f7b6ed0

[dcoudert]

New commits:

6425d02	trac #25403: generator of random regular bipartite graphs
f7b6ed0	trac #25403: fix small bug in RandomBipartite with a side of cardinality 1

[b0bf1a7b-bfe9-44fe-8236-57b33990cc18]

comment:2

Hello, this is my first attempt to review a patch... feel free to let me know if any of these suggestions are inappropriate or out of scope!

First, am I correct that RandomRegularBipartite does not sample uniformly from the set of random regular bipartite graphs with the given sizes and degrees? If this is the case, then the documentation for this function should make it more clear what the sampled distribution is.

Second, would you mind adding documentation (and possibly tests) for the position dictionaries generated by RandomBipartite and RandomRegularBipartite?

I also noticed that the only other random graph generator which assigns positions is RandomTriangulation and it only does so if the parameter set_position is explicitly set to True. Should these two functions thus also be given a set_position parameter for consistency?

Finally, the name given to the graph generated by RandomRegularBipartite could be made more informative, perhaps something like:

name="Random regular bipartite graph of size {}+{} with degrees {} and {}".format(n1, n2, d1, d2)

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

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

1d30ff1	trac #25403: Merged with 8.3.rc2
06090ba	trac #25403: implement reviewers comments

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

Changed commit from f7b6ed0 to 06090ba

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

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

9ae579f

trac #25403: more comments

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

Changed commit from 06090ba to 9ae579f

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

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

9ef139e

trac #25403: add parameter set_position

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

Changed commit from 9ae579f to 9ef139e

[dcoudert]

comment:6

Thank you for reviewing this ticket. It helps a lot.

I have implemented all your comments. For RandomTriangulation, the time to compute the positions of vertices is non negligible (planar embedding). Here, it's quite cheap, but I agree that in many cases we don't need it.

Don't forget to put your real name in the field "Reviewers"

[b0bf1a7b-bfe9-44fe-8236-57b33990cc18]

comment:7

Thanks for making the changes! It seems however there is some issue with the tests. After checking out your branch and building, sage -t src/sage/graphs/generators/random.py fails with a timeout. It seems the culprit is:

sage: graphs.RandomRegularBipartite(2, 3, 3, set_position=True).get_pos() ## line 318 ##

This particular graph must be complete bipartite, so perhaps there is some issue when generating these. In the complete bipartite case (d1 == n2) maybe the edge generation should just be made deterministic.

Finally, it would probably be more helpful to users if the coordinates of the positions were included in the docstring in addition to the code comments.

[b0bf1a7b-bfe9-44fe-8236-57b33990cc18]

Reviewer: Bryan Gin-ge Chen

[dcoudert]

comment:9

It's more complicated than that. If found other situations like graphs.RandomRegularBipartite(6, 6, 5, set_position=True) that can loop endlessly :( So we need another, more secured, algorithms...

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

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

8000a65

trac #25403: improved algorithm

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

Changed commit from 9ef139e to 8000a65

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

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

3266bc8	trac #25403: Merged with 8.3.rc3
e0dd5ab	trac #25403: pyflakes

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

Changed commit from 8000a65 to e0dd5ab

[dcoudert]

comment:12

This new version should perform better.

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

Changed commit from e0dd5ab to 87ea629

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

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

87ea629

various changes and fixes

[b0bf1a7b-bfe9-44fe-8236-57b33990cc18]

comment:15

Hi, I went ahead and pushed some changes to this branch:

• I had a look at the reference [MW1990]. Thanks for taking the time to implement much of their algorithm! However, I noticed that your implementation did not include the (indeed, rather complicated) probabilistic check to restart in their "NODOUBLES" function. For now, I have simply made a change to the docstring to point out that the generated graph is not uniformly random.
• I added a check on the maximum degree to the function (plus a note in the docstring and a doctest).
• I fixed a typo: retart instead of restart.
• I added information about the positions to the docstring. Also, I'm not sure if we need to do anything about this, but I figured I would point out here that the positions added by this ticket are inconsistent with the position generated by sage.graphs.CompleteBipartiteGraph. That function places the two parts horizontally and also uses differently scaled spacing.
• I fixed some other typos in the comments and docstrings and combined some imports into one line.

Everything else seemed OK, so you may set to positive_review if you're happy with my changes.

---

New commits:

87ea629

various changes and fixes

[dcoudert]

comment:16

Thank you for all the corrections.

For the consistency of positions, what I can do is add a method in graph_plot.py for bipartite embedding, like _bipartite_embedding(g, V1, V2, first=(0,1), last=(1,0)) in the flavor of _line_embedding, and then use it in all bipartite graphs generators. It can proceed as the plotting of CompleteBipartiteGraph. Would you agree on that ?

[b0bf1a7b-bfe9-44fe-8236-57b33990cc18]

comment:17

Replying to @dcoudert:

For the consistency of positions, what I can do is add a method in graph_plot.py for bipartite embedding, like _bipartite_embedding(g, V1, V2, first=(0,1), last=(1,0)) in the flavor of _line_embedding, and then use it in all bipartite graphs generators. It can proceed as the plotting of CompleteBipartiteGraph. Would you agree on that ?

I wasn't familiar with those methods in graph_plot, but this sounds like a great solution! We should probably update the ticket title / description now though.

[b0bf1a7b-bfe9-44fe-8236-57b33990cc18]

Description changed:

--- 
+++ 
@@ -1,2 +1,3 @@
-Add a generator of random regular bipartite graph.
+Add a generator of random regular bipartite graph, `RandomRegularBipartite`.

+This ticket also moves the graph embedding method in `CompleteBipartite` to `graph_plot` so that embeddings for `CompleteBipartiteGraph`, `RandomRegularBipartite` and `RandomBipartite` can be easily made consistent.

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

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

2e3d821	trac #25403: corrections of _line_embedding
2dafc65	trac #25403: use _line_embedding in random.py
946a02b	trac #25403: _line_embedding in CompleteBipartiteGraph
0de116b	trac #25403: polishing

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

Changed commit from 87ea629 to 0de116b

[dcoudert]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 Add a generator of random regular bipartite graph, `RandomRegularBipartite`.

-This ticket also moves the graph embedding method in `CompleteBipartite` to `graph_plot` so that embeddings for `CompleteBipartiteGraph`, `RandomRegularBipartite` and `RandomBipartite` can be easily made consistent.
+This ticket also unifies the graph embedding method of `CompleteBipartiteGraph`, `RandomRegularBipartite` and `RandomBipartite` by using method `_line_embedding` from `graph_plot.py`.

[dcoudert]

comment:20

I have chosen not to create a new method in graph_plot.py as the need for bipartite embedding is rather limited so far. I use 2 calls to _line_embedding instead.

I have corrected the method for _line_embedding to avoid errors with graphs on 0 or 1 vertex.

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

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

315feb7

Remove trailing whitespace

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

Changed commit from 0de116b to 315feb7

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

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

5c7a97d

Fix doctest in `sage/graphs/line_graph.py`

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

Changed commit from 315feb7 to 5c7a97d

[b0bf1a7b-bfe9-44fe-8236-57b33990cc18]

comment:23

I removed a trailing whitespace and fixed a doctest that was broken by the change to graph name inside CompleteBipartiteGraph. Feel free to set to positive_review after you see this.

[dcoudert]

comment:24

So then. Thanks.

[vbraun]

Changed branch from public/25403_random_regular_bipartite to 5c7a97d