Ticket #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 | Work issues: | |
| Report Upstream: | N/A | Reviewers: | Robert Miller |
| Authors: | Nathann Cohen | Merged in: | sage-4.5.alpha1 |
| Dependencies: | Stopgaps: |
Description (last modified by rlm) (diff)
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
-
trac_7563.patch
(41.3 KB) -
added by ncohen 3 years ago.
Change History
comment:2 Changed 3 years ago by ncohen
- Cc dimpase, mvngu, rlm, wdj, jason added
- Status changed from needs_work to needs_review
- Description modified (diff)
- Summary changed from Interval Graphs : recognition and interval representation to Interval Graphs : recognition
comment:3 follow-up: ↓ 4 Changed 3 years ago by ncohen
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
comment:4 in reply to: ↑ 3 Changed 3 years ago by jason
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:6 Changed 3 years ago by rlm
- Reviewers set to Robert Miller
- Description modified (diff)
- Authors set to Nathann Cohen
