Opened 10 years ago
Closed 10 years ago
#7563 closed enhancement (fixed)
Interval Graphs : recognition
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.5 |
Component: | graph theory | Keywords: | |
Cc: | dimpase, mvngu, rlm, wdj, jason | Merged in: | sage-4.5.alpha1 |
Authors: | Nathann Cohen | Reviewers: | Robert Miller |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This ticket implement PQ-Trees, to be used as a recognition algorithm for interval graphs. It also defines the function Graph.is_interval.
For the moment, PQ-Trees are defined inside of the graph/ folder, as it is where they are useful for the moment, but this may change if someone has a better idea :-)
I tried to document it as much as I could. Tell me if anything is missing !
Nathann
Depends on #8284.
Attachments (1)
Change History (9)
comment:1 Changed 10 years ago by
- Status changed from new to needs_work
comment:2 Changed 10 years ago by
- Cc dimpase mvngu rlm wdj jason added
- Description modified (diff)
- Status changed from needs_work to needs_review
- Summary changed from Interval Graphs : recognition and interval representation to Interval Graphs : recognition
comment:3 follow-up: ↓ 4 Changed 10 years ago by
comment:4 in reply to: ↑ 3 Changed 10 years ago by
Replying to ncohen:
Oh yes, and... There are many missing doctests
Ouch. That's a problem. I don't think the ticket should go into Sage without doctests on each python function.
(I haven't had time to look at the rest of the patch, though.)
comment:5 Changed 10 years ago by
"Your wish is my command" :-)
Nathann
Changed 10 years ago by
comment:6 Changed 10 years ago by
- Description modified (diff)
- Reviewers set to Robert Miller
comment:7 Changed 10 years ago by
- Status changed from needs_review to positive_review
Applies after #8284 and passes all its tests :). Coverage looks much better.
comment:8 Changed 10 years ago by
- Merged in set to sage-4.5.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
Oh yes, and... There are many missing doctests, but as this algorithm heavily uses dictionaries I wondered whether this could be done without being platform-dependent ^{};
Any idea welcome, here too.. Even though those functions will never be needed directly by the users, and all of them are indirectly tested anyway through the docstrings of is_interval.
Nathann