Opened 9 years ago

Closed 8 years ago

#8953 closed enhancement (fixed)

Perfect graph recognition algorithm

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-4.5.2
Component: graph theory Keywords:
Cc: rhinton Merged in: sage-4.5.2.alpha0
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

Costly, but nice enough for small graphs :-)

requires #8927

Attachments (1)

trac_8953.patch (4.7 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

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

Nathann

comment:3 Changed 9 years ago by ncohen

  • Cc rhinton added

comment:4 Changed 9 years ago by ncohen

  • Priority changed from major to minor

comment:5 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:6 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • Status changed from needs_review to needs_work

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.

comment:7 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

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

comment:8 Changed 9 years ago by 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!

comment:9 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

Agreed ! :-)

Thanksssssssss !

Nathann

comment:10 Changed 9 years ago by rlm

  • Reviewers set to Robert Miller
  • Status changed from positive_review to needs_work

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'  
**********************************************************************

comment:11 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

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

Nathann

comment:12 Changed 9 years ago by rlm

  • Status changed from needs_review to needs_work
  • Work issues set to rebase on sage-4.5

comment:13 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Hello !!!

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

It also contains your modifications :-)

Nathann

Changed 9 years ago by ncohen

comment:14 Changed 9 years ago by rlm

  • Status changed from needs_review to positive_review

It was probably the other patch causing conflict.

comment:15 Changed 8 years ago by mpatel

  • Merged in set to sage-4.5.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
  • Work issues rebase on sage-4.5 deleted
Note: See TracTickets for help on using tickets.