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:

Status badges

Description (last modified by Nathann Cohen)

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)

trac_12155.patch (3.9 KB) - added by Nathann Cohen 11 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 11 years ago by Nathann Cohen

Cc: Nathann Cohen added

comment:2 Changed 11 years ago by Lukáš Lánský

Cc: Lukáš Lánský added

comment:3 Changed 11 years ago by Nathann Cohen

Cc: Jason Grout added
Description: modified (diff)
Status: newneeds_review

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

comment:4 Changed 11 years ago by Rob Beezer

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 Rob Beezer

Status: needs_reviewneeds_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 Changed 11 years ago by Nathann Cohen

Status: needs_workneeds_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 Nathann Cohen

Attachment: trac_12155.patch added

comment:7 in reply to:  6 Changed 11 years ago by Rob Beezer

Status: needs_reviewpositive_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 Rob Beezer

Authors: Nathann Cohen
Reviewers: Rob Beezer

comment:9 Changed 11 years ago by Jeroen Demeyer

Merged in: sage-5.0.beta0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.