Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Independent Set of Representatives #6764

Closed
nathanncohen mannequin opened this issue Aug 16, 2009 · 16 comments
Closed

Independent Set of Representatives #6764

nathanncohen mannequin opened this issue Aug 16, 2009 · 16 comments
Assignees
@rlmill
Labels
c: graph theory p: major / 3 t: enhancement
Milestone
sage-4.3

Comments

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Aug 16, 2009

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 ;-)

Component: graph theory

Author: Nathann Cohen

Reviewer: Robert Miller

Merged: sage-4.3.rc1

Issue created by migration from https://trac.sagemath.org/ticket/6764
@nathanncohen nathanncohen mannequin added this to the sage-4.3.1 milestone Aug 16, 2009
@nathanncohen nathanncohen mannequin assigned rlmill Aug 16, 2009
@aghitza aghitza changed the title Independent Set of Reresentatives (uses Linear Programming) Independent Set of Representatives (uses Linear Programming) Aug 19, 2009
@nathanncohen

This comment has been minimized.

Sign in to view
@nathanncohen nathanncohen mannequin changed the title Independent Set of Representatives (uses Linear Programming) Independent Set of Representatives Aug 27, 2009
@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Aug 31, 2009

comment:3

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

@nathanncohen

This comment has been minimized.

Sign in to view
@nathanncohen

This comment has been minimized.

Sign in to view
@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Sep 6, 2009

comment:6

Just updated, everything is ready for review :-)

Thanks again for your help !

Nathann

@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 15, 2009

rebased for 4.3.rc1

@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 15, 2009

comment:7

Attachment: ISR.patch.gz

  1. The doctest needs to be marked as optional.

  2. There should be more examples.

  3. 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?

  4. "rebased for 4.3.rc1" means 4.3.rc0 + shortest_path should not use NetworkX if the underlying graph is a c_graph #7640 + fix bug in c_graph backends in_degree and out_degree #7674 + implement Dijkstra's algorithm for C graphs #7673, all of which are merged in rc1.

@rlmill rlmill mannequin added s: needs work and removed s: needs review labels Dec 15, 2009
@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Dec 15, 2009

comment:8

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

@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Dec 15, 2009

comment:9

Updated !

@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 15, 2009

comment:10

You haven't really addressed #2.

@rlmill rlmill mannequin added s: needs work and removed s: needs review labels Dec 15, 2009
@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 15, 2009

comment:11

(item 2 not ticket # 2)

@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Dec 16, 2009

comment:12

This one should be better then :-)

@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Dec 16, 2009

Attachment: trac_6764.patch.gz

@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 16, 2009

Reviewer: Robert Miller

@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 16, 2009

Author: Nathann Cohen

@mwhansen
Copy link
Contributor

Merged: sage-4.3.rc1

@mwhansen mwhansen modified the milestones: sage-4.3.1, sage-4.3 Dec 20, 2009
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@rlmill rlmill

Labels
c: graph theory p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-4.3
Development

No branches or pull requests
1 participant
@mwhansen