incubator-giraph-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Eli Reisman (Updated) (JIRA)" <>
Subject [jira] [Updated] (GIRAPH-157) Vertex to perform graph coloring on simple, connected, undirected graphs and related test.
Date Sat, 24 Mar 2012 01:23:25 GMT


Eli Reisman updated GIRAPH-157:

    Attachment: GIRAPH-157-2.patch

This is an update to fix the initialization issue that IntIntNullIntVertex had (see GIRAPH-161)
and that therefore my variation IntIntNullTextVertex carried with regard to possible null
initialization of edges and messages. See GIRAPH-161 for details. I'm still looking for larger
undirected, connected, simple graphs in line input format like <vertex id> <outboundEdge>
[outboundEdge...]<END_OF_LINE> that we know the correct chromatic number of to test
this thing on larger input graphs. So far, every graph I test it with is given a correct minimal
coloring. Lets break this thing, anyone?
> 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