Bipartite graphs should not accept loops

[dcoudert]

Loops should not be allowed in a bipartite graph, but we can currently do:

sage: B = BipartiteGraph(loops=True, multiedges=True)
sage: B.add_edge(0, 0)
sage: B.is_bipartite()
False
sage: B.add_edge(1, 1)
sage: B.add_edge(2, 2)
sage: B.edges(labels=0)
[(0, 0), (1, 1), (2, 2)]
sage: B.add_edge(0, 1, 'a')
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
...
RuntimeError: Edge vertices must lie in different partitions.
sage: B.add_edge(3, 3)
sage: B.edges()
[(0, 0, None), (1, 1, None), (2, 2, None), (3, 3, None)]

When adding edges in a different order, the behavior is more consistent.

sage: B = BipartiteGraph(loops=True, multiedges=True)
sage: B.add_edge(0, 1, 'a')
sage: B.add_edge(0, 1, 'b')
sage: B.is_bipartite()
True
sage: B.add_edge(0,0)
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
...
RuntimeError: Edge vertices must lie in different partitions.

CC: @tscrim @sagetrac-zgershkoff

Component: graph theory

Author: David Coudert

Branch: 3c0c3d4

Reviewer: Zach Gershkoff

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

[dcoudert]

comment:1

I don't know which is the best place to forbid loops in BipartiteGraph. Any advise is more than welcome.

[dcoudert]

comment:2

I did some trials and I discovered hidden issues in the Graph constructor like: self.allow_loops(loops if loops else False, check=False) and self.allow_loops(False if loops is False else True, check=False), but the default value of loops is None ...

Don't know what to do :(

[sagetrac-zgershkoff]

comment:3

Replying to @dcoudert:

I did some trials and I discovered hidden issues in the Graph constructor like: self.allow_loops(loops if loops else False, check=False) and self.allow_loops(False if loops is False else True, check=False), but the default value of loops is None ...

Don't know what to do :(

A bit of reading suggests that this is intentional behavior on the graph6 and sparse6 data types, respectively. Makes me wish the code were commented better. https://users.cecs.anu.edu.au/~bdm/data/formats.txt

For bipartite graphs, the offending code that adds loops is

        if self.left.issuperset((u, v)) or self.right.issuperset((u, v)):
            raise RuntimeError(
                "Edge vertices must lie in different partitions.")

because if u is v and it's a new vertex, it won't notice that it's making a loop. But loops should be disallowed before this code is reached.

So __init__ should definitely have loops turned off, and maybe bipartite_graph.py should have an override for allow_loops() that just raises an error. A user determined to break it could go around and call the Graph method to enable loops, so maybe have a check in generic_graph.py, like

    def allow_loops(self, new, check=True):
        if isinstance(BipartiteGraph):
            raise ...

But that might be overreaching.

[dcoudert]

comment:4

A bit of reading suggests that this is intentional behavior on the graph6 and sparse6 data types, respectively. Makes me wish the code were commented better. https://users.cecs.anu.edu.au/~bdm/data/formats.txt

I fully agree. The graph module is one of the best of sagemath for the quality of its documentation, but it's not enough. An effort was started here #19477 but not finalized.

So __init__ should definitely have loops turned off, and maybe bipartite_graph.py should have an override for allow_loops() that just raises an error. A user determined to break it could go around and call the Graph method to enable loops, so maybe have a check in generic_graph.py, like

    def allow_loops(self, new, check=True):
        if isinstance(BipartiteGraph):
            raise ...

But that might be overreaching.

I was thinking to implement something like that.

One of my concern is the use of **argv in __init__. One possibility is to

• explicitly list authorized parameters, so not listing loops
• explicitly set loops=False in all calls to other constructors
• set the loops flag to False
• rewrite self.allow_loops to forbid self.allow_loops(True). It would be better to remove methods from the class, but I don't know how to do that.

[dcoudert]

Commit: 3c0c3d4

[dcoudert]

comment:5

This fixes some of the issues but it's neither a smart solution nor a complete fix.

Indeed, the following example should raises an error and not silently remove loops, no ?

sage: G = Graph([(0, 0), (0, 1), (1, 1)], loops=True)
sage: B = BipartiteGraph(G)
sage: B.edges(labels=0)
[(0, 1)]

At least, we can't add loops.

sage: sage: B.add_edge(0,0)
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
...
RuntimeError: Edge vertices must lie in different partitions.

---

New commits:

7951f65	trac #23275: forbid loops=True in __init__
8cf658e	trac #23275: another example
3c0c3d4	trac #23275: rewrite method allow_loops for bipartite graphs

[dcoudert]

Branch: u/dcoudert/23275

[saraedum]

Author: David Coudert

[dcoudert]

comment:7

anyone to review ?

[sagetrac-zgershkoff]

comment:8

It does what it says it does, although I should note that the module can still be fooled into accepting loops.

sage: B = BipartiteGraph()
sage: Graph.allow_loops(B, True)
sage: B.add_edge(0,0)
sage: B.is_bipartite()
False

[sagetrac-zgershkoff]

Reviewer: Zachary Gershkoff

[dcoudert]

comment:9

To avoid that, we should make a backend

sage: B = BipartiteGraph()
sage: B._backend
<type 'sage.graphs.base.sparse_graph.SparseGraphBackend'>

The method Graph.allow_loops(B, True) calls B._backend.loops(True).

[vbraun]

Changed branch from u/dcoudert/23275 to 3c0c3d4

[jdemeyer]

Changed commit from 3c0c3d4 to none

[jdemeyer]

Changed reviewer from Zachary Gershkoff to Zach Gershkoff