BipartiteGraph blindly trusts generic graphs

[kliem]

BipartiteGraph does currently check edges, when using the method add_edges:

sage: bg = BipartiteGraph()
bg.add_vertices([0, 1, 2], left=[True, False, True])
bg.add_edges([[0, 2]]) 

This doesn't raise an error, but it should.

While BipartiteGraph has its own method add_edge, it seems to trust generic graph do add_edges by iterating over the edges and calling add_edge. This is not the case (anymore).

We fix this, by implementing the method add_edges for BipartiteGraph, which just calls the backend on the prechecked edges.

Component: graph theory

Keywords: bipartite graph, add edges

Author: Jonathan Kliem

Branch/Commit: b0753d2

Reviewer: David Coudert

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

[kliem]

New commits:

4110553

add a doctest to not blindly trust generic graph

[kliem]

Commit: 4110553

[kliem]

Branch: public/28897

[dcoudert]

comment:2

Actually, the added doctest shows that we need a specific method for add_edges. The one of generic graph calls a backend that is not specific to bipartite graphs.

[kliem]

comment:4

At the moment everything works fine. add_edges calls add_edge, which checks that the vertices lie in different partitions.

However, once one modifies add_edges to directly call the backend, BipartiteGraph needs a modified version of it. If we add a special version now, we still have to remember it, once we optimize add_edges in generic graph.

The doctest would just ensure that one doesn't miss it with little effort for now.

[dcoudert]

comment:5

No. In 9.0.beta9, add_edges calls self._backend.add_edge(u, v, label, self._directed), and so the added doctest fails.
The patchbots are reporting that failing doctest.

[kliem]

comment:6

Ok. Never mind. I must have misread and not tested it (even though I thought I did).

[sagetrac-git]

Changed commit from 4110553 to a038512

[sagetrac-git]

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

a038512

implement add_edges for BipartiteGraph

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:10

You must change the documentation for parameter loops as loops should not be allowed in a bipartite graph. I suggest to set it to False by default, and document that it is always considered as False. This is exactly what current implementation do. For instance, with this patch, we get

sage: G = BipartiteGraph([(0,0)], loops=True)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-5-273b7e5c1458> in <module>()
----> 1 G = BipartiteGraph([(Integer(0),Integer(0))], loops=True)

/Users/dcoudert/sage3/sage/local/lib/python3.7/site-packages/sage/graphs/bipartite_graph.py in __init__(self, data, partition, check, *args, **kwds)
    309         else:
    310             if 'loops' in kwds and kwds['loops']:
--> 311                 raise ValueError('loops are not allowed in bipartite graphs')
    312             kwds['loops'] = False
    313 

ValueError: loops are not allowed in bipartite graphs

I just realized that some input parameters of BipartiteGraph are not documented, like weighted, multiedges, and of course loops.

Instead of defining a function check_edge and call self._backend.add_edges(map...), it might be faster to make a loop for e in edges in which you check the validity of that edge and if the edge is ok, then call self._backend.add_edge(u, v, label, self._directed). Indeed, method self._backend.add_edges also has to check if an edge is a pair or a triple.

[sagetrac-git]

Changed commit from a038512 to b0753d2

[sagetrac-git]

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

b0753d2

improved method add_edges and documentation

[kliem]

comment:12

Ok.

As for ignoring loops, I wouldn't allow it. In a generic graph, I can see that one wants the method to remove loops for comfort.

In a bipartite graph, one needs to clean up the input anyway. Loops is just one of many cases, where the ends of an edge are not in different parts.

[dcoudert]

comment:13

Please set the default value of loops to False.

Once done, you can set to positive review on my behalf.

[kliem]

comment:14

I don't understand. Doesn't False mean that we just skip loops without error?

[dcoudert]

comment:15

No, in Graph we raise an error when loops is False or None. The behavior has been changed some months ago after years of deprecation warnings.

sage: G = Graph(loops=False)
sage: G.add_edge(0,0)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-5-a53374f9e702> in <module>()
----> 1 G.add_edge(Integer(0),Integer(0))

/Users/dcoudert/sage3/sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in add_edge(self, u, v, label)
  10816                     pass
  10817 
> 10818         self._backend.add_edge(u, v, label, self._directed)
  10819 
  10820     def add_edges(self, edges, loops=True):

/Users/dcoudert/sage3/sage/local/lib/python3.7/site-packages/sage/graphs/base/sparse_graph.pyx in sage.graphs.base.sparse_graph.SparseGraphBackend.add_edge (build/cythonized/sage/graphs/base/sparse_graph.c:17581)()
   1500 
   1501         if u_int == v_int and not self._loops:
-> 1502             raise ValueError(f"cannot add edge from {u!r} to {v!r} in graph without loops")
   1503 
   1504         if not self.multiple_edges(None):

ValueError: cannot add edge from 0 to 0 in graph without loops
sage: G = Graph(loops=None)
sage: G.add_edge(0,0)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-7-a53374f9e702> in <module>()
----> 1 G.add_edge(Integer(0),Integer(0))

/Users/dcoudert/sage3/sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in add_edge(self, u, v, label)
  10816                     pass
  10817 
> 10818         self._backend.add_edge(u, v, label, self._directed)
  10819 
  10820     def add_edges(self, edges, loops=True):

/Users/dcoudert/sage3/sage/local/lib/python3.7/site-packages/sage/graphs/base/sparse_graph.pyx in sage.graphs.base.sparse_graph.SparseGraphBackend.add_edge (build/cythonized/sage/graphs/base/sparse_graph.c:17581)()
   1500 
   1501         if u_int == v_int and not self._loops:
-> 1502             raise ValueError(f"cannot add edge from {u!r} to {v!r} in graph without loops")
   1503 
   1504         if not self.multiple_edges(None):

ValueError: cannot add edge from 0 to 0 in graph without loops

[kliem]

comment:16

Yes. But when you do

sage: G.add_edges([[0, 0]], loops=False)

it just ignores all the loops and does not raise an error (as is documented in add_edges).

[dcoudert]

comment:17

Right.

LGTM.

[fchapoton]

comment:18

9.0 is out

[vbraun]

Changed branch from public/28897 to b0753d2