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 )
Costly, but nice enough for small graphs :-)
requires #8927
Attachments (1)
Change History (16)
comment:1 Changed 9 years ago by
- Description modified (diff)
comment:2 Changed 9 years ago by
- Status changed from new to needs_review
comment:3 Changed 9 years ago by
- Cc rhinton added
comment:4 Changed 9 years ago by
- Priority changed from major to minor
comment:5 Changed 9 years ago by
- Description modified (diff)
comment:6 Changed 9 years ago by
- 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
- 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
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
- Status changed from needs_review to positive_review
Agreed ! :-)
Thanksssssssss !
Nathann
comment:10 Changed 9 years ago by
- 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
- Status changed from needs_work to needs_review
1) Sorryyyyyyyyy !!! 2) Fixed :-)
Nathann
comment:12 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues set to rebase on sage-4.5
comment:13 Changed 9 years ago by
- 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
comment:14 Changed 9 years ago by
- Status changed from needs_review to positive_review
It was probably the other patch causing conflict.
comment:15 Changed 8 years ago by
- 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
New version dealing with BipartiteGraph? graphs. Sorry for the two versions, they are identical ;-)
Nathann