Implement an efficient graph colouring algorithm

[karlnapf]

For graphs represented as large, sparse matrices. Since this should be efficient, a fast greedy algorithm is needed. Alternatively, integrate a library that can do that. Task includes a review on possible methods and to choose the "best". This is a preliminary task of the GSoC 2013 project idea of estimating large-scale Gaussian densities.

[vikkamath]

are you open to parallel algorithms for this?

[karlnapf]

We are totally open for parallel algorithms - assuming that you mean single-machine parallel. Preferably with openmp What method do you have in mind?

BTW: We aim to use this on large (and sparse) graphs (>100000 nodes and more)

[charnugagoo]

Hi, karlnapf: I am the first time here. If I implement this algorithm, should I use shogun api or write my own? Thanks

[charnugagoo]

Hi, karlnapf: I am so willing to try my algorithm that I cannot wait for your reply :p My greedy algorithm is like topology sort with priority queue, which is nearly linear on sparse graphs. (O(avg_degree*node_number), 3s for 100,000 nodes and 10,000,000 edges) I have implement it as an independent cpp program. For I am the first time here, I don't know the workflow, how to submit it.

Thanks~

[karlnapf]

Hi Well, I was sleeping :) First of all, do you have a description of the method?
The complexity sounds exactly as what we want - how does it depend on the number of colors?

We merge code with pull requests on github, so you have to fork our repository, pull it to your computer, modify locally, commit locally, push, and send us a pull request.

I suggest you create a new class CSparseGraphColoring in the statistics folder of shogun. See any other shogun class or the development readme on how to do this. The next steps are unit-tests, an example, and documentation.

You can ask for details on IRC (heiko)

[charnugagoo]

Hi, karlnapf:

My algorithm is to greedy coloring nodes in sequence, from each node with max/min degree in each sub-graph to their neighbors using a priority queue, just like topology sort. I tried this algorithm on multiple data sets. On dataset of 100,000 nodes and 10,000,000 edges, 270+ max-degrees, programes use 47 colors.

I am learning the workflow and structure of shogun. I think I would come back fast after learning.

Thanks~

[karlnapf]

Hi that sounds good. So grab a copy of shogun and send a pull request on github. Also, I would love to read a paper on the algorithm - could you provide one? Heiko

[Froskekongen]

It should be mentioned that it is preferable to do an d-distance colouring of the graph induced by the sparse matrix directly. Computing the power of a large sparse matrix before doing a 1- or 2-distance colouring bloats the memory usage unnecessarily.

[karlnapf]

Agreed!

[towelenee]

https://github.com/shogun-toolbox/shogun/pull/1116 I write some code for your problem, but it something like prototype.

[karlnapf]

closing as we are now using colpack

[Froskekongen]

I would advise against using ColPack as the final solution - as far as I remember it only supports up to 2-distance colouring. This makes it really inefficient if you are to make d in the d-distance colouring large, since a power of the adjacency matrix would explicitly need to be computed.

[karlnapf]

@Froskekongen yeah that is true, but what would be the alternatives? This one at least works for now. What are you doing in KRYLSTAT?

[Froskekongen]

I use ColPack in KRYLSTAT, too, but I was exploring alternatives. In this article: http://www.stce.rwth-aachen.de/twiki/pub/Teaching/Summer10/SemCPSC/jacobian_color.pdf, there is an alternative for 2-distance colouring on page 22. It should be easy to add one more inner loop to extend it to 3-distance colouring, and perhaps it's possible to extend it to d-distance by a some clever recursion? I really didn't have time to explore this fully when doing this myself.

[karlnapf]

Nice, thanks for that.

@lambday feel free to have a look at this. It's not top priority now (since the other stuff works - at least with reasonably conditioned matrices), but it might be really useful to continue on this in a bit.

[lambday]

@karlnapf @Froskekongen Yeah I noticed that while implementing. I will give it a read and discuss here regarding possible implementations.

[mmurrs]

Is this issue still open for contribution?

[karlnapf]

You could have a go, but it is very low priority. I suggest to pick something else

[mmurrs]

Ok, thanks for the quick response. Do you have a suggestion for a "good first issue" that would be better to work on?

[karlnapf]

sort them by date and pick the most recent one, there are plenty of those ...