Databases
StackOverflow2013
Postsdbo
POC++ Graph Vertex Coloring Library or Source Code
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POC++ Graph Vertex Coloring Library or Source Code
    primarykey
    data
    text
    <p>Is there a C++ (or any other language) library with a portfolio of algorithms for the problem of <a href="http://en.wikipedia.org/wiki/Graph_coloring" rel="nofollow noreferrer">graph coloring</a>?</p> <p>There are of course naive greedy vertex coloring algorithms, but I'm interested in more interesting algorithms like:</p> <ol> <li>Algorithms mentioned in the "Exact Algorithms" section of the <a href="http://en.wikipedia.org/wiki/Graph_coloring" rel="nofollow noreferrer">wiki</a></li> <li>Approximation algorithms that take advantage of special graph properties like the graph being <a href="http://en.wikipedia.org/wiki/Planar_graph" rel="nofollow noreferrer">planar</a> or a <a href="http://en.wikipedia.org/wiki/Unit_disk_graph" rel="nofollow noreferrer">unit disk graph</a>.</li> <li>Algorithms that find the <a href="http://en.wikipedia.org/wiki/Fractional_coloring" rel="nofollow noreferrer">fractional coloring</a> of a graph.</li> </ol> <p>That last one is of particular importance to me.</p> <p>What I found so far is the list on <a href="http://www.cs.sunysb.edu/~algorith/files/vertex-coloring.shtml" rel="nofollow noreferrer">this page</a> but none of them have any of the above algorithms. Moreover, the best one is <a href="http://webdocs.cs.ualberta.ca/~joe/Coloring" rel="nofollow noreferrer">Joe Culberson's Graph Coloring code</a> and that was implemented in late 90's, so is very much outdated in terms of not having a documented API (not that this is important for what this question is about, but I thought I'd mention it).</p> <p>There's the <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4621641" rel="nofollow noreferrer">Koala graph coloring library</a> that has the spirit of what I'm looking for, but if you look at their <a href="http://koalalib.org/wiki/index.php/KoalaWiki" rel="nofollow noreferrer">source code</a> it has not delivered on the promise just yet. It appears to be in very early stages of development.</p> <p>Other general graph libraries are mentioned in <a href="https://stackoverflow.com/questions/2751826/which-c-graph-library-should-i-use">this stackoverflow question</a>. They include:</p> <ol> <li><a href="http://www.graphviz.org/" rel="nofollow noreferrer">Graphviz</a></li> <li><a href="http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/index.html" rel="nofollow noreferrer">Boost Graph Library</a></li> <li><a href="http://lemon.cs.elte.hu/trac/lemon" rel="nofollow noreferrer">Lemon</a></li> <li><a href="http://igraph.sourceforge.net/introduction.html" rel="nofollow noreferrer">igraph</a></li> <li><a href="http://www.ogdf.net/ogdf.php?id=" rel="nofollow noreferrer">OGDF</a></li> </ol> <p>I should note that I use the <a href="http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/index.html" rel="nofollow noreferrer">Boost Graph Library</a> for a lot of things. In fact, it provides a naive vertex coloring implementation. Joe Culberson's code (mentioned above) does much more.</p> <p>The following is a list of graph coloring code, I've found (and tested in most cases) but they still mostly fall short in terms of the three algorithm classes above.</p> <ol> <li><a href="http://code.google.com/p/graphcol" rel="nofollow noreferrer">GraphCol</a> - documentation is not in English, sigh.</li> <li><a href="http://code.google.com/p/planarity" rel="nofollow noreferrer">Planarity</a> - contains a coloring algorithm that guarantees a 5-coloring or better for planar graphs.</li> <li><a href="http://code.google.com/p/graph-coloring/" rel="nofollow noreferrer">Graph-Coloring</a> - appears to be a re-implementation of a small number of algorithms already implemented by Joe Culberson (above).</li> </ol>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USAlan Turing
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POC++ Graph Vertex Coloring Library or Source Code
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POC++ Graph Vertex Coloring Library or Source Code
      1. USAlan Turing
      1. VTFavorite
    3. VO
      singulars
      1. POC++ Graph Vertex Coloring Library or Source Code
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload