The current add_edge method in BipartiteGraph refuses to add an edge between two vertices belonging to the same set. This may seem perfectly fine, but when the two vertices are in distinct connected components, the graph may stay bipartite with a new edge even if the vertices are in the same partition :

sage: g = BipartiteGraph(2*graphs.GridGraph([4,4]))
sage: g.add_edge(0,30)
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)

/usr/local/sage/devel/sage-bip/sage/graphs/<ipython console> in <module>()

/usr/local/sage/local/lib/python2.6/site-packages/sage/graphs/bipartite_graph.pyc in add_edge(self, u, v, label)
    690         # check for endpoints in different partitions
    691         if self.left.issuperset((u,v)) or self.right.issuperset((u,v)):
--> 692             raise RuntimeError('Edge vertices must lie in different partitions.')
    693 
    694         # add the edge

RuntimeError: Edge vertices must lie in different partitions.

From the discussion on #8425 :

//////
To be honest, I really would like to be able to deal with Bipartite Graphs without having to specify myself in which set my vertices are... What would you think of setting a vertex to "left" if the users does not specify left=True or right=True, and modify a bit add_edge ? This way, the edge could be added immediately if the two vertices at its ends are in different sets, and if they are not the colors could be changed whenever possible to fit the graph with a new edge ?

Actually, when a graph is bipartite and split in two sets, you can add an edge in exactly two situations :

• The colors between the endpoints are different

• The colors are the same, but the vertices belong to two different connected components

So two solutions :

• Add an edge if the colors are different. If they are not, check that there is no path from one vertex to the other, and if it is the case reverse the coloring of one of the two components and add the edge

• Fix a partition for any connected component, and maintain them updated.

The problem is that the first makes of add_edge a linear-time function. The second way keeps it to O(1), but we would have to update the list of connected components, even if it is not so hard. The truth is I do not know what is best for this class, and I'm eager to learn your advice on it. It is also possible to add a flag like "allow_set_modifications" if you want to keep the possibility to refuse an addition in some cases... But anyway this should be mentionned in the docstrings :-)
///////

If anybody working on the BipartiteGraph class is willing to give all this a try.... :-)

Nathann

CC: @rhinton @sagetrac-brunellus

Component: graph theory

Author: Bruno Edwards, David Coudert

Branch/Commit: 8eb29c8

Reviewer: David Coudert

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