Opened 11 years ago
Closed 10 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 )
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)
Change History (16)
comment:1 Changed 11 years ago by
- 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
- 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
- Summary changed from [with patch, needs review] Independent Set of Representatives to [with patch, needs work] Independent Set of Representatives
comment:4 Changed 10 years ago by
- Description modified (diff)
comment:5 Changed 10 years ago by
- Description modified (diff)
comment:6 Changed 10 years ago by
- 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
comment:7 Changed 10 years ago by
- 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, shouldMIP
beMixedIntegerLinearProgram
?
comment:8 Changed 10 years ago by
This is a rather old patch. I'll update it immediately !
comment:10 Changed 10 years ago by
- Status changed from needs_review to needs_work
You haven't really addressed #2.
comment:11 Changed 10 years ago by
(item 2 not ticket # 2)
comment:12 Changed 10 years ago by
- Status changed from needs_work to needs_review
This one should be better then :-)
Changed 10 years ago by
comment:13 Changed 10 years ago by
- Reviewers set to Robert Miller
- Status changed from needs_review to positive_review
comment:14 Changed 10 years ago by
- 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
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