[
https://issues.apache.org/jira/browse/GIRAPH-157?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13291150#comment-13291150
]
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 JIRA ;)
> Vertex to perform graph coloring on simple, connected, undirected graphs and
> related test.
> ------------------------------------------------------------------------------------------
>
> Key: GIRAPH-157
> URL: https://issues.apache.org/jira/browse/GIRAPH-157
> 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:
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
