#8744: Improve add_edge in BipartiteGraph to make it independent from the
current
coloring
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.4
Component: graph theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8744>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
