commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject 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/
Date Fri, 03 Feb 2012 22:31:15 GMT
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()



Mime
View raw message