commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Simone Tripodi (JIRA)" <>
Subject [jira] [Commented] (SANDBOX-335) [Graph] Graph Coloring: Backtracking algorithm
Date Sat, 02 Jul 2011 20:22:21 GMT


Simone Tripodi commented on SANDBOX-335:

Nice work Marco, very nice work!
I have anyway some minor note I'd like you fix before applying the patch:

 * in the {{GraphColoringBacktraking#backtraking(int)}} the {{else}} clause can be moved outside
the _else_, I think you can group the boolean clauses in just one;
 * just a hint/idea: in the {{GraphColoring#backTrackingColoring()}} method, can we use a
{{Queue}} of colors instead of {{Lits}}? Consuming it would make easier to catch the case
when available colors for the algorithm are exhausted;
 * in the {{GraphColoingBackTrackingTestCase#testSudokuWithConstraints()}} method you used
a {{StringBuilder}} but inside the {{add(String)}} method you used the string concatenation,
you can safely continue use the {{add(String)}} method instead;
 * javadoc for {{<V,E>}} are missing in the bigger part of cases, you can copy them
from {{Graph}} interface.

Many thanks in advance!!!

> [Graph] Graph Coloring: Backtracking algorithm
> ----------------------------------------------
>                 Key: SANDBOX-335
>                 URL:
>             Project: Commons Sandbox
>          Issue Type: Improvement
>          Components: Graph
>            Reporter: Marco Speranza
>            Priority: Minor
>         Attachments: GraphColoring-BackTrackingAlgo-Fixed.patch, GraphColoring-BackTrackingAlgo.patch
> Here is an little enhancement for graph coloring problem. I implemented an bruteforce
algorithm that uses the backtracking technique to find the exact solution for the m-coloring
problem (m is the maximum number of usable colors).  

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


View raw message