commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Simone Tripodi (JIRA)" <>
Subject [jira] [Commented] (SANDBOX-333) Graph coloring implementation
Date Tue, 28 Jun 2011 10:18:17 GMT


Simone Tripodi commented on SANDBOX-333:

That's simply amazing Marco, thanks for contributing!
I raw the patch and looks good, the only part I like less is {{GraphColoring}}, line 79:

int deg = ( (Set<V>) g.getConnectedVertices( v ) ).size();

That could be not always true, because users could provide their {{Graph}} implementation
wrapping databases/NoSQL/something else... so what we can do is adding a method {{Integer
getDegree( V )}} - having it makes sense also for other algorithms implementations... WDYT?

> Graph coloring implementation
> -----------------------------
>                 Key: SANDBOX-333
>                 URL:
>             Project: Commons Sandbox
>          Issue Type: Improvement
>          Components: Graph
>            Reporter: Marco Speranza
>            Priority: Minor
>         Attachments: GraphColoring.patch
> Hi all, I just implemented a simple version of graph coloring problem. 
> This implementation contains the chromatic number ( is the minimal number of colors needed
to color each vertex such that no two adjacent vertices share the same color) and also the
coloring algorithm.

This message is automatically generated by JIRA.
For more information on JIRA, see:


View raw message