Sebastian Schelter commented on GIRAPH-157:

Hello Eli,

I'm not sure how your algorithm works, but finding a minimal coloring for a 
graph is an NP-hard problem, so I doubt your implementation really achieves 
this (at least in polynomial time).

Could you sketch the idea of the algorithm in pseudocode for us?

> 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.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: 
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply via email to