#8425: BipartiteGraph add_edge allows bipartite property to be violated.
----------------------------+-----------------------------------------------
Reporter: rhinton | Owner: rhinton
Type: defect | Status: needs_work
Priority: major | Milestone: sage-4.4
Component: graph theory | Keywords: BipartiteGraph, add_edge
Author: Ryan Hinton | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Hello !!!
I have to admit I do not really like this one :-/
I seldom work on this BipartiteGraph class, and I understand you usally
know which are your left and right sets, but I have to admit I would not
want to see an error raised when I am building a valid bipartite graph,
without taking care of the sets myself. For example :
{{{
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.
}}}
And 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 :-)
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8425#comment:6>
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.
