Context Navigation

← Previous Ticket
Next Ticket →

#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 10 years ago.: rebased for 4.3.rc1
trac_6764.patch (5.3 KB) - added by ncohen 10 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 10 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 10 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 10 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 10 years ago by ncohen

Description modified (diff)

comment:5 Changed 10 years ago by ncohen

Description modified (diff)

comment:6 Changed 10 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 10 years ago by rlm

Attachment ISR.patch added

rebased for 4.3.rc1

comment:7 Changed 10 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

The doctest needs to be marked as optional.

There should be more examples.

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?