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()
