[prev in list] [next in list] [prev in thread] [next in thread]
List: jakarta-commons-dev
Subject: svn commit: r1141492 - in /commons/sandbox/graph/trunk/src:
From: simonetripodi () apache ! org
Date: 2011-06-30 11:54:27
Message-ID: 20110630115427.7F31D238896F () eris ! apache ! org
[Download RAW message or body]
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()
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic