Opened 11 years ago
Last modified 6 years ago
#8744 new enhancement
Improve add_edge in BipartiteGraph to make it independent from the current coloring
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | graph theory | Keywords: | |
Cc: | rhinton, brunellus | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
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 somec ases... 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
Change History (5)
comment:1 Changed 9 years ago by
- Cc brunellus added
comment:2 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:3 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:4 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:5 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4