Opened 9 years ago

Closed 9 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 rlm)

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)

trac_7563.patch (41.3 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_work

comment:2 Changed 9 years ago by ncohen

  • 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: Changed 9 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 9 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:5 Changed 9 years ago by ncohen

"Your wish is my command" :-)

Nathann

Changed 9 years ago by ncohen

comment:6 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • Description modified (diff)
  • Reviewers set to Robert Miller

comment:7 Changed 9 years ago by rlm

  • Status changed from needs_review to positive_review

Applies after #8284 and passes all its tests :). Coverage looks much better.

comment:8 Changed 9 years ago by rlm

  • Merged in set to sage-4.5.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.