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 );
}
}
