[ https://issues.apache.org/jira/browse/GIRAPH-157?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13290149#comment-13290149 ]
Sebastian Schelter commented on GIRAPH-157: ------------------------------------------- You tackle an NP-complete problem and you state 'I make no claims its in polynomial time'. Even quadratic time is infeasible for not-so-large graphs. > 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