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 2011/06/28 14:18:37 UTC
svn commit: r1140557 - in /commons/sandbox/graph/trunk/src:
main/java/org/apache/commons/graph/coloring/
test/java/org/apache/commons/graph/coloring/
test/java/org/apache/commons/graph/utils/
Author: simonetripodi
Date: Tue Jun 28 12:18:36 2011
New Revision: 1140557
URL: http://svn.apache.org/viewvc?rev=1140557&view=rev
Log:
[SANDBOX-333] Graph coloring implementation - patch provided by Marco Speranza
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java (with props)
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java (with props)
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java (with props)
Added: 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=1140557&view=auto
==============================================================================
--- 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/GraphColoring.java Tue Jun 28 12:18:36 2011
@@ -0,0 +1,134 @@
+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;
+import java.util.TreeMap;
+
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.UndirectedGraph;
+import org.apache.commons.graph.Vertex;
+
+/*
+ * 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.
+ */
+
+/**
+ * Contains the graph coloring implementation. http://scienceblogs.com/goodmath/2007/06/graph_coloring_algorithms_1.php
+ */
+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 )
+ {
+ Map<V, Integer> coloredVertices = new HashMap<V, Integer>();
+ List<V> uncoloredVertices = null;
+
+ // decreasing sorting all vertices by degree.
+ Map<Integer, List<V>> orderedVertex = new TreeMap<Integer, List<V>>( new Comparator<Integer>()
+ {
+ public int compare( Integer o1, Integer o2 )
+ {
+ return o1.compareTo( o2 ) * -1;
+ }
+ } );
+
+ for ( V v : g.getVertices() )
+ {
+ int degree = g.getDegree( v );
+ List<V> vertices = orderedVertex.get( degree );
+
+ if ( vertices == null )
+ {
+ vertices = new ArrayList<V>();
+ }
+
+ vertices.add( v );
+ orderedVertex.put( degree, vertices );
+ }
+
+ uncoloredVertices = new ArrayList<V>();
+ for ( Integer key : orderedVertex.keySet() )
+ {
+ uncoloredVertices.addAll( orderedVertex.get( key ) );
+ }
+
+ // search coloring
+ int currrentColorIndex = 0;
+
+ Iterator<V> it = uncoloredVertices.iterator();
+ while ( it.hasNext() )
+ {
+ V v = it.next();
+
+ // remove vertex from uncolored list.
+ it.remove();
+ coloredVertices.put( v, currrentColorIndex );
+
+ // color all vertex not adiacent
+ Iterator<V> it2 = uncoloredVertices.iterator();
+ while ( it2.hasNext() )
+ {
+ V v2 = it2.next();
+ if ( g.getEdge( v, v2 ) == null )
+ {
+ // v2 is not connect to v.
+ it2.remove();
+ coloredVertices.put( v2, currrentColorIndex );
+ }
+ }
+
+ it = uncoloredVertices.iterator();
+ currrentColorIndex++;
+ }
+
+ return coloredVertices;
+ }
+
+ /**
+ * This class can not be instantiated.
+ */
+ private GraphColoring()
+ {
+ // do nothing
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: 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=1140557&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java (added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java Tue Jun 28 12:18:36 2011
@@ -0,0 +1,92 @@
+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 org.apache.commons.graph.coloring.GraphColoring.colorNumber;
+import static org.apache.commons.graph.utils.GraphUtils.buildBipartedGraph;
+import static org.apache.commons.graph.utils.GraphUtils.buildCompleteGraph;
+import static org.junit.Assert.assertEquals;
+
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.model.BaseLabeledEdge;
+import org.apache.commons.graph.model.BaseLabeledVertex;
+import org.apache.commons.graph.model.UndirectedMutableGraph;
+import org.junit.Test;
+
+/**
+ *
+ */
+public class GraphColoringTestCase
+{
+
+ @Test
+ public void testCromaticNumber()
+ {
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>();
+
+ BaseLabeledVertex one = new BaseLabeledVertex( "1" );
+ BaseLabeledVertex two = new BaseLabeledVertex( "2" );
+ BaseLabeledVertex three = new BaseLabeledVertex( "3" );
+
+ g.addVertex( one );
+ g.addVertex( two );
+ g.addVertex( three );
+
+ g.addEdge( one, new BaseLabeledEdge( "1 -> 2" ), two );
+ g.addEdge( two, new BaseLabeledEdge( "2 -> 3" ), three );
+ g.addEdge( three, new BaseLabeledEdge( "3 -> 1" ), one );
+
+ assertEquals( 3, colorNumber( g ) );
+ }
+
+ @Test
+ public void testCromaticNumberComplete()
+ {
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 =
+ new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>();
+ buildCompleteGraph( 100, g1 );
+
+ assertEquals( 100, colorNumber( g1 ) );
+ }
+
+ @Test
+ public void testCromaticNumberBiparted()
+ {
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g1 =
+ new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>();
+ buildBipartedGraph( 100, g1 );
+
+ assertEquals( 2, colorNumber( g1 ) );
+ }
+
+ @Test
+ public void testCromaticNumberSparseGraph()
+ {
+ UndirectedMutableGraph<Vertex, Edge> g1 = new UndirectedMutableGraph<Vertex, Edge>();
+ for ( int i = 0; i < 100; i++ )
+ {
+ g1.addVertex( new BaseLabeledVertex( "" + i ) );
+ }
+
+ assertEquals( 1, colorNumber( g1 ) );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java?rev=1140557&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java (added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java Tue Jun 28 12:18:36 2011
@@ -0,0 +1,120 @@
+package org.apache.commons.graph.utils;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.commons.graph.model.BaseLabeledEdge;
+import org.apache.commons.graph.model.BaseLabeledVertex;
+import org.apache.commons.graph.model.UndirectedMutableGraph;
+
+/*
+ * 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.
+ */
+
+/**
+ * Utilities graph class.
+ */
+public class GraphUtils
+{
+
+ /**
+ * Creates a complete graph with nVertices
+ *
+ * @param nVertices number of vertices
+ * @param g graph
+ */
+ public static void buildCompleteGraph( int nVertices, UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g )
+ {
+ // building Graph
+ for ( int i = 0; i < nVertices; i++ )
+ {
+ BaseLabeledVertex v = new BaseLabeledVertex( "" + i );
+ g.addVertex( v );
+ }
+
+ for ( BaseLabeledVertex v1 : g.getVertices() )
+ {
+ for ( BaseLabeledVertex v2 : g.getVertices() )
+ {
+ if ( !v1.equals( v2 ) )
+ {
+ g.addEdge( v1, new BaseLabeledEdge( "" ), v2 );
+ }
+ }
+ }
+ }
+
+ /**
+ * Create a Biparted graph
+ *
+ * @param nVertices number of vertices
+ * @param g graph
+ */
+ public static void buildBipartedGraph( int nVertices, UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g )
+ {
+ // building Graph
+ for ( int i = 0; i < nVertices; i++ )
+ {
+ BaseLabeledVertex v = new BaseLabeledVertex( "" + i );
+ g.addVertex( v );
+ }
+
+ List<BaseLabeledVertex> fistPartition = new ArrayList<BaseLabeledVertex>();
+ List<BaseLabeledVertex> secondPartition = new ArrayList<BaseLabeledVertex>();
+
+ int count = 0;
+ for ( BaseLabeledVertex v1 : g.getVertices() )
+ {
+ if ( count++ == nVertices / 2 )
+ {
+ break;
+ }
+ fistPartition.add( v1 );
+ }
+
+ count = 0;
+ for ( BaseLabeledVertex v2 : g.getVertices() )
+ {
+ if ( count++ < nVertices / 2 )
+ {
+ continue;
+ }
+ secondPartition.add( v2 );
+ }
+
+ for ( BaseLabeledVertex v1 : fistPartition )
+ {
+ for ( BaseLabeledVertex v2 : secondPartition )
+ {
+ if ( !v1.equals( v2 ) )
+ {
+ g.addEdge( v1, new BaseLabeledEdge( "" ), v2 );
+ }
+ }
+ }
+ }
+
+ /**
+ * This class can't be instantiated
+ */
+ private GraphUtils()
+ {
+ // do nothing
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/utils/GraphUtils.java
------------------------------------------------------------------------------
svn:mime-type = text/plain