New Graph Coloring Library

[Rhyd Lewis]

Just wanted to let the NetworkX community know about a new library that I've developed for graph coloring. 

GCol is an open-source Python library built on top of NetworkX. It provides high-performance algorithms for node coloring, edge coloring, face coloring, equitable coloring, weighted coloring, precoloring, and maximum independent set identification. It also offers several tools for solution visualization.

Most of the methods provided by GCol are not possible in NetworkX.

Documentation is here, https://gcol.readthedocs.io/en/latest/ and the library can be installed using pip. 

[Thomas Balstrøm]

Hi Rhyd,

Thanks for pointing to this resource. I've installed the library successfully. Meanwhile, I'm informed that your method hasn't been implemented for directed graphs. Will it be considered?

Thank you,

Thomas Balstroem,

Dept. of Geoscience 

Univ. of Copenhagen, Denmark

[Russell Jurney]

This is neat! Can you outline some practical problems that graph coloring can be used for? I want to index this and come back to it when I face that kind of problem :)

Russell

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/networkx-discuss/843be82d-e9ea-4dec-b324-cec6f8b8a604n%40googlegroups.com.

[thomasb...@gmail.com]

Sure. My interest is in hydrologic stream networks and their topological ordering. I’ve used NetworkX to assign so called Strahler orders to a stream network’s edges, and I want to color them as visualized in this reference: Strahler number - Wikipedia. I’m using a GIS (ArcGIS Pro) to visualize the Strahler stream orders according to their true geographic location, but I’m curious how a conceptual representation of a stream hierarchy may look like, also.

Thanks, Thomas

To view this discussion visit https://groups.google.com/d/msgid/networkx-discuss/CANSvDjpNu384T4SVVU5J0%2BbYJp%2BLvq%3Damcg7p6et%2BrqKT4sc2w%40mail.gmail.com.

[Rhyd Lewis]

Hi Thomas,

Thanks for thr feedback, and good to hear you've got it working. I've deliberately avoided directed graphs in the library because, from a coloring perspective, directions don't really make sense. (If we have an arc (u,v) but no arc (v,u) should u and v be different colors or not?). If you have a directed graph, one alternative is to just to remove the directions on the graph before applying GCol's routines. 

There's also another optimisation problem called "oriented coloring", which deals with directed graphs, but it is quite different to "normal" graph coloring and is not in this library (yet...)

I'd be glad to hear about your uses of the library.

Best Wishes,

Rhyd