You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by si...@apache.org on 2012/02/03 23:31:15 UTC
svn commit: r1240375 - in /commons/sandbox/graph/trunk/src: changes/
main/java/org/apache/commons/graph/
main/java/org/apache/commons/graph/coloring/
test/java/org/apache/commons/graph/coloring/
Author: simonetripodi
Date: Fri Feb 3 22:31:14 2012
New Revision: 1240375
URL: http://svn.apache.org/viewvc?rev=1240375&view=rev
Log:
[SANDBOX-382] Add new test for coloring - patch provided by Marco Speranza
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java (with props)
Modified:
commons/sandbox/graph/trunk/src/changes/changes.xml
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/DefaultColoringAlgorithmsSelector.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java
Modified: commons/sandbox/graph/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/changes/changes.xml?rev=1240375&r1=1240374&r2=1240375&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Fri Feb 3 22:31:14 2012
@@ -23,6 +23,9 @@
</properties>
<body>
<release version="0.1" date="201?-??-??" description="First release.">
+ <action dev="simonetripodi" type="fix" issue="SANDBOX-382" due-to="Marco Speranza">
+ Add new test for coloring
+ </action>
<action dev="simonetripodi" type="fix" issue="SANDBOX-381" due-to="Marco Speranza">
Unused class GraphColoringBacktraking
</action>
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java?rev=1240375&r1=1240374&r2=1240375&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java Fri Feb 3 22:31:14 2012
@@ -63,7 +63,7 @@ public final class CommonsGraph<V extend
*/
public static <V extends Vertex, E extends Edge, G extends UndirectedGraph<V, E>> ColorsBuilder<V, E, G> coloring( G graph )
{
- graph = checkNotNull( graph, "Null graph can not be exported" );
+ graph = checkNotNull( graph, "Coloring can not be calculated on null graph" );
return new DefaultColorsBuilder<V, E, G>( graph );
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/DefaultColoringAlgorithmsSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/DefaultColoringAlgorithmsSelector.java?rev=1240375&r1=1240374&r2=1240375&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/DefaultColoringAlgorithmsSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/DefaultColoringAlgorithmsSelector.java Fri Feb 3 22:31:14 2012
@@ -27,7 +27,6 @@ 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;
@@ -75,11 +74,11 @@ final class DefaultColoringAlgorithmsSel
{
if ( !colorsIt.hasNext() )
{
- throw new GraphException( "The color set is too small." );
+ throw new NotEnoughColorsException( colors );
}
C color = colorsIt.next();
- // this list contains all vertex colore with the current color.
+ // this list contains all vertex colors with the current color.
List<V> currentColorVertices = new ArrayList<V>();
Iterator<V> uncoloredVtxIterator = uncoloredOrderedVertices.iterator();
while ( uncoloredVtxIterator.hasNext() )
@@ -144,7 +143,8 @@ final class DefaultColoringAlgorithmsSel
{
return partialColoredVertex;
}
- return null;
+
+ throw new NotEnoughColorsException( colors );
}
/**
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java?rev=1240375&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java Fri Feb 3 22:31:14 2012
@@ -0,0 +1,39 @@
+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 java.lang.String.format;
+
+import java.util.Set;
+
+import org.apache.commons.graph.GraphException;
+
+public class NotEnoughColorsException
+ extends GraphException
+{
+
+ private static final long serialVersionUID = -8782950517745777605L;
+
+ public NotEnoughColorsException( Set<?> colors )
+ {
+ super( format( "Input color set %s has not enough colors to color the given graph", colors ) );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: 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=1240375&r1=1240374&r2=1240375&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java Fri Feb 3 22:31:14 2012
@@ -32,6 +32,9 @@ import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.logging.Logger;
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.UndirectedGraph;
+import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.builder.AbstractGraphConnection;
import org.apache.commons.graph.model.BaseLabeledEdge;
import org.apache.commons.graph.model.BaseLabeledVertex;
@@ -41,38 +44,105 @@ import org.junit.Test;
/**
*
*/
-public class GraphColoringBackTrackingTestCase extends AbstractColoringTest
+public class GraphColoringBackTrackingTestCase
+ extends AbstractColoringTest
{
+ @Test( expected = NullPointerException.class )
+ public void testNullGraph()
+ {
+ coloring( (UndirectedGraph<Vertex, Edge>) null ).withColors( null ).applyingBackTrackingAlgorithm();
+ }
+
+ @Test( expected = NullPointerException.class )
+ public void testNullColorGraph()
+ {
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+ @Override
+ public void connect()
+ {
+ // empty
+ }
+
+ } );
+ coloring( g ).withColors( null ).applyingBackTrackingAlgorithm();
+ }
+
@Test
- public void testCromaticNumber()
- throws Exception
+ public void testEmptyGraph()
+ {
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ @Override
+ public void connect()
+ {
+ // empty
+ }
+
+ } );
+ ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = coloring( g ).withColors( createColorsList( 1 ) ).applyingBackTrackingAlgorithm();
+ assertNotNull( coloredVertices );
+ assertEquals( 0, coloredVertices.getRequiredColors() );
+ }
+
+ @Test(expected=NotEnoughColorsException.class)
+ public void testNotEnoughtColorGraph()
+ throws NotEnoughColorsException
{
final BaseLabeledVertex two = new BaseLabeledVertex( "2" );
UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g =
- newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
- {
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ @Override
+ public void connect()
+ {
+ BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) );
+ addVertex( two );
+ BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) );
+
+ addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two );
+ addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three );
+ addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one );
+ }
+
+ } );
+ coloring( g ).withColors( createColorsList( 1 ) ).applyingBackTrackingAlgorithm();
+ }
- @Override
- public void connect()
+ @Test
+ public void testCromaticNumber()
+ {
+ final BaseLabeledVertex two = new BaseLabeledVertex( "2" );
+
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
{
- BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) );
- addVertex( two );
- BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) );
-
- addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two );
- addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three );
- addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one );
- }
- } );
+ @Override
+ public void connect()
+ {
+ BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) );
+ addVertex( two );
+ BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) );
+
+ addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two );
+ addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three );
+ addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one );
+ }
+
+ } );
ColoredVertices<BaseLabeledVertex, Integer> coloredVertex = new ColoredVertices<BaseLabeledVertex, Integer>();
coloredVertex.addColor( two, 2 );
ColoredVertices<BaseLabeledVertex, Integer> coloredVertices =
- coloring( g ).withColors( createColorsList( 3 ) ).applyingBackTrackingAlgorithm( coloredVertex );
+ coloring( g ).withColors( createColorsList( 3 ) ).applyingBackTrackingAlgorithm( coloredVertex );
assertNotNull( coloredVertices );
assertEquals( 3, coloredVertices.getRequiredColors() );
assertEquals( new Integer( 2 ), coloredVertices.getColor( two ) );
@@ -88,7 +158,7 @@ public class GraphColoringBackTrackingTe
buildCompleteGraph( 100, g1 );
ColoredVertices<BaseLabeledVertex, Integer> coloredVertices =
- coloring( g1 ).withColors( createColorsList( 100 ) ).applyingBackTrackingAlgorithm();
+ coloring( g1 ).withColors( createColorsList( 100 ) ).applyingBackTrackingAlgorithm();
assertNotNull( coloredVertices );
assertEquals( 100, coloredVertices.getRequiredColors() );
checkColoring( g1, coloredVertices );
@@ -103,7 +173,7 @@ public class GraphColoringBackTrackingTe
buildBipartedGraph( 100, g1 );
ColoredVertices<BaseLabeledVertex, Integer> coloredVertices =
- coloring( g1 ).withColors( createColorsList( 2 ) ).applyingBackTrackingAlgorithm();
+ coloring( g1 ).withColors( createColorsList( 2 ) ).applyingBackTrackingAlgorithm();
assertNotNull( coloredVertices );
assertEquals( 2, coloredVertices.getRequiredColors() );
checkColoring( g1, coloredVertices );
@@ -120,7 +190,7 @@ public class GraphColoringBackTrackingTe
}
ColoredVertices<BaseLabeledVertex, Integer> coloredVertices =
- coloring( g1 ).withColors( createColorsList( 1 ) ).applyingBackTrackingAlgorithm();
+ coloring( g1 ).withColors( createColorsList( 1 ) ).applyingBackTrackingAlgorithm();
assertNotNull( coloredVertices );
assertEquals( 1, coloredVertices.getRequiredColors() );
checkColoring( g1, coloredVertices );
@@ -138,7 +208,7 @@ public class GraphColoringBackTrackingTe
buildCrownGraph( 6, g );
ColoredVertices<BaseLabeledVertex, Integer> coloredVertices =
- coloring( g ).withColors( createColorsList( 2 ) ).applyingBackTrackingAlgorithm();
+ coloring( g ).withColors( createColorsList( 2 ) ).applyingBackTrackingAlgorithm();
assertNotNull( coloredVertices );
assertEquals( 2, coloredVertices.getRequiredColors() );
checkColoring( g, coloredVertices );
@@ -153,7 +223,7 @@ public class GraphColoringBackTrackingTe
BaseLabeledVertex[][] grid = buildSudokuGraph( g1 );
ColoredVertices<BaseLabeledVertex, Integer> sudoku =
- coloring( g1 ).withColors( createColorsList( 9 ) ).applyingBackTrackingAlgorithm();
+ coloring( g1 ).withColors( createColorsList( 9 ) ).applyingBackTrackingAlgorithm();
assertNotNull( sudoku );
checkColoring( g1, sudoku );
assertEquals( 9, sudoku.getRequiredColors() );
@@ -187,7 +257,7 @@ public class GraphColoringBackTrackingTe
predefinedColor.addColor( grid[1][2], 5 );
ColoredVertices<BaseLabeledVertex, Integer> sudoku =
- coloring( g1 ).withColors( createColorsList( 9 ) ).applyingBackTrackingAlgorithm( predefinedColor );
+ coloring( g1 ).withColors( createColorsList( 9 ) ).applyingBackTrackingAlgorithm( predefinedColor );
assertNotNull( sudoku );
checkColoring( g1, sudoku );
assertEquals( 9, sudoku.getRequiredColors() );
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=1240375&r1=1240374&r2=1240375&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 Fri Feb 3 22:31:14 2012
@@ -26,9 +26,14 @@ import static org.apache.commons.graph.u
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.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;
import org.apache.commons.graph.builder.AbstractGraphConnection;
import org.apache.commons.graph.model.BaseLabeledEdge;
import org.apache.commons.graph.model.BaseLabeledVertex;
@@ -43,6 +48,99 @@ public class GraphColoringTestCase exten
private Set<Integer> colors = createColorsList( 11 );
+ @Test( expected = NullPointerException.class )
+ public void testNullGraph()
+ {
+ coloring( (UndirectedGraph<Vertex, Edge>) null ).withColors( null ).applyingGreedyAlgorithm();
+ }
+
+ @Test( expected = NullPointerException.class )
+ public void testNullColorGraph()
+ {
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ @Override
+ public void connect()
+ {
+ // empty
+ }
+
+ } );
+ coloring( g ).withColors( null ).applyingBackTrackingAlgorithm();
+ }
+
+ @Test
+ public void testEmptyGraph()
+ {
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ @Override
+ public void connect()
+ {
+ // empty
+ }
+
+ } );
+ ColoredVertices<BaseLabeledVertex, Integer> coloredVertices = coloring( g ).withColors( createColorsList( 1 ) ).applyingGreedyAlgorithm();
+ assertNotNull( coloredVertices );
+ assertEquals( 0, coloredVertices.getRequiredColors() );
+ }
+
+ @Test(expected=NotEnoughColorsException.class)
+ public void testNotEnoughtColorGraph()
+ throws NotEnoughColorsException
+ {
+ final BaseLabeledVertex two = new BaseLabeledVertex( "2" );
+
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ @Override
+ public void connect()
+ {
+ BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) );
+ addVertex( two );
+ BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) );
+
+ addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two );
+ addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three );
+ addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one );
+ }
+
+ } );
+ coloring( g ).withColors( createColorsList( 1 ) ).applyingGreedyAlgorithm();
+ }
+
+ @Test(expected=GraphException.class)
+ public void testNotEnoughtColorGreedyGraph()
+ throws GraphException
+ {
+ final BaseLabeledVertex two = new BaseLabeledVertex( "2" );
+
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ @Override
+ public void connect()
+ {
+ BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) );
+ addVertex( two );
+ BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) );
+
+ addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two );
+ addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three );
+ addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one );
+ }
+
+ } );
+ coloring( g ).withColors( createColorsList( 1 ) ).applyingGreedyAlgorithm();
+ }
@Test
public void testCromaticNumber()