Opened 12 years ago

Last modified 11 years ago

#6679 closed enhancement

[with patch, needs review] Vertex Coloring, Edge Coloring (uses Linear Programming) — at Version 4

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

Status badges

Description (last modified by ncohen)

Hello everybody !!!

Here are two new functions for the Graph class in Sage : vertex_coloring and edge_coloring.

Those new functions both use Linear programming, so to use them you will have to install the patche AllMIP-2.flattened in #6502 along with the package GLPK :

http://www.sagemath.org/packages/optional/

If you want them to be ever more efficient, you can also install COIN-OR/CBC ( from #6603 ) with this line :

sage -f http://www-sop.inria.fr/members/Nathann.Cohen/cbc-2.3.spkg

I hope I learned what I had to with my previous patch, as I hope you will find those functions sufficiently and correctly documented. These functions should be ---way--- more efficient than the previous ones, regardless of the Linear Solver you chose to use.

Change History (6)

Changed 12 years ago by ncohen

First patch !

Changed 12 years ago by ncohen

First patch !

comment:1 Changed 12 years ago by ncohen

Hmmm... The two patches coloring-1 and coloring-1.2 are exactly identical, but I do not know how to remove the second one ;

comment:2 Changed 12 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 12 years ago by ncohen

  • Description modified (diff)

comment:4 Changed 12 years ago by ncohen

  • Description modified (diff)
Note: See TracTickets for help on using tickets.