commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1140739 - in /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring: ColoredVertices.java GraphColoring.java
Date Tue, 28 Jun 2011 17:26:03 GMT
Author: simonetripodi
Date: Tue Jun 28 17:26:03 2011
New Revision: 1140739

URL: http://svn.apache.org/viewvc?rev=1140739&view=rev
Log:
used a data structure to store and maintain the color for each vertex and the required number
of colors for graph coloring.

Added:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java
  (with props)
Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java

Added: 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=1140739&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java
Tue Jun 28 17:26:03 2011
@@ -0,0 +1,91 @@
+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.HashMap;
+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.
+ *
+ * @param <V> the Graph vertices type.
+ */
+public final class ColoredVertices<V extends Vertex>
+{
+
+    private final Map<V, Integer> coloredVertices = new HashMap<V, Integer>();
+
+    private Integer requiredColors;
+
+    /**
+     * This class can be instantiated only inside the package
+     */
+    ColoredVertices()
+    {
+        // do nothing
+    }
+
+    /**
+     * Store the input {@link Vertex} color.
+     *
+     * @param v the {@link Vertex} for which storing the color.
+     * @param color the input {@link Vertex} color.
+     */
+    void addColor( V v, Integer color )
+    {
+        if ( requiredColors == null || color.compareTo( requiredColors ) > 0 )
+        {
+            requiredColors = color;
+        }
+        coloredVertices.put( v, color );
+    }
+
+    /**
+     * Returns the color associated to the input {@link Vertex}.
+     *
+     * @param v the {@link Vertex} for which getting the color.
+     * @return the color associated to the input {@link Vertex}.
+     */
+    public Integer getColor( V v )
+    {
+        if ( v == null )
+        {
+            throw new IllegalArgumentException( "Impossible to get the color for a null Vertex"
);
+        }
+
+        return coloredVertices.get( v );
+    }
+
+    /**
+     * Returns the number of required colors for coloring the Graph.
+     *
+     * @return the number of required colors for coloring the Graph.
+     */
+    public int getRequiredColors()
+    {
+        // if requiredColors = 0, it would return 0, and that's wrong
+        return requiredColors + 1;
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

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=1140739&r1=1140738&r2=1140739&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 Jun 28 17:26:03 2011
@@ -1,9 +1,7 @@
 package org.apache.commons.graph.coloring;
 
 import java.util.ArrayList;
-import java.util.Collections;
 import java.util.Comparator;
-import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
@@ -39,27 +37,14 @@ public final class GraphColoring
 {
 
     /**
-     * Return the color number of the graph. The color number is the minimal number of colors
needed to color each
-     * vertex such that no two adjacent vertices share the same color.
-     *
-     * @param g The graph.
-     * @return the graph color number.
-     */
-    public static <V extends Vertex, E extends Edge> int colorNumber( UndirectedGraph<V,
E> g )
-    {
-        Map<V, Integer> coloredVertices = coloring( g );
-        return Collections.max( coloredVertices.values() ) + 1;
-    }
-
-    /**
      * Colors the graph such that no two adjacent vertices share the same color.
      *
      * @param g The graph.
      * @return The color - vertex association.
      */
-    public static <V extends Vertex, E extends Edge> Map<V, Integer> coloring(
UndirectedGraph<V, E> g )
+    public static <V extends Vertex, E extends Edge> ColoredVertices<V> coloring(
UndirectedGraph<V, E> g )
     {
-        Map<V, Integer> coloredVertices = new HashMap<V, Integer>();
+        ColoredVertices<V> coloredVertices = new ColoredVertices<V>();
         List<V> uncoloredVertices = null;
 
         // decreasing sorting all vertices by degree.
@@ -101,9 +86,9 @@ public final class GraphColoring
 
             // remove vertex from uncolored list.
             it.remove();
-            coloredVertices.put( v, currrentColorIndex );
+            coloredVertices.addColor( v, currrentColorIndex );
 
-            // color all vertex not adiacent
+            // color all vertices not adjacent
             Iterator<V> it2 = uncoloredVertices.iterator();
             while ( it2.hasNext() )
             {
@@ -112,7 +97,7 @@ public final class GraphColoring
                 {
                     // v2 is not connect to v.
                     it2.remove();
-                    coloredVertices.put( v2, currrentColorIndex );
+                    coloredVertices.addColor( v2, currrentColorIndex );
                 }
             }
 



Mime
View raw message