Opened 2 years ago
Closed 2 years ago
#28897 closed defect (fixed)
BipartiteGraph blindly trusts generic graphs
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  graph theory  Keywords:  bipartite graph, add edges 
Cc:  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  b0753d2 (Commits, GitHub, GitLab)  Commit:  b0753d2b74db0d3147453e116c4aab823a09a1c5 
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Change History (19)
comment:1 Changed 2 years ago by
 Branch set to public/28897
 Commit set to 411055376d1906c355ad656d1b38a970b1cded3b
 Status changed from new to needs_review
comment:2 Changed 2 years ago by
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.
comment:3 Changed 2 years ago by
 Status changed from needs_review to needs_work
comment:4 Changed 2 years ago by
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.
comment:5 Changed 2 years ago by
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.
comment:6 Changed 2 years ago by
Ok. Never mind. I must have misread and not tested it (even though I thought I did).
comment:7 Changed 2 years ago by
 Description modified (diff)
 Type changed from enhancement to defect
comment:8 Changed 2 years ago by
 Commit changed from 411055376d1906c355ad656d1b38a970b1cded3b to a038512146278c2f5779133a26fc0cc65365ba35
Branch pushed to git repo; I updated commit sha1. New commits:
a038512  implement add_edges for BipartiteGraph

comment:9 Changed 2 years ago by
 Status changed from needs_work to needs_review
comment:10 Changed 2 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to needs_work
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) <ipythoninput5273b7e5c1458> in <module>() > 1 G = BipartiteGraph([(Integer(0),Integer(0))], loops=True) /Users/dcoudert/sage3/sage/local/lib/python3.7/sitepackages/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.
comment:11 Changed 2 years ago by
 Commit changed from a038512146278c2f5779133a26fc0cc65365ba35 to b0753d2b74db0d3147453e116c4aab823a09a1c5
Branch pushed to git repo; I updated commit sha1. New commits:
b0753d2  improved method add_edges and documentation

comment:12 Changed 2 years ago by
 Status changed from needs_work to needs_review
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.
comment:13 Changed 2 years ago by
Please set the default value of loops to False
.
Once done, you can set to positive review on my behalf.
comment:14 Changed 2 years ago by
I don't understand. Doesn't False
mean that we just skip loops without error?
comment:15 Changed 2 years ago by
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) <ipythoninput5a53374f9e702> in <module>() > 1 G.add_edge(Integer(0),Integer(0)) /Users/dcoudert/sage3/sage/local/lib/python3.7/sitepackages/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/sitepackages/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) <ipythoninput7a53374f9e702> in <module>() > 1 G.add_edge(Integer(0),Integer(0)) /Users/dcoudert/sage3/sage/local/lib/python3.7/sitepackages/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/sitepackages/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
comment:16 Changed 2 years ago by
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
).
comment:19 Changed 2 years ago by
 Branch changed from public/28897 to b0753d2b74db0d3147453e116c4aab823a09a1c5
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
add a doctest to not blindly trust generic graph