Opened 11 years ago
Closed 11 years ago
#12155 closed defect (fixed)
Bug when taking complement of bipartite graph.
Reported by: | Fidel Barrera-Cruz | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | graph theory | Keywords: | bipartite, complement |
Cc: | Rob Beezer, Nathann Cohen, Lukáš Lánský, Jason Grout | Merged in: | sage-5.0.beta0 |
Authors: | Nathann Cohen | Reviewers: | Rob Beezer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Quick description:
sage: g=graphs.CompleteBipartiteGraph(3,3) sage: g.complement() ... RuntimeError: Edge vertices must lie in different partitions.
For more details please see discussion at
http://groups.google.com/group/sage-devel/browse_thread/thread/9fc4c6bfa8d005b3
Apply:
Attachments (1)
Change History (10)
comment:1 Changed 11 years ago by
Cc: | Nathann Cohen added |
---|
comment:2 Changed 11 years ago by
Cc: | Lukáš Lánský added |
---|
comment:3 Changed 11 years ago by
Cc: | Jason Grout added |
---|---|
Description: | modified (diff) |
Status: | new → needs_review |
comment:4 Changed 11 years ago by
Nathann,
Looks good. Testing right now. What do you think of adding something to the TESTS section for each graph that keeps somebody from thinking it would be cool to change these constructions back to returning BipartiteGraph
instances? Just build one and take the complement with a reference to this ticket. I guess this is where a test suite would help - taking the complement in the test suite would keep somebody from ever making a new construction like these.
Is there someplace that shows how to convert a plain graph into a bipartite graph? (I have not looked.) In other words
G = graphs.CompleteBipartiteGraph(3, 4) H = BipartiteGraph(G)
Or maybe a way to do the conversion by giving the partition, so that there is no real computation to find it? If there are any methods for the BipartiteGraph? class which are specialized for that situation, it'd be good to document how to easily get to those. Lots of travel for the next 5 weeks, but I'll try to stay with this one.
Rob
comment:5 Changed 11 years ago by
Status: | needs_review → needs_work |
---|
I got two errors on 4.8.alpha3. Error messages (print "Error!"
) could be cleaned-up in the first.
rob@lava:/sage/sage-4.8.alpha3/devel/sage$ ../../sage -t devel/sage-main/sage/graphs/graph.py sage -t "devel/sage-main/sage/graphs/graph.py" ********************************************************************** File "/sage/sage-4.8.alpha3/devel/sage-main/sage/graphs/graph.py", line 1475: sage: if not g.is_forest(): cycle = g.is_even_hole_free(certificate = True) if cycle.order() % Integer(2) == Integer(1): print "Error !" if not cycle.is_isomorphic( graphs.CycleGraph(cycle.order())): print "Error !" Exception raised: Traceback (most recent call last): File "/sage/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/sage/sage-4.8.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/sage/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_6[8]>", line 2, in <module> cycle = g.is_even_hole_free(certificate = True) File "/sage/sage-4.8.alpha3/local/lib/python/site-packages/sage/graphs/graph.py", line 1528, in is_even_hole_free subgraph = self.subgraph_search(GraphGenerators().CycleGraph(start), induced = True) File "/sage/sage-4.8.alpha3/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 9444, in subgraph_search return self.subgraph(g) File "/sage/sage-4.8.alpha3/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 9071, in subgraph edge_property=edge_property) File "/sage/sage-4.8.alpha3/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 9328, in _subgraph_by_deleting G = self.copy() File "/sage/sage-4.8.alpha3/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 472, in __copy__ G = self.__class__(self, name=self.name(), pos=copy(self._pos), boundary=copy(self._boundary), implementation=implementation, sparse=sparse) File "/sage/sage-4.8.alpha3/local/lib/python/site-packages/sage/graphs/graph.py", line 1085, in __init__ pos = data.get_pos().copy() AttributeError: 'list' object has no attribute 'copy' ********************************************************************** File "/sage/sage-4.8.alpha3/devel/sage-main/sage/graphs/graph.py", line 1500: sage: all( t(graphs.RandomBipartite(10,10,.5)) for i in range(100) ) Exception raised: Traceback (most recent call last): File "/sage/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/sage/sage-4.8.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/sage/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_6[14]>", line 1, in <module> all( t(graphs.RandomBipartite(Integer(10),Integer(10),RealNumber('.5'))) for i in range(Integer(100)) )###line 1500: sage: all( t(graphs.RandomBipartite(10,10,.5)) for i in range(100) ) File "<doctest __main__.example_6[14]>", line 1, in <genexpr> all( t(graphs.RandomBipartite(Integer(10),Integer(10),RealNumber('.5'))) for i in range(Integer(100)) )###line 1500: sage: all( t(graphs.RandomBipartite(10,10,.5)) for i in range(100) ) File "<doctest __main__.example_6[13]>", line 1, in <lambda> t = lambda x : (Graph(x).is_forest() or###line 1498: sage: t = lambda x : (Graph(x).is_forest() or File "/sage/sage-4.8.alpha3/local/lib/python/site-packages/sage/graphs/graph.py", line 1085, in __init__ pos = data.get_pos().copy() AttributeError: 'list' object has no attribute 'copy' ********************************************************************** 1 items had failures: 2 of 16 in __main__.example_6 ***Test Failed*** 2 failures. For whitespace errors, see the file /home/rob/.sage//tmp/graph_18917.py [12.0 s]
comment:6 follow-up: 7 Changed 11 years ago by
Status: | needs_work → needs_review |
---|
OOps.... Shame on me :-/
It is fixed in this patch, which also contains tests.
Btw, there is some doc for the BipartiteGraph? class there http://www.sagemath.org/doc/reference/sage/graphs/bipartite_graph.html
but I have to admit I am really not a big fan of this class... It just prevents somebody from using some operations at the cost of many problems (that most of the functions inherited by BipartiteGraph? just do not work), and I really believe that "keeping a graph bipartite" should be something you should do yourself when you need it, and not put it inside of the graph class. That's the problem with graph properties, if you want to ensure that they are kept throughout the object's life you have to double check every operation. This being said, check that a graph is bipartite is probably one of the cheapest tests there is.
Nathann
Changed 11 years ago by
Attachment: | trac_12155.patch added |
---|
comment:7 Changed 11 years ago by
Status: | needs_review → positive_review |
---|
Replying to ncohen:
It is fixed in this patch, which also contains tests.
Everything looks good now. Positive review.
but I have to admit I am really not a big fan of this class...
After this experience, I agree. It might be nice to use this class to carry around the bipartition, and specialized methods for algorithms that are much faster ona bipartite graph, but enforcing the bipartition through operations seems to great a burden.
Rob
comment:8 Changed 11 years ago by
Authors: | → Nathann Cohen |
---|---|
Reviewers: | → Rob Beezer |
comment:9 Changed 11 years ago by
Merged in: | → sage-5.0.beta0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Fixing the problem by ensuring that no instances of BipartiteGraph? are returned by the graph generators.
https://groups.google.com/d/topic/sage-devel/n8TGv6jQBbM/discussion
Nathann