Adding greedy coloring algorithms to NetworkX
Henrik Haugbølle
Hi all,
We are three students from the IT University of Copenhagen who would like to implement a variety of greedy graph coloring algorithms[1] into NetworkX.
We have read the documentation[2] regarding testing and development (how we must fork, create feature branches, request code reviews, etc), and are currently getting familiar with the source and how other algorithms are implemented.
Our objective is to implement ~5 greedy coloring algorithms during the next few months. And we have a few questions on how to approach this using best practices in the community.
As a starting point, we are thinking about creating the folder networkx/algorithms/coloring which should contain the algorithms. Is this sensible or is there a better way to structure it?
Version-control-vise we will implement each of the algorithms in different branches of our fork, so they can be reviewed (and hopefully pulled into the trunk) separately. Are we missing anything here?
As for the algorithms themselves, we are considering the following approach. An algorithm takes a graph G as input, and returns a “colored” graph G’ whose nodes now each contain a color-attribute. Furthermore we would provide utility methods to return e.g. the number of colors used to color the graph.
We would love some feedback on how we should approach this project and whether our initial thoughts fits the practices of the community.
Kind regards,
Jan, Christian, & Henrik
Aric Hagberg
algorithms.
It looks like you have found the correct documentation and process for
getting new code into NetworkX and your proposal to make a fork and
add in networkx/algorithms/coloring is good.
You might consider having the functions return a dictionary with nodes
as keys and colors (or integers) as labels. That might be more
efficient than creating a new "colored graph" or than modifying the
original input graph.
Let us know when you have some code for us to review and comment on.
Best Wishes,
Aric
> 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 post to this group, send email to networkx...@googlegroups.com.
> Visit this group at http://groups.google.com/group/networkx-discuss.
> For more options, visit https://groups.google.com/groups/opt_out.
Henrik Haugbølle
I think you are right about the return of the functions, and that the dictionary approach would be both more efficient and flexible.
We will keep you posted as soon as we have some code! :)
Moritz Emanuel Beber
On 02/11/2014 02:49 PM, Henrik Haugbølle wrote:
>
>
> I think you are right about the return of the functions, and that the
> dictionary approach would be both more efficient and flexible.
>
discussion converged towards a list of sets of nodes as the returned
structure (or a generator that returns sets). Thus the "colour" would be
given by the order of the sets. Additionally, you can cover corner cases
where a node has more than one colour (is part of more than one set).
Happy hacking,
Moritz
Henrik Haugbølle
We are new to greedy coloring algorithms, so we are having a hard time constructing an example where a node has more than one colour. If you know of any, it would be of great help if you could provide it :)
Moritz Emanuel Beber
On 02/11/2014 04:19 PM, Henrik Haugbølle wrote:
> Hi Moritz,
>
> Thank you for the feedback. That definitely sounds feasible in
> situations where one would like to actually draw the graph! It's noted.
>
> We are new to greedy coloring algorithms, so we are having a hard time
> constructing an example where a node has more than one colour. If you
> know of any, it would be of great help if you could provide it :)
>
considered a failure. I just wanted to say that in principle the list of
sets structure can allow for that, or you could provide one set of nodes
with unsolvable conflicts, for example. I wanted to point out the
flexibility rather than that it was actually needed.
Cheers,
Moritz
Henrik Haugbølle
Thank you for the clarification - and it's a good point!
Henrik Haugbølle
We are still in the initial phase of researching greedy coloring algorithms. But to ensure that we follow the NetworkX practices, we have implemented the simple first-fit algorithm using maximum degree ordering.
Our implementation is online in our forked repository and can be found here (direct link: https://github.com/itu-sass-s2014/networkx/blob/greedy-coloring-max-degree-first/networkx/algorithms/coloring/maxdegree.py).
We would like to provide all 5 algorithms before we initiate a pull request (for code-review etc). But we would very much appreciate any feedback.
Kind regards,
Jan, Christian & Henrik
Moritz Emanuel Beber
Hi Aric, Moritz, and the rest of the NetworkX community,
We are still in the initial phase of researching greedy coloring algorithms. But to ensure that we follow the NetworkX practices, we have implemented the simple first-fit algorithm using maximum degree ordering.
Our implementation is online in our forked repository and can be found here (direct link: https://github.com/itu-sass-s2014/networkx/blob/greedy-coloring-max-degree-first/networkx/algorithms/coloring/maxdegree.py).
We would like to provide all 5 algorithms before we initiate a pull request (for code-review etc). But we would very much appreciate any feedback.
Just my 2 cents, though, Dan and Aric should decide what they view as best practice.
Moritz