Perfect graph recognition algorithm

[ncohen]

Costly, but nice enough for small graphs :-)

requires #8927

[ncohen]

New version dealing with BipartiteGraph? graphs. Sorry for the two versions, they are identical ;-)

Nathann

[rlm]

Doctests fail:

sage -t  "devel/sage-main/sage/graphs/graph.py"             
**********************************************************************
File "/Users/rlmill/sage-4.4.4.alpha0/devel/sage-main/sage/graphs/graph.py", line 1458:
    sage: g.is_perfect()
Exception raised:
    Traceback (most recent call last):
      File "/Users/rlmill/sage-4.4.4.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/rlmill/sage-4.4.4.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/rlmill/sage-4.4.4.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_9[5]>", line 1, in <module>
        g.is_perfect()###line 1458:
    sage: g.is_perfect()
      File "/Users/rlmill/sage-4.4.4.alpha0/local/lib/python/site-packages/sage/graphs/graph.py", line 1516, in is_perfect
        counter_example = self.induced_subgraph_search(graphs.CycleGraph(i))
    AttributeError: 'Graph' object has no attribute 'induced_subgraph_search'
**********************************************************************

for example. Also, you should explain what a perfect graph is in the docstring, before quoting the theorem.

[ncohen]

Sorryyyyy !! This method has been renamed during the review of the corresponding ticket, and I didn't update this patch... I'll send one in a second !

Nathann

[rlm]

Your new patch applies fine (without #8927 even) and passes all doctests in sage/graphs. If you approve of the editing changes in my referee's patch, then set this ticket to positive review!

[ncohen]

Agreed ! :-)

Thanksssssssss !

Nathann

[rlm]

After sage-4.5.alpha1 is released, this will lead to a failed doctest:

**********************************************************************
File "/scratch/rlmill/release/sage-4.5.alpha1/devel/sage-main/sage/graphs/graph.py", line 1629:
    sage: g.is_perfect()
Exception raised:
    Traceback (most recent call last):
      File "/scratch/rlmill/release/sage-4.5.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/scratch/rlmill/release/sage-4.5.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/scratch/rlmill/release/sage-4.5.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_11[5]>", line 1, in <module>
        g.is_perfect()###line 1629:
    sage: g.is_perfect()
      File "/scratch/rlmill/release/sage-4.5.alpha1/local/lib/python/site-packages/sage/graphs/graph.py", line 1702, in is_perfect
        counter_example = self.subgraph_search(graphs.CycleGraph(i), induced = True).complement()
    AttributeError: 'NoneType' object has no attribute 'complement'  
**********************************************************************

[ncohen]

1) Sorryyyyyyyyy !!! 2) Fixed :-)

Nathann

[ncohen]

Hello !!!

My patch applied fine on sage-4.5, though I just updated it...

It also contains your modifications :-)

Nathann

[rlm]

It was probably the other patch causing conflict.