Opened 10 years ago
Closed 10 years ago
#12155 closed defect (fixed)
Bug when taking complement of bipartite graph.
Reported by: | fidelbarrera | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | graph theory | Keywords: | bipartite, complement |
Cc: | rbeezer, ncohen, brunellus, jason | 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 10 years ago by
- Cc ncohen added
comment:2 Changed 10 years ago by
- Cc brunellus added
comment:3 Changed 10 years ago by
- Cc jason added
- Description modified (diff)
- Status changed from new to needs_review
comment:4 Changed 10 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 10 years ago by
- Status changed from needs_review to 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 10 years ago by
- Status changed from needs_work to 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 10 years ago by
comment:7 in reply to: ↑ 6 Changed 10 years ago by
- Status changed from needs_review to 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 10 years ago by
- Reviewers set to Rob Beezer
comment:9 Changed 10 years ago by
- Merged in set to sage-5.0.beta0
- Resolution set to fixed
- Status changed from positive_review to 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