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