commons-issues mailing list archives

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

    [ https://issues.apache.org/jira/browse/SANDBOX-335?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13059118#comment-13059118
] 

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: https://issues.apache.org/jira/browse/SANDBOX-335
>             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: http://www.atlassian.com/software/jira

        

Mime
View raw message