Mailing-List: contact issues-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: issues@commons.apache.org
Date: Sat, 2 Jul 2011 20:22:21 +0000 (UTC)
From: "Simone Tripodi (JIRA)" <jira@apache.org>
To: issues@commons.apache.org
Message-ID: 
 <1863002545.260.1309638141857.JavaMail.tomcat@hel.zones.apache.org>
In-Reply-To: 
 <601596857.9066.1309539988439.JavaMail.tomcat@hel.zones.apache.org>
Subject: [jira] [Commented] (SANDBOX-335) [Graph] Graph Coloring:
 Backtracking algorithm
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ 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