commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1142948 - in /commons/sandbox/graph/trunk/src: main/java/org/apache/commons/graph/coloring/ test/java/org/apache/commons/graph/coloring/
Date Tue, 05 Jul 2011 09:45:20 GMT
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() ) );
-        }
-    }
-
 }



Mime
View raw message