Graphs: simple bipartite double method added to undirected graphs

[Ivo-Maffei]

The bipartite double of a graph is its tensor product with the graph K_2.
A simple method bipartite_double(extended=False) is added to the undirected graph class in order to compute the bipartite double and the extended bipartite double of a graph.

Depends on #30240

CC: @dimpase

Component: graph theory

Author: Ivo Maffei

Branch/Commit: 2d6c8ba

Reviewer: David Coudert

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

[Ivo-Maffei]

comment:1

The dependency on #30240 is only needed to avoid a merge conflict in the master bibliography

[Ivo-Maffei]

Commit: 13dc48a

[Ivo-Maffei]

Branch: public/graphs/30355

[Ivo-Maffei]

Last 10 new commits:

7a906b1	fixed typos and formatting
8164445	itertools to simplify code
6a15420	change optional flag for atlasrep
92537c0	renamed locally GQ function and added references
6f3754b	forgot to rename graph
7754591	fixed indentation issue
4e17fd7	fixed bug introduced by removing module_list
e063b5e	simplified import
574960d	added gap_packages flag to atlasrep
13dc48a	Merge branch 30240 into bipartite_double

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:3

Several comments:

• no need to add dependency on Graphs: a few distance-regular graphs #30240 here

• small changes

-        The bipartite double of a graph `G` has vertices
-        `\{ (v,0), (v,1) : v \in G\}` and for any edge `(u, v)` in `G`
-        we have edges `((u,0),(v,1))` and `((u,1),(v,0))`.
-        Note that this is the tensor product of `G` with `K_2`.
-        See :
+        The bipartite double of a graph `G` has vertex set
+        `\{ (v,0), (v,1) : v \in G\}` and for any edge `(u, v)` in `G`
+        it has edges `((u,0),(v,1))` and `((u,1),(v,0))`.
+        Note that this is the tensor product of `G` with `K_2`.

• input

-        - ``extended`` -- boolean (optional); if ``True`` return the extended
-          bipartite double, else the bipartite double. Default: ``False``.
+        - ``extended`` -- boolean (default: ``False``); Whether to return the extended
+          bipartite double, or only the bipartite double (default)

• it is not important to mention and test that the input graph is untouched. You return a new graph, no?

• instead of a REFERENCES: block, use a .. SEEALSO:: block (check other methods)

• TETS -> TESTS

• no need to import the complete graph generator, simply use Graph([(0, 1)])

• simpler code

-        if extended:
-            for v in self:
-                v1 = (v, 0)
-                v2 = (v, 1)
-
-                G.add_edge((v1, v2))
+        if extended:
+            G.add_edges(((v, 0), (v, 1)) for v in self)

• What if self is the empty graph ? a 1 vertex graph ? a disconnected graph ?

• instead of testing for equality (sage: H == G.tensor_product(graphs.CompleteGraph(2))), it might be better to check if the graphs are isomorphismic.

[sagetrac-git]

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

2d6c8ba

fix docstring; added doctests; simplier code

[sagetrac-git]

Changed commit from 13dc48a to 2d6c8ba

[Ivo-Maffei]

comment:5

Replying to @dcoudert:

• no need to add dependency on Graphs: a few distance-regular graphs #30240 here

I based this branch on #30240 because otherwise the reference [VDKT2016] would not work.
I could add it to the master bibliography again, but I think this will cause a merge conflict with #30240.

• it is not important to mention and test that the input graph is untouched. You return a new graph, no?

I mentioned it in the OUTPUT section. I could stress it in a .. NOTE:: block, if you wish.

• What if self is the empty graph ? a 1 vertex graph ? a disconnected graph ?

I added this cases in the TESTS and EXAMPLES sections. Should I also discuss them somewhere else?

[dcoudert]

comment:6

LGTM.

[vbraun]

Changed branch from public/graphs/30355 to 2d6c8ba