giraph-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Eli Reisman (JIRA)" <>
Subject [jira] [Commented] (GIRAPH-157) Vertex to perform graph coloring on simple, connected, undirected graphs and related test.
Date Thu, 07 Jun 2012 17:35:24 GMT


Eli Reisman commented on GIRAPH-157:

Sorry, that quote is in response to someone else's comment about polynomial time.

This is an NP-complete problem. My claims for speed were concerning running the Giraph test
suite and having the test pass without undue delays in the "mvn verify" runs. The graphs I
have tested on all came out with a correct answer, but I lack larger graphs to test it on
that I know for sure the coloring of.

When I have more time (soon I hope) if anyone is interested I can attempt to use some tools
I have located on the net to create some graphs that I can predict the minimal coloring of,
and test it on those. Small experiments to this effect so far have gone well, but as I said
I have not had time to come back to this in a while.

Here's my take on the upsides of this graph coloring patch, same as before:

- the patch passes the tests and again doesn't seem to slow Giraph/Hadoop down during "mvn
verify". When it comes to the coloring job, your speed results will vary with the size and
complexity of the graph involved.

- the patch implements a small and simple algorithm to do this work, so if I have not come
up with a good solution, it should (I thought it would?) be easy for someone smarter than
me to help me fix it.

- When I looked into this problem, I did not think I could discover a way around NP-complete
problem (why does everyone think this was my goal?) I just wanted to come up with an algorithm
that could be implemented "thinking like a vertex" via Giraph instead of more traditional
implementations. I assumed it might be clearer to read or reason about in this form compared
to more traditional methods. No big dreams on this one other than that ;)

In conclusion,

If anyone can help me make this better, or just knows whats wrong with it, or can say they
have looked at it and can't verify if its right or wrong without more testing, or has bigger
graph data you know the correct minimal coloring of that I can test on, please post! Whats
the next move here?

Thanks for posting Sebastian, I welcome any advice or help!

PS: If I think of a way to solve NP-complete problems, I will be posting that in a separate

> Vertex to perform graph coloring on simple, connected, undirected graphs and related
> ------------------------------------------------------------------------------------------
>                 Key: GIRAPH-157
>                 URL:
>             Project: Giraph
>          Issue Type: Test
>          Components: examples, test
>    Affects Versions: 0.2.0
>            Reporter: Eli Reisman
>            Assignee: Eli Reisman
>            Priority: Trivial
>              Labels: newbie
>         Attachments: GIRAPH-157-2.patch, GIRAPH-157.patch
> Hi. I am attempting to learn the Hadoop and Giraph codebases and wanted to write a simple
client application for Giraph to help me learn the ins and outs of it. This is a simple unit
test and vertex modeled after the ConnectedComponentsVertex and related test. The vertex test
runs whenever you run the "mvn test" or "mvn verify" suite of tests. When finished processing,
each vertex will have an integer value that is its color.
> This is a pretty simple implementation, and although I have tested it on a number of
small graphs of varied trickiness and it seems to rapidly arrive at a minimal coloring, its
hard (for me at least) to guess which possible coloring it will arrive at and I have no idea
how it will do on really big graphs yet without finding some more pre-colored larger test
graphs to try it on. Ideas anyone?
> Anyway, it was fun to put this together, and I'd be happy to improve it or receive some
help or advice to further the cause. Thanks again, I am hoping this will be the first of many
(hopefully more useful) contributions!
> Eli

This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:!default.jspa
For more information on JIRA, see:


View raw message