Opened 8 years ago

Closed 8 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 ncohen)

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 ncohen 8 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 8 years ago by ncohen

  • Cc ncohen added

comment:2 Changed 8 years ago by brunellus

  • Cc brunellus added

comment:3 Changed 8 years ago by ncohen

  • Cc jason added
  • Description modified (diff)
  • Status changed from new to needs_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 8 years ago by rbeezer

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 8 years ago by rbeezer

  • 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: Changed 8 years ago by ncohen

  • 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 8 years ago by ncohen

comment:7 in reply to: ↑ 6 Changed 8 years ago by rbeezer

  • 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 8 years ago by rbeezer

  • Authors set to Nathann Cohen
  • Reviewers set to Rob Beezer

comment:9 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.