Opened 2 years ago

Closed 2 years ago

#28897 closed defect (fixed)

BipartiteGraph blindly trusts generic graphs

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description (last modified by gh-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.

Change History (19)

comment:1 Changed 2 years ago by gh-kliem

  • Branch set to public/28897
  • Commit set to 411055376d1906c355ad656d1b38a970b1cded3b
  • Status changed from new to needs_review

New commits:

4110553add a doctest to not blindly trust generic graph

comment:2 Changed 2 years ago by dcoudert

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 dcoudert

  • Status changed from needs_review to needs_work

comment:4 Changed 2 years ago by gh-kliem

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 dcoudert

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 gh-kliem

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

comment:7 Changed 2 years ago by gh-kliem

  • Description modified (diff)
  • Type changed from enhancement to defect

comment:8 Changed 2 years ago by git

  • Commit changed from 411055376d1906c355ad656d1b38a970b1cded3b to a038512146278c2f5779133a26fc0cc65365ba35

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

a038512implement add_edges for BipartiteGraph

comment:9 Changed 2 years ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:10 Changed 2 years ago by dcoudert

  • 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)
<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.

comment:11 Changed 2 years ago by git

  • Commit changed from a038512146278c2f5779133a26fc0cc65365ba35 to b0753d2b74db0d3147453e116c4aab823a09a1c5

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

b0753d2improved method add_edges and documentation

comment:12 Changed 2 years ago by gh-kliem

  • 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 dcoudert

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 gh-kliem

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

comment:15 Changed 2 years ago by dcoudert

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

comment:16 Changed 2 years ago by gh-kliem

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:17 Changed 2 years ago by dcoudert

  • Status changed from needs_review to positive_review

Right.

LGTM.

comment:18 Changed 2 years ago by chapoton

  • Milestone changed from sage-9.0 to sage-9.1

9.0 is out

comment:19 Changed 2 years ago by vbraun

  • Branch changed from public/28897 to b0753d2b74db0d3147453e116c4aab823a09a1c5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.