Author: simonetripodi Date: Tue Jul 5 21:30:30 2011 New Revision: 1143206 URL: http://svn.apache.org/viewvc?rev=1143206&view=rev Log: [SANDBOX-338] [Graph Coloring] Generic iterable set of color - patch submitted by Marco Speranza
Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java (with props) commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java (with props) Removed: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoingBackTrackingTestCase.java Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java?rev=1143206&r1=1143205&r2=1143206&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java (original) +++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java Tue Jul 5 21:30:30 2011 @@ -31,13 +31,14 @@ import org.apache.commons.graph.Vertex; * Maintains the color for each {@link Vertex} and the required number of colors for {@link Graph} coloring. * * @param <V> the Graph vertices type. + * @param <C> the Color type. */ -public final class ColoredVertices<V extends Vertex> +public final class ColoredVertices<V extends Vertex, C> { - private final Map<V, Integer> coloredVertices = new HashMap<V, Integer>(); + private final Map<V, C> coloredVertices = new HashMap<V, C>(); - private final List<Integer> usedColor = new ArrayList<Integer>(); + private final List<C> usedColor = new ArrayList<C>(); /** * This class can be instantiated only inside the package @@ -53,7 +54,7 @@ public final class ColoredVertices<V ext * @param v the {@link Vertex} for which storing the color. * @param color the input {@link Vertex} color. */ - void addColor( V v, Integer color ) + void addColor( V v, C color ) { coloredVertices.put( v, color ); int idx = usedColor.indexOf( color ); @@ -74,7 +75,7 @@ public final class ColoredVertices<V ext */ void removeColor( V v ) { - Integer color = coloredVertices.remove( v ); + C color = coloredVertices.remove( v ); usedColor.remove( color ); } @@ -84,7 +85,7 @@ public final class ColoredVertices<V ext * @param v the {@link Vertex} for which getting the color. * @return the color associated to the input {@link Vertex}. */ - public Integer getColor( V v ) + public C getColor( V v ) { if ( v == null ) { Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java?rev=1143206&r1=1143205&r2=1143206&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java (original) +++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java Tue Jul 5 21:30:30 2011 @@ -6,6 +6,7 @@ import java.util.List; import java.util.Set; import org.apache.commons.graph.Edge; +import org.apache.commons.graph.GraphException; import org.apache.commons.graph.UndirectedGraph; import org.apache.commons.graph.Vertex; @@ -30,8 +31,8 @@ import org.apache.commons.graph.Vertex; /** * Contains the graph coloring implementation. This is a greedy implementation for the graph coloring problem. This - * algorithm couldn't find the mimium coloring for the given graph since this is an NP-complete problem. <a - * href="http://scienceblogs.com/goodmath/2007/06/graph_coloring_algorithms_1.php"> + * algorithm couldn't find the mimium coloring for the given graph since this is an NP-complete problem. <a href= + * "http://scienceblogs.com/goodmath/2007/06/graph_coloring_algorithms_1.php"> */ public final class GraphColoring { @@ -41,12 +42,14 @@ public final class GraphColoring * * @param <V> the Graph vertices type * @param <E> the Graph edges type + * @param <C> the Color vertices type * @param g The graph. * @return The color - vertex association. */ - public static <V extends Vertex, E extends Edge> ColoredVertices<V> greedyColoring( UndirectedGraph<V, E> g ) + public static <V extends Vertex, E extends Edge, C> ColoredVertices<V, C> greedyColoring( UndirectedGraph<V, E> g, + Set<C> colors ) { - final ColoredVertices<V> coloredVertices = new ColoredVertices<V>(); + final ColoredVertices<V, C> coloredVertices = new ColoredVertices<V, C>(); // decreasing sorting all vertices by degree. final UncoloredOrderedVertices<V> uncoloredOrderedVertices = new UncoloredOrderedVertices<V>(); @@ -57,10 +60,16 @@ public final class GraphColoring } // search coloring - Iterator<V> it = uncoloredOrderedVertices.iterator(); - for ( int currentColorIndex = 0; it.hasNext(); currentColorIndex++ ) + Iterator<C> colorsIt = colors.iterator(); + while ( it.hasNext() ) { + if ( !colorsIt.hasNext() ) + { + throw new GraphException( "The color set is too small." ); + } + C color = colorsIt.next(); + // this list contains all vertex colore with the current color. List<V> currentColorVertices = new ArrayList<V>(); Iterator<V> uncoloredVtxIterator = uncoloredOrderedVertices.iterator(); @@ -73,7 +82,8 @@ public final class GraphColoring { if ( g.getEdge( currentColoredVtx, uncoloredVtx ) != null ) { - // we've found that 'uncoloredVtx' is adiacent to 'currentColoredVtx' + // we've found that 'uncoloredVtx' is adiacent to + // 'currentColoredVtx' foundAnAdjacentVertex = true; break; } @@ -81,10 +91,11 @@ public final class GraphColoring if ( !foundAnAdjacentVertex ) { - // It's possible to color the vertex 'uncoloredVtx', it has no connected vertex into + // It's possible to color the vertex 'uncoloredVtx', it has + // no connected vertex into // 'currentcoloredvtx' uncoloredVtxIterator.remove(); - coloredVertices.addColor( uncoloredVtx, currentColorIndex ); + coloredVertices.addColor( uncoloredVtx, color ); currentColorVertices.add( uncoloredVtx ); } } @@ -101,17 +112,18 @@ public final class GraphColoring * * @param <V> the Graph vertices type * @param <E> the Graph edges type + * @param <C> the Color vertices type * @param g the graph. * @param colors the set of colors. * @param partialColoredVertex subset of vertices already colored. * @return The color - vertex association. */ - public static <V extends Vertex, E extends Edge> ColoredVertices<V> backTrackingColoring( UndirectedGraph<V, E> g, - Set<Integer> colors, - ColoredVertices<V> partialColoredVertex ) + public static <V extends Vertex, E extends Edge, C> ColoredVertices<V, C> backTrackingColoring( UndirectedGraph<V, E> g, + Set<C> colors, + ColoredVertices<V, C> partialColoredVertex ) { - GraphColoringBacktraking<V, E> graphColoringBacktaking = - new GraphColoringBacktraking<V, E>( g, colors, partialColoredVertex ); + GraphColoringBacktraking<V, E, C> graphColoringBacktaking = + new GraphColoringBacktraking<V, E, C>( g, colors, partialColoredVertex ); return graphColoringBacktaking.coloring(); } Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java?rev=1143206&r1=1143205&r2=1143206&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java (original) +++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java Tue Jul 5 21:30:30 2011 @@ -28,20 +28,21 @@ import org.apache.commons.graph.Undirect import org.apache.commons.graph.Vertex; /** - * Graph m-coloring algorithm. This algorithm uses a bruteforce backtraking procedure to find a graph color using a + * Graph m-coloring algorithm. This algorithm uses a bruteforce backtracking procedure to find a graph color using a * predefined set of colors. * * @param <V> the Graph vertices type * @param <E> the Graph edges type + * @param <C> the Color vertices type */ -class GraphColoringBacktraking<V extends Vertex, E extends Edge> +class GraphColoringBacktraking<V extends Vertex, E extends Edge, C> { - final private ColoredVertices<V> coloredVertices; + final private ColoredVertices<V, C> coloredVertices; final private UndirectedGraph<V, E> g; - final private Set<Integer> colors; + final private Set<C> colors; final private List<V> vertexList = new ArrayList<V>(); @@ -50,10 +51,11 @@ class GraphColoringBacktraking<V extends * * @param <V> the Graph vertices type * @param <E> the Graph edges type + * @param <C> the Color vertices type * @param g The graph. * @param colors The list of colors. */ - GraphColoringBacktraking( UndirectedGraph<V, E> g, Set<Integer> colors, ColoredVertices<V> partialColoredVertex ) + GraphColoringBacktraking( UndirectedGraph<V, E> g, Set<C> colors, ColoredVertices<V, C> partialColoredVertex ) { this.coloredVertices = partialColoredVertex; this.g = g; @@ -65,7 +67,7 @@ class GraphColoringBacktraking<V extends * * @return true if all vertices have been colored, false otherwise. */ - ColoredVertices<V> coloring() + ColoredVertices<V, C> coloring() { for ( V v : g.getVertices() ) { @@ -84,7 +86,7 @@ class GraphColoringBacktraking<V extends /** * This is the recursive step. - * + * * @param result The set that will be returned * @param element the element * @return true if there is a valid coloring for the graph, false otherwise. @@ -102,7 +104,7 @@ class GraphColoringBacktraking<V extends int next = currentVertexIndex + 1; V nextVertex = vertexList.get( next ); - for ( Integer color : colors ) + for ( C color : colors ) { coloredVertices.addColor( nextVertex, color ); boolean isDone = backtraking( next ); @@ -116,8 +118,8 @@ class GraphColoringBacktraking<V extends } /** - * Tests if there is some adiacent vertices with the same color. - * + * Tests if there is some adjacent vertices with the same color. + * * @param currentVertex * @return */ @@ -127,13 +129,13 @@ class GraphColoringBacktraking<V extends { return false; } - Integer nextVertecColor = coloredVertices.getColor( currentVertex ); + C nextVertecColor = coloredVertices.getColor( currentVertex ); if ( nextVertecColor == null ) return false; for ( V abj : g.getConnectedVertices( currentVertex ) ) { - Integer adjColor = coloredVertices.getColor( abj ); + C adjColor = coloredVertices.getColor( abj ); if ( adjColor != null && nextVertecColor.equals( adjColor ) ) { return true; Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java?rev=1143206&view=auto ============================================================================== --- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java (added) +++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java Tue Jul 5 21:30:30 2011 @@ -0,0 +1,97 @@ +package org.apache.commons.graph.coloring; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import static org.junit.Assert.assertNotNull; +import static org.junit.Assert.assertTrue; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.Map; +import java.util.Random; +import java.util.Set; + +import org.apache.commons.graph.Edge; +import org.apache.commons.graph.Vertex; +import org.apache.commons.graph.VertexPair; +import org.apache.commons.graph.model.UndirectedMutableGraph; + +/** + * Abstract class used for test coloring. + */ +abstract class AbstractColoringTest +{ + + AbstractColoringTest() + { + } + + /** + * Return a random association with index and a color string in RGB. + */ + protected Map<Integer, String> createColorMap( int numColor ) + { + Map<Integer, String> colorCodes = new HashMap<Integer, String>(); + for ( int i = 0; i < 100; i++ ) + { + Random rnd = new Random( i ); + colorCodes.put( i, String.format( "\"#%2x%2x%2x\"", rnd.nextInt( 255 ), rnd.nextInt( 255 ), rnd.nextInt( 255 ) ) ); + } + return colorCodes; + } + + /** + * Creates a list of integer colors. + * + * @param colorNumber number of colors + * @return the list. + */ + protected Set<Integer> createColorsList( int colorNumber ) + { + Set<Integer> colors = new HashSet<Integer>(); + for ( int j = 0; j < colorNumber; j++ ) + { + colors.add( j ); + } + return colors; + } + + /** + * This method checks if all connected vertices have different colors. + * + * @param g + * @param coloredVertices + */ + protected <V extends Vertex, E extends Edge, C> void checkColoring( UndirectedMutableGraph<V, E> g, + ColoredVertices<V, C> coloredVertices ) + { + for ( E e : g.getEdges() ) + { + VertexPair<V> vp = g.getVertices( e ); + C h = coloredVertices.getColor( vp.getHead() ); + C t = coloredVertices.getColor( vp.getTail() ); + + assertNotNull( h ); + assertNotNull( t ); + assertTrue( !h.equals( t ) ); + } + } + +} Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java ------------------------------------------------------------------------------ svn:eol-style = native Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java ------------------------------------------------------------------------------ svn:keywords = Date Author Id Revision HeadURL Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java ------------------------------------------------------------------------------ svn:mime-type = text/plain Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java?rev=1143206&view=auto ============================================================================== --- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java (added) +++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java Tue Jul 5 21:30:30 2011 @@ -0,0 +1,210 @@ +package org.apache.commons.graph.coloring; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import static org.apache.commons.graph.coloring.GraphColoring.backTrackingColoring; +import static org.apache.commons.graph.utils.GraphUtils.buildBipartedGraph; +import static org.apache.commons.graph.utils.GraphUtils.buildCompleteGraph; +import static org.apache.commons.graph.utils.GraphUtils.buildCrownGraph; +import static org.apache.commons.graph.utils.GraphUtils.buildSudokuGraph; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertNotNull; + +import java.text.DecimalFormat; +import java.text.NumberFormat; +import java.util.logging.Logger; + +import org.apache.commons.graph.model.BaseLabeledEdge; +import org.apache.commons.graph.model.BaseLabeledVertex; +import org.apache.commons.graph.model.UndirectedMutableGraph; +import org.junit.Test; + +/** + * + */ +public class GraphColoringBackTrackingTestCase extends AbstractColoringTest +{ + + @Test + public void testCromaticNumber() + throws Exception + { + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + + BaseLabeledVertex one = new BaseLabeledVertex( "1" ); + BaseLabeledVertex two = new BaseLabeledVertex( "2" ); + BaseLabeledVertex three = new BaseLabeledVertex( "3" ); + + g.addVertex( one ); + g.addVertex( two ); + g.addVertex( three ); + + g.addEdge( one, new BaseLabeledEdge( "1 -> 2" ), two ); + g.addEdge( two, new BaseLabeledEdge( "2 -> 3" ), three ); + g.addEdge( three, new BaseLabeledEdge( "3 -> 1" ), one ); + + ColoredVertices<BaseLabeledVertex, Integer> coloredVertex = new ColoredVertices<BaseLabeledVertex, Integer>(); + coloredVertex.addColor( two, 2 ); + + ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = + backTrackingColoring( g, createColorsList( 3 ), coloredVertex ); + assertNotNull( coloredVertices ); + assertEquals( 3, coloredVertices.getRequiredColors() ); + assertEquals( new Integer( 2 ), coloredVertices.getColor( two ) ); + checkColoring( g, coloredVertices ); + } + + @Test + public void testCromaticNumberComplete() + { + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + + buildCompleteGraph( 100, g1 ); + + ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = + backTrackingColoring( g1, createColorsList( 100 ), new ColoredVertices<BaseLabeledVertex, Integer>() ); + assertNotNull( coloredVertices ); + assertEquals( 100, coloredVertices.getRequiredColors() ); + checkColoring( g1, coloredVertices ); + } + + @Test + public void testCromaticNumberBiparted() + { + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + + buildBipartedGraph( 100, g1 ); + + ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = + backTrackingColoring( g1, createColorsList( 2 ), new ColoredVertices<BaseLabeledVertex, Integer>()); + assertNotNull( coloredVertices ); + assertEquals( 2, coloredVertices.getRequiredColors() ); + checkColoring( g1, coloredVertices ); + } + + @Test + public void testCromaticNumberSparseGraph() + { + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + for ( int i = 0; i < 100; i++ ) + { + g1.addVertex( new BaseLabeledVertex( "" + i ) ); + } + + ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = + backTrackingColoring( g1, createColorsList( 1 ), new ColoredVertices<BaseLabeledVertex, Integer>() ); + assertNotNull( coloredVertices ); + assertEquals( 1, coloredVertices.getRequiredColors() ); + checkColoring( g1, coloredVertices ); + } + + /** + * see <a href="http://en.wikipedia.org/wiki/Crown_graph">wiki</a> for more details + */ + @Test + public void testCrawnGraph() + { + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + + buildCrownGraph( 6, g ); + + ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = + backTrackingColoring( g, createColorsList( 2 ), new ColoredVertices<BaseLabeledVertex, Integer>() ); + assertNotNull( coloredVertices ); + assertEquals( 2, coloredVertices.getRequiredColors() ); + checkColoring( g, coloredVertices ); + } + + @Test + public void testSudoku() + throws Exception + { + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + BaseLabeledVertex[][] grid = buildSudokuGraph( g1 ); + + ColoredVertices<BaseLabeledVertex, Integer> sudoku = + backTrackingColoring( g1, createColorsList( 9 ), new ColoredVertices<BaseLabeledVertex, Integer>() ); + assertNotNull( sudoku ); + checkColoring( g1, sudoku ); + assertEquals( 9, sudoku.getRequiredColors() ); + + // Printout the result + StringBuilder sb = new StringBuilder(); + NumberFormat nf = new DecimalFormat( "00" ); + sb.append( "\n" ); + for ( int i = 0; i < 9; i++ ) + { + for ( int j = 0; j < 9; j++ ) + { + sb.append( "| " + nf.format( sudoku.getColor( grid[i][j] ) ) + " | " ); + } + sb.append( "\n" ); + } + Logger.getAnonymousLogger().fine( sb.toString() ); + } + + @Test + public void testSudokuWithConstraints() + throws Exception + { + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + BaseLabeledVertex[][] grid = buildSudokuGraph( g1 ); + + ColoredVertices<BaseLabeledVertex, Integer> predefinedColor = new ColoredVertices<BaseLabeledVertex, Integer>(); + predefinedColor.addColor( grid[0][0], 1 ); + predefinedColor.addColor( grid[5][5], 8 ); + predefinedColor.addColor( grid[1][2], 5 ); + + ColoredVertices<BaseLabeledVertex, Integer> sudoku = + backTrackingColoring( g1, createColorsList( 9 ), predefinedColor ); + assertNotNull( sudoku ); + checkColoring( g1, sudoku ); + assertEquals( 9, sudoku.getRequiredColors() ); + + assertEquals( new Integer( 1 ), sudoku.getColor( grid[0][0] ) ); + assertEquals( new Integer( 8 ), sudoku.getColor( grid[5][5] ) ); + assertEquals( new Integer( 5 ), sudoku.getColor( grid[1][2] ) ); + + // Printout the result + StringBuilder sb = new StringBuilder(); + NumberFormat nf = new DecimalFormat( "00" ); + sb.append( "\n" ); + for ( int i = 0; i < 9; i++ ) + { + for ( int j = 0; j < 9; j++ ) + { + sb.append( "| " ); + sb.append( nf.format( sudoku.getColor( grid[i][j] ) ) ); + sb.append( " | " ); + } + sb.append( "\n" ); + } + Logger.getAnonymousLogger().fine( sb.toString() ); + + } + +} Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java ------------------------------------------------------------------------------ svn:eol-style = native Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java ------------------------------------------------------------------------------ svn:keywords = Date Author Id Revision HeadURL Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java ------------------------------------------------------------------------------ svn:mime-type = text/plain Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java?rev=1143206&r1=1143205&r2=1143206&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java (original) +++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java Tue Jul 5 21:30:30 2011 @@ -24,9 +24,10 @@ import static org.apache.commons.graph.u import static org.apache.commons.graph.utils.GraphUtils.buildCompleteGraph; import static org.apache.commons.graph.utils.GraphUtils.buildCrownGraph; import static org.apache.commons.graph.utils.GraphUtils.buildSudokuGraph; -import static org.apache.commons.graph.utils.GraphUtils.checkColoring; import static org.junit.Assert.assertEquals; +import java.util.Set; + import org.apache.commons.graph.model.BaseLabeledEdge; import org.apache.commons.graph.model.BaseLabeledVertex; import org.apache.commons.graph.model.UndirectedMutableGraph; @@ -35,14 +36,18 @@ import org.junit.Test; /** * */ -public class GraphColoringTestCase +public class GraphColoringTestCase extends AbstractColoringTest { + private Set<Integer> colors = createColorsList( 11 ); + + @Test public void testCromaticNumber() throws Exception { - UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); BaseLabeledVertex one = new BaseLabeledVertex( "1" ); BaseLabeledVertex two = new BaseLabeledVertex( "2" ); @@ -56,27 +61,29 @@ public class GraphColoringTestCase g.addEdge( two, new BaseLabeledEdge( "2 -> 3" ), three ); g.addEdge( three, new BaseLabeledEdge( "3 -> 1" ), one ); - ColoredVertices<BaseLabeledVertex> coloredVertices = greedyColoring( g ); + ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = greedyColoring( g, colors ); checkColoring( g, coloredVertices ); } @Test public void testCromaticNumberComplete() { - UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); buildCompleteGraph( 100, g1 ); - ColoredVertices<BaseLabeledVertex> coloredVertices = greedyColoring( g1 ); + ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = greedyColoring( g1, createColorsList( 100 ) ); checkColoring( g1, coloredVertices ); } @Test public void testCromaticNumberBiparted() { - UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); buildBipartedGraph( 100, g1 ); - ColoredVertices<BaseLabeledVertex> coloredVertices = greedyColoring( g1 ); + ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = greedyColoring( g1, colors ); checkColoring( g1, coloredVertices ); } @@ -84,13 +91,14 @@ public class GraphColoringTestCase @Test public void testCromaticNumberSparseGraph() { - UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); for ( int i = 0; i < 100; i++ ) { g1.addVertex( new BaseLabeledVertex( "" + i ) ); } - ColoredVertices<BaseLabeledVertex> coloredVertices = greedyColoring( g1 ); + ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = greedyColoring( g1, colors ); assertEquals( 1, coloredVertices.getRequiredColors() ); checkColoring( g1, coloredVertices ); @@ -102,10 +110,11 @@ public class GraphColoringTestCase @Test public void testCrawnGraph() { - UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); buildCrownGraph( 6, g ); - ColoredVertices<BaseLabeledVertex> coloredVertices = greedyColoring( g ); + ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = greedyColoring( g, colors ); checkColoring( g, coloredVertices ); } @@ -113,10 +122,11 @@ public class GraphColoringTestCase public void testSudoku() throws Exception { - UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); + UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = + new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>(); buildSudokuGraph( g1 ); - ColoredVertices<BaseLabeledVertex> sudoku = GraphColoring.greedyColoring( g1 ); + ColoredVertices<BaseLabeledVertex, Integer> sudoku = GraphColoring.greedyColoring( g1, colors ); checkColoring( g1, sudoku ); } Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java?rev=1143206&r1=1143205&r2=1143206&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java (original) +++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java Tue Jul 5 21:30:30 2011 @@ -19,20 +19,10 @@ package org.apache.commons.graph.utils; * under the License. */ -import static org.junit.Assert.assertNotNull; -import static org.junit.Assert.assertTrue; - import java.util.ArrayList; -import java.util.HashMap; import java.util.List; -import java.util.Map; -import java.util.Random; -import org.apache.commons.graph.Edge; import org.apache.commons.graph.GraphException; -import org.apache.commons.graph.Vertex; -import org.apache.commons.graph.VertexPair; -import org.apache.commons.graph.coloring.ColoredVertices; import org.apache.commons.graph.model.BaseLabeledEdge; import org.apache.commons.graph.model.BaseLabeledVertex; import org.apache.commons.graph.model.BaseMutableGraph; @@ -46,7 +36,7 @@ public class GraphUtils /** * Creates a complete graph with nVertices - * + * * @param nVertices number of vertices * @param g graph */ @@ -80,7 +70,7 @@ public class GraphUtils /** * Create a Biparted graph - * + * * @param nVertices number of vertices * @param g graph */ @@ -167,7 +157,7 @@ public class GraphUtils /** * Creates a graph that contains all classic sudoku contratints. - * + * * @return */ public static BaseLabeledVertex[][] buildSudokuGraph( UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> sudoku ) @@ -279,42 +269,6 @@ public class GraphUtils } /** - * This method checks if all connected vertices have different colors. - * - * @param g - * @param coloredVertices - */ - static public <V extends Vertex, E extends Edge> void checkColoring( UndirectedMutableGraph<V, E> g, - ColoredVertices<V> coloredVertices ) - { - for ( E e : g.getEdges() ) - { - VertexPair<V> vp = g.getVertices( e ); - Integer h = coloredVertices.getColor( vp.getHead() ); - Integer t = coloredVertices.getColor( vp.getTail() ); - - assertNotNull( h ); - assertNotNull( t ); - assertTrue( !h.equals( t ) ); - } - } - - - /** - * Retrun a random association with index and a colro strin in RGB. - */ - public static Map<Integer, String> createColorMap(int numColor) - { - Map<Integer, String> colorCodes = new HashMap<Integer, String>(); - for(int i = 0; i < 100; i++) - { - Random rnd = new Random(i); - colorCodes.put( i, String.format( "\"#%2x%2x%2x\"", rnd.nextInt( 255 ), rnd.nextInt( 255 ), rnd.nextInt( 255 ) ) ); - } - return colorCodes; - } - - /** * This class can't be instantiated */ private GraphUtils()