Improve add_edge in BipartiteGraph to make it independent from the current coloring

[nathanncohen]

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

[enjeck]

comment:6

I just tested this out using the example in the description. It worked without any error message. So it's safe to say this has been fixed?

[dcoudert]

comment:7

Not fully as this ticket raises the question of the addition of edges between vertices lying in different connected components.

So far, the order in which edges are added matters.

sage: g = BipartiteGraph()
sage: g.add_edges([(0, 1), (1, 2), (2, 3)])
sage: g = BipartiteGraph()
sage: g.add_edges([(0, 1), (3, 2), (1, 2)])
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-23-fa0c70b30e4b> in <module>
----> 1 g.add_edges([(Integer(0), Integer(1)), (Integer(3), Integer(2)), (Integer(1), Integer(2))])

~/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/graphs/bipartite_graph.py in add_edges(self, edges, loops)
    931             # check for endpoints in different partitions
    932             if self.left.issuperset((u, v)) or self.right.issuperset((u, v)):
--> 933                 raise RuntimeError("edge vertices must lie in different partitions")
    934 
    935             # automatically decide partitions for the newly created vertices

RuntimeError: edge vertices must lie in different partitions

I have no opinion on the best solution. Regular users of this class should clarify expected behavior.

[Bruno-TT]

comment:10

Made a start on this ticket. Seeing as there is already an inherited .connected_components() method, that calculates them on the fly (rather than maintaining an invariant), I'm using that.

[Bruno-TT]

Branch: /u/gh-Bruno-TT/improved-add-edge

[Bruno-TT]

Commit: c3028e7

[dcoudert]

comment:12

You should use self.connected_component_containing_vertex(v, sort=False).

For coding style, prefer old_left = frozenset(self.left) with spaces around =.

---

New commits:

ce05306

initial logic / proof of concept

[dcoudert]

Changed commit from c3028e7 to ce05306

[Bruno-TT]

Changed commit from ce05306 to c46e838

[Bruno-TT]

comment:13

Replying to David Coudert:

You should use self.connected_component_containing_vertex(v, sort=False).

Good spot, thanks!

For coding style, prefer old_left = frozenset(self.left) with spaces around =.

Thanks, will do this tomorrow.

---

New commits:

c46e838

refactoring + improvements + warning + doctests

[dcoudert]

comment:14

add_edge:

• you don't need to save current left/right
• the warning is not necessary (we usually don't do that). The behavior of the method should be well documented.

There is something wrong in the proposed behavior for add_edges, and it's true that other add_edges methods in the graph module must also be corrected (in other tickets). The issue is that we modify the graph before raising an error. It would be much better to first check if it is possible to add all edges and then to actually add them and update the partition accordingly or raise an error without modifying the graph.

[Bruno-TT]

comment:15

Replying to David Coudert:

add_edge:

• you don't need to save current left/right

Thanks, good spot - removed it.

• the warning is not necessary (we usually don't do that). The behavior of the method should be well documented.

Cool, I've removed the warning and updated the tests + documentation.

There is something wrong in the proposed behavior for add_edges, and it's true that other add_edges methods in the graph module must also be corrected (in other tickets). The issue is that we modify the graph before raising an error. It would be much better to first check if it is possible to add all edges and then to actually add them and update the partition accordingly or raise an error without modifying the graph.

Good idea, I didn't think of that. I'll try and implement an algorithm now.

[Bruno-TT]

Changed commit from c46e838 to 5cebd58

[Bruno-TT]

comment:16

Update: I've implemented the algorithm to check whether adding a set of edges is possible

---

New commits:

7d92dfd	formatting + docs and doctest + removed warning
5cebd58	add_edges is now all-or-nothing + tests

[dcoudert]

Changed branch from /u/gh-Bruno-TT/improved-add-edge to public/graphs/8744_add_edge

[dcoudert]

comment:17

I moved the branch to public and pushed a review ticket (easier than explaining all the details). Let me know if you agree.

---

New commits:

0db1a7d	trac #8744: merge with 9.8.beta4
3dfe5fb	trac #8744: review commit

[dcoudert]

Reviewer: David Coudert

[dcoudert]

Changed commit from 5cebd58 to 3dfe5fb

[dcoudert]

comment:18

Why have you added the statement # autopep8: off ?

[Bruno-TT]

comment:19

Replying to David Coudert:

I moved the branch to public and pushed a review ticket (easier than explaining all the details). Let me know if you agree.

Assuming this is a typo and you mean review commit? If not then I can't find the ticket

3dfe5fb	trac #8744: review commit

I don't quite understand why you've chosen to remove the

return set(left), set(right), vertex_in_left
...
self.left, self.right, vertex_in_left = b

and replace it with

return vertex_in_left
...
# If we get here, then we've found a valid bipartition.
        # We update the bipartition
        self.left.clear()
        self.right.clear()
        for v in vertex_in_left:
            if vertex_in_left[v]:
                self.left.add(v)
            else:
                self.right.add(v)

I understand that vertex_in_left contains all the info needed to reconstruct the sets, but surely it's more efficient to just return the set objects and replace the references inside the graph, rather than adding another loop to reconstruct them?

Other than that, I like all the changes you made. It was a good idea having one edges_to_add list instead of us,vs,labels.

[sagetrac-git]

Changed commit from 3dfe5fb to 8eb29c8

[sagetrac-git]

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

8eb29c8

trac #8744: better loop

[dcoudert]

comment:21

The reason for not returning set(left), set(right), vertex_in_left is simply that we don't maintain left and right anymore in _check_bipartition_for_add_edges. So we have to rebuild left and right.

[dcoudert]

comment:22

For me this ticket is good to go.

[dcoudert]

Author: Bruno Edwards, David Coudert

[Bruno-TT]

comment:23

Replying to David Coudert:

For me this ticket is good to go.

I second that

[vbraun]

Changed branch from public/graphs/8744_add_edge to 8eb29c8