commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1141492 - in /commons/sandbox/graph/trunk/src: main/java/org/apache/commons/graph/coloring/ test/java/org/apache/commons/graph/coloring/ test/java/org/apache/commons/graph/utils/
Date Thu, 30 Jun 2011 11:54:27 GMT
Author: simonetripodi
Date: Thu Jun 30 11:54:26 2011
New Revision: 1141492

URL: http://svn.apache.org/viewvc?rev=1141492&view=rev
Log:
[SANDBOX-334] Bad coloring for crawn graph - patch submitted by Marco Speranza

Modified:
    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/UncoloredOrderedVertices.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/GraphColoring.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java?rev=1141492&r1=1141491&r2=1141492&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
Thu Jun 30 11:54:26 2011
@@ -1,6 +1,8 @@
 package org.apache.commons.graph.coloring;
 
+import java.util.ArrayList;
 import java.util.Iterator;
+import java.util.List;
 
 import org.apache.commons.graph.Edge;
 import org.apache.commons.graph.UndirectedGraph;
@@ -26,14 +28,16 @@ import org.apache.commons.graph.Vertex;
  */
 
 /**
- * Contains the graph coloring implementation. http://scienceblogs.com/goodmath/2007/06/graph_coloring_algorithms_1.php
+ * 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">
  */
 public final class GraphColoring
 {
 
     /**
      * Colors the graph such that no two adjacent vertices share the same color.
-     *
+     * 
      * @param g The graph.
      * @return The color - vertex association.
      */
@@ -50,32 +54,42 @@ public final class GraphColoring
         }
 
         // search coloring
-        int currrentColorIndex = 0;
 
         Iterator<V> it = uncoloredOrderedVertices.iterator();
-        while ( it.hasNext() )
+        for ( int currentColorIndex = 0; it.hasNext(); currentColorIndex++ )
         {
-            V v = it.next();
+            // consume the vertex.
+            it.next();
 
-            // remove vertex from uncolored list.
-            it.remove();
-            coloredVertices.addColor( v, currrentColorIndex );
-
-            // color all vertices not adjacent
-            Iterator<V> it2 = uncoloredOrderedVertices.iterator();
-            while ( it2.hasNext() )
+            // this list contains all vertex colore with the current color.
+            List<V> currentColorVertices = new ArrayList<V>();
+            Iterator<V> uncoloredVtxIterator = uncoloredOrderedVertices.iterator();
+            while ( uncoloredVtxIterator.hasNext() )
             {
-                V v2 = it2.next();
-                if ( g.getEdge( v, v2 ) == null )
+                V uncoloredVtx = uncoloredVtxIterator.next();
+
+                boolean foundAnAdjacentVertex = false;
+                for ( V currentColoredVtx : currentColorVertices )
+                {
+                    if ( g.getEdge( currentColoredVtx, uncoloredVtx ) != null )
+                    {
+                        // we've found that 'uncoloredVtx' is adiacent to 'currentColoredVtx'
+                        foundAnAdjacentVertex = true;
+                        break;
+                    }
+                }
+
+                if ( !foundAnAdjacentVertex )
                 {
-                    // v2 is not connect to v.
-                    it2.remove();
-                    coloredVertices.addColor( v2, currrentColorIndex );
+                    // It's possible to color the vertex 'uncoloredVtx', it has no connected
vertex into
+                    // 'currentcoloredvtx'
+                    uncoloredVtxIterator.remove();
+                    coloredVertices.addColor( uncoloredVtx, currentColorIndex );
+                    currentColorVertices.add( uncoloredVtx );
                 }
             }
 
             it = uncoloredOrderedVertices.iterator();
-            currrentColorIndex++;
         }
 
         return coloredVertices;

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java?rev=1141492&r1=1141491&r2=1141492&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
Thu Jun 30 11:54:26 2011
@@ -111,4 +111,14 @@ final class UncoloredOrderedVertices<V e
         };
     }
 
+    /**
+     * Returns the number of vertices degrees in the graph.
+     *
+     * @return the number of vertices degrees in the graph.
+     */
+    public int size()
+    {
+        return orderedVertices.size();
+    }
+
 }

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=1141492&r1=1141491&r2=1141492&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
Thu Jun 30 11:54:26 2011
@@ -23,12 +23,15 @@ import static org.apache.commons.graph.c
 import static org.apache.commons.graph.utils.GraphUtils.buildBipartedGraph;
 import static org.apache.commons.graph.utils.GraphUtils.buildCompleteGraph;
 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.apache.commons.graph.utils.GraphUtils;
 import org.junit.Test;
 
 /**
@@ -39,8 +42,10 @@ public class GraphColoringTestCase
 
     @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" );
@@ -54,7 +59,11 @@ public class GraphColoringTestCase
         g.addEdge( two, new BaseLabeledEdge( "2 -> 3" ), three );
         g.addEdge( three, new BaseLabeledEdge( "3 -> 1" ), one );
 
-        assertEquals( 3, coloring( g ).getRequiredColors() );
+        ColoredVertices<BaseLabeledVertex> coloredVertices = coloring( g );
+        assertEquals( 3, coloredVertices.getRequiredColors() );
+
+        checkColoring( g, coloredVertices );
+
     }
 
     @Test
@@ -64,7 +73,11 @@ public class GraphColoringTestCase
             new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>();
         buildCompleteGraph( 100, g1 );
 
-        assertEquals( 100, coloring( g1 ).getRequiredColors() );
+        ColoredVertices<BaseLabeledVertex> coloredVertices = coloring( g1 );
+        assertEquals( 100, coloredVertices.getRequiredColors() );
+
+        checkColoring( g1, coloredVertices );
+
     }
 
     @Test
@@ -74,19 +87,111 @@ public class GraphColoringTestCase
             new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>();
         buildBipartedGraph( 100, g1 );
 
-        assertEquals( 2, coloring( g1 ).getRequiredColors() );
+        ColoredVertices<BaseLabeledVertex> coloredVertices = coloring( g1 );
+
+        assertEquals( 2, coloredVertices.getRequiredColors() );
+        checkColoring( g1, coloredVertices );
+
     }
 
     @Test
     public void testCromaticNumberSparseGraph()
     {
-        UndirectedMutableGraph<Vertex, Edge> g1 = new UndirectedMutableGraph<Vertex,
Edge>();
+        UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 =
+            new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>();
         for ( int i = 0; i < 100; i++ )
         {
             g1.addVertex( new BaseLabeledVertex( "" + i ) );
         }
 
-        assertEquals( 1, coloring( g1 ).getRequiredColors() );
+        ColoredVertices<BaseLabeledVertex> coloredVertices = coloring( g1 );
+
+        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>();
+
+        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() );
+
+        checkColoring( g, coloredVertices );
+
+    }
+
+    @Test
+    public void testSudoku()
+        throws Exception
+    {
+
+        UndirectedMutableGraph<Vertex, Edge> g1 = GraphUtils.buildSudokuGraph();
+
+        // The true color number fot this graph is 9. but the greedy euristics is not the
best and returns 11.
+        ColoredVertices<Vertex> sudoku = GraphColoring.coloring( g1 );
+        assertEquals( 11, sudoku.getRequiredColors() );
+
+        checkColoring( g1, sudoku );
+
+        // for ( int i = 0; i < 9; i++ )
+        // {
+        // for ( int j = 0; j < 9; j++ )
+        // {
+        // System.out.print ( sudoku.getColor(GraphUtils.grid[i][j]) + " | " );
+        // }
+        // System.out.println();
+        // }
+
+        // Writer w = new OutputStreamWriter(System.out);
+        // GraphUtils.DOTexport(w, g1);
+        // w.flush();
+        // w.close();
+
+    }
+
+    /**
+     * 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() ) );
+
+        }
     }
 
 }

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=1141492&r1=1141491&r2=1141492&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
Thu Jun 30 11:54:26 2011
@@ -3,6 +3,8 @@ package org.apache.commons.graph.utils;
 import java.util.ArrayList;
 import java.util.List;
 
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.model.BaseLabeledEdge;
 import org.apache.commons.graph.model.BaseLabeledVertex;
 import org.apache.commons.graph.model.UndirectedMutableGraph;
@@ -34,7 +36,7 @@ public class GraphUtils
 
     /**
      * Creates a complete graph with nVertices
-     *
+     * 
      * @param nVertices number of vertices
      * @param g graph
      */
@@ -110,6 +112,101 @@ public class GraphUtils
     }
 
     /**
+     * Creates a graph that contains all classic sudoku contratints.
+     *
+     * @return
+     */
+    public static UndirectedMutableGraph<Vertex, Edge> buildSudokuGraph()
+    {
+        UndirectedMutableGraph<Vertex, Edge> sudoku = new UndirectedMutableGraph<Vertex,
Edge>();
+
+        BaseLabeledVertex[][] grid = new BaseLabeledVertex[9][9];
+
+        // build sudoku grid.
+        for ( int row = 0; row < 9; row++ )
+        {
+            for ( int col = 0; col < 9; col++ )
+            {
+                grid[row][col] = new BaseLabeledVertex( row + "," + col );
+                sudoku.addVertex( grid[row][col] );
+            }
+        }
+
+        int[] rowsOffsets = new int[] { 0, 3, 6 };
+        int[] colsOffsets = new int[] { 0, 3, 6 };
+
+        // build constraint.
+        for ( int rof = 0; rof < 3; rof++ )
+        {
+            for ( int cof = 0; cof < 3; cof++ )
+            {
+                List<Vertex> boxes = new ArrayList<Vertex>();
+                for ( int row = rowsOffsets[rof]; row < 3 + rowsOffsets[rof]; row++ )
+                {
+                    for ( int col = colsOffsets[cof]; col < 3 + colsOffsets[cof]; col++
)
+                    {
+                        boxes.add( grid[row][col] );
+                    }
+                }
+
+                for ( Vertex v1 : boxes )
+                {
+                    for ( Vertex v2 : boxes )
+                    {
+
+                        Edge e = new BaseLabeledEdge( v1 + " -> " + v2 );
+                        if ( !v1.equals( v2 ) )
+                        {
+                            sudoku.addEdge( v1, e, v2 );
+                        }
+                    }
+                }
+            }
+        }
+
+        // create rows constraint
+        for ( int j = 0; j < 9; j++ )
+        {
+            for ( int i = 0; i < 9; i++ )
+            {
+                for ( int h = 0; h < 9; h++ )
+                {
+                    Vertex v1 = grid[j][i];
+                    Vertex v2 = grid[j][h];
+
+                    if ( !v1.equals( v2 ) )
+                    {
+                        Edge e = new BaseLabeledEdge( v1 + " -> " + v2 );
+                        sudoku.addEdge( v1, e, v2 );
+                    }
+
+                }
+            }
+        }
+
+        // create cols constraint
+        for ( int j = 0; j < 9; j++ )
+        {
+            for ( int i = 0; i < 9; i++ )
+            {
+                for ( int h = 0; h < 9; h++ )
+                {
+                    Vertex v1 = grid[i][j];
+                    Vertex v2 = grid[h][j];
+
+                    if ( !v1.equals( v2 ) )
+                    {
+                        Edge e = new BaseLabeledEdge( v1 + " -> " + v2 );
+                        sudoku.addEdge( v1, e, v2 );
+                    }
+
+                }
+            }
+        }
+        return sudoku;
+    }
+
+    /**
      * This class can't be instantiated
      */
     private GraphUtils()



Mime
View raw message