Opened 11 years ago

Closed 11 years ago

#6764 closed enhancement (fixed)

Independent Set of Representatives

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

See ​http://groups.google.com/group/sage-devel/browse_thread/thread/9d9b09274f1eab83/79938a2139ba25d9?lnk=gst&q=isr#79938a2139ba25d9

This patch add the ISR() function for graphs. The Independent Set of Representatives is a generalisation of graph coloring and list coloring, but goes way further ! I tried to take care of the documentation, so you will find some more informations in the docstrings if you need it ! ;-)

This patch uses Linear Programming, so you will have to first install GLPK (see #6867), then the patch for numerical.MIP at #6869 ;-)

Attachments (2)

ISR.patch​ (4.0 KB) - added by rlm 11 years ago.
rebased for 4.3.rc1
trac_6764.patch​ (5.3 KB) - added by ncohen 11 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 11 years ago by AlexGhitza

  • Summary changed from [with patch, needs review] Independent Set of Reresentatives (uses Linear Programming) to [with patch, needs review] Independent Set of Representatives (uses Linear Programming)

comment:2 Changed 11 years ago by ncohen

  • Description modified (diff)
  • Summary changed from [with patch, needs review] Independent Set of Representatives (uses Linear Programming) to [with patch, needs review] Independent Set of Representatives

comment:3 Changed 11 years ago by ncohen

  • Summary changed from [with patch, needs review] Independent Set of Representatives to [with patch, needs work] Independent Set of Representatives

As the functions dealing with LP have not been reviewed, I prefer to rewrite the MIP class for Sage to make it easier to use. I will post a new version of the MIP patch as soon as possible, along with all the patches for functions using it.

Sorry for the trouble, I'll try to make it quick !

Nathann

comment:4 Changed 11 years ago by ncohen

  • Description modified (diff)

comment:5 Changed 11 years ago by ncohen

  • Description modified (diff)

comment:6 Changed 11 years ago by ncohen

  • Summary changed from [with patch, needs work] Independent Set of Representatives to [with patch, needs review] Independent Set of Representatives

Just updated, everything is ready for review :-)

Thanks again for your help !

Nathann

Changed 11 years ago by rlm

rebased for 4.3.rc1

comment:7 Changed 11 years ago by rlm

  • Report Upstream set to N/A
  • Status changed from needs_review to needs_work
  • Summary changed from [with patch, needs review] Independent Set of Representatives to Independent Set of Representatives
  1. The doctest needs to be marked as optional.
  1. There should be more examples.
  1. Whether or not GLPK is installed, the import from sage.numerical.mip import MIP fails. I suppose this is a rather old patch, should MIP be MixedIntegerLinearProgram?
  1. "rebased for 4.3.rc1" means 4.3.rc0 + #7640 + #7674 + #7673, all of which are merged in rc1.

comment:8 Changed 11 years ago by ncohen

This is a rather old patch. I'll update it immediately !

comment:9 Changed 11 years ago by ncohen

  • Status changed from needs_work to needs_review

Updated !

comment:10 Changed 11 years ago by rlm

  • Status changed from needs_review to needs_work

You haven't really addressed #2.

comment:11 Changed 11 years ago by rlm

(item 2 not ticket # 2)

comment:12 Changed 11 years ago by ncohen

  • Status changed from needs_work to needs_review

This one should be better then :-)

Changed 11 years ago by ncohen

comment:13 Changed 11 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

comment:14 Changed 11 years ago by mhansen

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