Author: simonetripodi
Date: Tue Jul 5 09:45:20 2011
New Revision: 1142948
URL: http://svn.apache.org/viewvc?rev=1142948&view=rev
Log:
[SANDBOX-335] Graph Coloring: Backtracking algorithm - patch provided by Marco
Speranza
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java
(with props)
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoingBackTrackingTestCase.java
(with props)
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/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.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=1142948&r1=1142947&r2=1142948&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 09:45:20 2011
@@ -19,15 +19,16 @@ package org.apache.commons.graph.colorin
* under the License.
*/
+import java.util.ArrayList;
import java.util.HashMap;
+import java.util.List;
import java.util.Map;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
/**
- * Maintains the color for each {@link Vertex} and the required number of
colors
- * for {@link Graph} coloring.
+ * Maintains the color for each {@link Vertex} and the required number of
colors for {@link Graph} coloring.
*
* @param <V> the Graph vertices type.
*/
@@ -36,7 +37,7 @@ public final class ColoredVertices<V ext
private final Map<V, Integer> coloredVertices = new HashMap<V, Integer>();
- private Integer requiredColors;
+ private final List<Integer> usedColor = new ArrayList<Integer>();
/**
* This class can be instantiated only inside the package
@@ -54,11 +55,27 @@ public final class ColoredVertices<V ext
*/
void addColor( V v, Integer color )
{
- if ( requiredColors == null || color.compareTo( requiredColors ) > 0 )
+ coloredVertices.put( v, color );
+ int idx = usedColor.indexOf( color );
+ if ( idx == -1 )
{
- requiredColors = color;
+ usedColor.add( color );
}
- coloredVertices.put( v, color );
+ else
+ {
+ usedColor.set( idx, color );
+ }
+ }
+
+ /**
+ * Remove the input {@link Vertex} color.
+ *
+ * @param v the {@link Vertex} for which storing the color.
+ */
+ void removeColor( V v )
+ {
+ Integer color = coloredVertices.remove( v );
+ usedColor.remove( color );
}
/**
@@ -84,8 +101,15 @@ public final class ColoredVertices<V ext
*/
public int getRequiredColors()
{
- // if requiredColors = 0, it would return 0, and that's wrong
- return requiredColors + 1;
+ return usedColor.size();
+ }
+
+ /**
+ * Tests if the 'vertex' is colored.
+ */
+ public boolean containsColoredVertex( V vertex )
+ {
+ return coloredVertices.containsKey( vertex );
}
}
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=1142948&r1=1142947&r2=1142948&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 09:45:20 2011
@@ -3,6 +3,7 @@ package org.apache.commons.graph.colorin
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
+import java.util.Set;
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.UndirectedGraph;
@@ -37,11 +38,13 @@ public final class GraphColoring
/**
* Colors the graph such that no two adjacent vertices share the same
color.
- *
+ *
+ * @param <V> the Graph vertices type
+ * @param <E> the Graph edges type
* @param g The graph.
* @return The color - vertex association.
*/
- public static <V extends Vertex, E extends Edge> ColoredVertices<V>
coloring( UndirectedGraph<V, E> g )
+ public static <V extends Vertex, E extends Edge> ColoredVertices<V>
greedyColoring( UndirectedGraph<V, E> g )
{
final ColoredVertices<V> coloredVertices = new ColoredVertices<V>();
@@ -58,9 +61,6 @@ public final class GraphColoring
Iterator<V> it = uncoloredOrderedVertices.iterator();
for ( int currentColorIndex = 0; it.hasNext(); currentColorIndex++ )
{
- // consume the vertex.
- it.next();
-
// this list contains all vertex colore with the current color.
List<V> currentColorVertices = new ArrayList<V>();
Iterator<V> uncoloredVtxIterator =
uncoloredOrderedVertices.iterator();
@@ -96,6 +96,26 @@ public final class GraphColoring
}
/**
+ * Graph m-coloring algorithm. This algorithm uses a bruteforce
backtraking 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 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 )
+ {
+ GraphColoringBacktraking<V, E> graphColoringBacktaking =
+ new GraphColoringBacktraking<V, E>( g, colors,
partialColoredVertex );
+ return graphColoringBacktaking.coloring();
+ }
+
+ /**
* This class can not be instantiated.
*/
private GraphColoring()
Added:
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=1142948&view=auto
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java
(added)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java
Tue Jul 5 09:45:20 2011
@@ -0,0 +1,146 @@
+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 java.util.ArrayList;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.UndirectedGraph;
+import org.apache.commons.graph.Vertex;
+
+/**
+ * Graph m-coloring algorithm. This algorithm uses a bruteforce backtraking
procedure to find a graph color using a
+ * predefined set of colors.
+ *
+ * @param <V> the Graph vertices type
+ * @param <E> the Graph edges type
+ */
+class GraphColoringBacktraking<V extends Vertex, E extends Edge>
+{
+
+ final private ColoredVertices<V> coloredVertices;
+
+ final private UndirectedGraph<V, E> g;
+
+ final private Set<Integer> colors;
+
+ final private List<V> vertexList = new ArrayList<V>();
+
+ /**
+ * Creates a new instance of {@link GraphColoringBacktraking}.
+ *
+ * @param <V> the Graph vertices type
+ * @param <E> the Graph edges type
+ * @param g The graph.
+ * @param colors The list of colors.
+ */
+ GraphColoringBacktraking( UndirectedGraph<V, E> g, Set<Integer> colors,
ColoredVertices<V> partialColoredVertex )
+ {
+ this.coloredVertices = partialColoredVertex;
+ this.g = g;
+ this.colors = colors;
+ }
+
+ /**
+ * Tries to color the graph using a predefined set of colors.
+ *
+ * @return true if all vertices have been colored, false otherwise.
+ */
+ ColoredVertices<V> coloring()
+ {
+ for ( V v : g.getVertices() )
+ {
+ if ( !coloredVertices.containsColoredVertex( v ) )
+ {
+ vertexList.add( v );
+ }
+ }
+
+ if ( backtraking( -1 ) )
+ {
+ return coloredVertices;
+ }
+ return null;
+ }
+
+ /**
+ * 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.
+ */
+ private boolean backtraking( int currentVertexIndex )
+ {
+ if ( currentVertexIndex != -1 && isThereColorConflict( vertexList.get(
currentVertexIndex ) ) )
+ {
+ return false;
+ }
+ if ( currentVertexIndex == vertexList.size() - 1 )
+ {
+ return true;
+ }
+
+ int next = currentVertexIndex + 1;
+ V nextVertex = vertexList.get( next );
+ for ( Integer color : colors )
+ {
+ coloredVertices.addColor( nextVertex, color );
+ boolean isDone = backtraking( next );
+ if ( isDone )
+ {
+ return true;
+ }
+ }
+ coloredVertices.removeColor( nextVertex );
+ return false;
+ }
+
+ /**
+ * Tests if there is some adiacent vertices with the same color.
+ *
+ * @param currentVertex
+ * @return
+ */
+ private boolean isThereColorConflict( V currentVertex )
+ {
+ if ( currentVertex == null )
+ {
+ return false;
+ }
+ Integer nextVertecColor = coloredVertices.getColor( currentVertex );
+ if ( nextVertecColor == null )
+ return false;
+
+ for ( V abj : g.getConnectedVertices( currentVertex ) )
+ {
+ Integer adjColor = coloredVertices.getColor( abj );
+ if ( adjColor != null && nextVertecColor.equals( adjColor ) )
+ {
+ return true;
+ }
+
+ }
+ return false;
+ }
+
+}
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoringBacktraking.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoingBackTrackingTestCase.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoingBackTrackingTestCase.java?rev=1142948&view=auto
==============================================================================
---
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoingBackTrackingTestCase.java
(added)
+++
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoingBackTrackingTestCase.java
Tue Jul 5 09:45:20 2011
@@ -0,0 +1,229 @@
+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.apache.commons.graph.utils.GraphUtils.checkColoring;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+
+import java.text.DecimalFormat;
+import java.text.NumberFormat;
+import java.util.HashSet;
+import java.util.Set;
+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 GraphColoingBackTrackingTestCase
+{
+
+ @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> coloredVertex = new
ColoredVertices<BaseLabeledVertex>();
+ coloredVertex.addColor( two, 2 );
+
+ ColoredVertices<BaseLabeledVertex> 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> coloredVertices =
+ backTrackingColoring( g1, createColorsList( 100 ), new
ColoredVertices<BaseLabeledVertex>() );
+ 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> coloredVertices =
+ backTrackingColoring( g1, createColorsList( 2 ), new
ColoredVertices<BaseLabeledVertex>());
+ 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> coloredVertices =
+ backTrackingColoring( g1, createColorsList( 1 ), new
ColoredVertices<BaseLabeledVertex>() );
+ 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> coloredVertices =
+ backTrackingColoring( g, createColorsList( 2 ), new
ColoredVertices<BaseLabeledVertex>() );
+ 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> sudoku =
+ backTrackingColoring( g1, createColorsList( 9 ), new
ColoredVertices<BaseLabeledVertex>() );
+ 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> predefinedColor = new
ColoredVertices<BaseLabeledVertex>();
+ predefinedColor.addColor( grid[0][0], 1 );
+ predefinedColor.addColor( grid[5][5], 8 );
+ predefinedColor.addColor( grid[1][2], 5 );
+
+ ColoredVertices<BaseLabeledVertex> 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() );
+
+ }
+
+ /**
+ * Creates a list of colors.
+ *
+ * @param colorNumber number of colors
+ * @return the list.
+ */
+ private Set<Integer> createColorsList( int colorNumber )
+ {
+ Set<Integer> colors = new HashSet<Integer>();
+ for ( int j = 0; j < colorNumber; j++ )
+ {
+ colors.add( j );
+ }
+ return colors;
+ }
+
+}
Propchange:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoingBackTrackingTestCase.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoingBackTrackingTestCase.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoingBackTrackingTestCase.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=1142948&r1=1142947&r2=1142948&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 09:45:20 2011
@@ -19,23 +19,21 @@ package org.apache.commons.graph.colorin
* under the License.
*/
-import static org.apache.commons.graph.coloring.GraphColoring.coloring;
+import static org.apache.commons.graph.coloring.GraphColoring.greedyColoring;
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.apache.commons.graph.utils.GraphUtils.checkColoring;
import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
-import org.apache.commons.graph.Edge;
-import org.apache.commons.graph.Vertex;
-import org.apache.commons.graph.VertexPair;
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 GraphColoringTestCase
{
@@ -44,8 +42,7 @@ public class GraphColoringTestCase
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" );
@@ -59,49 +56,41 @@ public class GraphColoringTestCase
g.addEdge( two, new BaseLabeledEdge( "2 -> 3" ), three );
g.addEdge( three, new BaseLabeledEdge( "3 -> 1" ), one );
- ColoredVertices<BaseLabeledVertex> coloredVertices = coloring( g );
- assertEquals( 3, coloredVertices.getRequiredColors() );
-
+ ColoredVertices<BaseLabeledVertex> coloredVertices = greedyColoring( g
);
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 = coloring( g1 );
- assertEquals( 100, coloredVertices.getRequiredColors() );
-
+ ColoredVertices<BaseLabeledVertex> coloredVertices = greedyColoring(
g1 );
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 = coloring( g1 );
+ ColoredVertices<BaseLabeledVertex> coloredVertices = greedyColoring(
g1 );
- assertEquals( 2, coloredVertices.getRequiredColors() );
checkColoring( g1, coloredVertices );
}
@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 = coloring( g1 );
+ ColoredVertices<BaseLabeledVertex> coloredVertices = greedyColoring(
g1 );
assertEquals( 1, coloredVertices.getRequiredColors() );
checkColoring( g1, coloredVertices );
@@ -113,33 +102,10 @@ public class GraphColoringTestCase
@Test
public void testCrawnGraph()
{
- UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g =
- new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>();
-
- BaseLabeledVertex one = new BaseLabeledVertex( "1" );
- BaseLabeledVertex two = new BaseLabeledVertex( "2" );
- BaseLabeledVertex three = new BaseLabeledVertex( "3" );
- BaseLabeledVertex four = new BaseLabeledVertex( "4" );
- BaseLabeledVertex five = new BaseLabeledVertex( "5" );
- BaseLabeledVertex six = new BaseLabeledVertex( "6" );
-
- g.addVertex( one );
- g.addVertex( two );
- g.addVertex( three );
- g.addVertex( four );
- g.addVertex( five );
- g.addVertex( six );
-
- g.addEdge( one, new BaseLabeledEdge( "1 -> 2" ), two );
- g.addEdge( two, new BaseLabeledEdge( "2 -> 3" ), three );
- g.addEdge( three, new BaseLabeledEdge( "3 -> 4" ), four );
- g.addEdge( four, new BaseLabeledEdge( "4 -> 5" ), five );
- g.addEdge( five, new BaseLabeledEdge( "5 -> 6" ), six );
- g.addEdge( six, new BaseLabeledEdge( "5 -> 1" ), one );
-
- ColoredVertices<BaseLabeledVertex> coloredVertices = coloring( g );
- assertEquals( 2, coloring( g ).getRequiredColors() );
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = new
UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>();
+ buildCrownGraph( 6, g );
+ ColoredVertices<BaseLabeledVertex> coloredVertices = greedyColoring( g
);
checkColoring( g, coloredVertices );
}
@@ -147,29 +113,11 @@ public class GraphColoringTestCase
public void testSudoku()
throws Exception
{
- UndirectedMutableGraph<Vertex, Edge> g1 = buildSudokuGraph();
-
- // The true color number for this graph is 9. but the greedy heuristic
is not the best and returns 11.
- ColoredVertices<Vertex> sudoku = GraphColoring.coloring( g1 );
- assertEquals( 11, sudoku.getRequiredColors() );
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 = new
UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>();
+ buildSudokuGraph( g1 );
+ ColoredVertices<BaseLabeledVertex> sudoku =
GraphColoring.greedyColoring( g1 );
checkColoring( g1, sudoku );
}
- /**
- * This method checks if all connected vertices have different colors.
- *
- * @param g
- * @param coloredVertices
- */
- private <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 );
- assertTrue( coloredVertices.getColor( vp.getHead() ) !=
coloredVertices.getColor( vp.getTail() ) );
- }
- }
-
}
