8

Is there a C++ (or any other language) library with a portfolio of algorithms for the problem of graph coloring?

There are of course naive greedy vertex coloring algorithms, but I'm interested in more interesting algorithms like:

  1. Algorithms mentioned in the "Exact Algorithms" section of the wiki
  2. Approximation algorithms that take advantage of special graph properties like the graph being planar or a unit disk graph.
  3. Algorithms that find the fractional coloring of a graph.

That last one is of particular importance to me.

What I found so far is the list on this page but none of them have any of the above algorithms. Moreover, the best one is Joe Culberson's Graph Coloring code 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).

There's the Koala graph coloring library that has the spirit of what I'm looking for, but if you look at their source code it has not delivered on the promise just yet. It appears to be in very early stages of development.

Other general graph libraries are mentioned in this stackoverflow question. They include:

  1. Graphviz
  2. Boost Graph Library
  3. Lemon
  4. igraph
  5. OGDF

I should note that I use the Boost Graph Library for a lot of things. In fact, it provides a naive vertex coloring implementation. Joe Culberson's code (mentioned above) does much more.

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.

  1. GraphCol - documentation is not in English, sigh.
  2. Planarity - contains a coloring algorithm that guarantees a 5-coloring or better for planar graphs.
  3. Graph-Coloring - appears to be a re-implementation of a small number of algorithms already implemented by Joe Culberson (above).
Improve this question
1
  • Koala is still being developed on top of the structures provided by the NetworKit library. Commented Dec 7, 2023 at 9:49

4 Answers 4

Reset to default
3

There's some good ones at http://rhydlewis.eu/gcol/. These correspond to a portfolio of algorithms reviewed and tested in my book:

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. https://link.springer.com/book/10.1007/978-3-030-81054-2

These include greedy, backtracking and metaheuristic approaches. I've included compilation instructions etc. in the above link.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Maybe you can help yourself with the Boost Graph Library.

Improve this answer

1 Comment

I love BGL, and it does provide one algorithm for vertex coloring, but it's a naive one and Joe Culberson's code (mentioned in the question) does much more. Moreover, BGL certainly doesn't have anything like the three "more interesting" algorithms I mentioned that I'm looking for.
0

GCol is an open-source Python library for graph coloring. It has exact and heuristic algorithms for node coloring, edge coloring, equitable coloring, weighted coloring, precoloring, and maximum independent set indentification.

Full disclosure: I wrote and maintain the library. It is based on my 2021 book:

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5.

Improve this answer

Comments

-1

You can try CXXGraph library. It contains some useful algorithm on Graph

Improve this answer

1 Comment

No coloring, though

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.