Author: simonetripodi
Date: Tue Jun 28 23:07:06 2011
New Revision: 1140893
URL: http://svn.apache.org/viewvc?rev=1140893&view=rev
Log:
avoid reload all ordered vertices in a new list, implemented a lazy-iterator
that cycles over the multi-valued TreeMap
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
(with props)
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/GraphColoring.java
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=1140893&r1=1140892&r2=1140893&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 23:07:06 2011
@@ -1,11 +1,6 @@
package org.apache.commons.graph.coloring;
-import java.util.ArrayList;
-import java.util.Comparator;
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;
@@ -44,42 +39,20 @@ public final class GraphColoring
*/
public static <V extends Vertex, E extends Edge> ColoredVertices<V>
coloring( UndirectedGraph<V, E> g )
{
- ColoredVertices<V> coloredVertices = new ColoredVertices<V>();
- List<V> uncoloredVertices = null;
+ final ColoredVertices<V> coloredVertices = new ColoredVertices<V>();
// 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 o2.compareTo( o1 );
- }
- } );
+ final UncoloredOrderedVertices<V> uncoloredOrderedVertices = new
UncoloredOrderedVertices<V>();
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 ) );
+ uncoloredOrderedVertices.addVertexDegree( v, g.getDegree( v ) );
}
// search coloring
int currrentColorIndex = 0;
- Iterator<V> it = uncoloredVertices.iterator();
+ Iterator<V> it = uncoloredOrderedVertices.iterator();
while ( it.hasNext() )
{
V v = it.next();
@@ -89,7 +62,7 @@ public final class GraphColoring
coloredVertices.addColor( v, currrentColorIndex );
// color all vertices not adjacent
- Iterator<V> it2 = uncoloredVertices.iterator();
+ Iterator<V> it2 = uncoloredOrderedVertices.iterator();
while ( it2.hasNext() )
{
V v2 = it2.next();
@@ -101,7 +74,7 @@ public final class GraphColoring
}
}
- it = uncoloredVertices.iterator();
+ it = uncoloredOrderedVertices.iterator();
currrentColorIndex++;
}
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java?rev=1140893&view=auto
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
(added)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
Tue Jun 28 23:07:06 2011
@@ -0,0 +1,114 @@
+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.Comparator;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.TreeMap;
+
+import org.apache.commons.graph.Vertex;
+
+/**
+ *
+ *
+ * @param <V>
+ */
+final class UncoloredOrderedVertices<V extends Vertex>
+ implements Comparator<Integer>, Iterable<V>
+{
+
+ private final Map<Integer, Set<V>> orderedVertices = new TreeMap<Integer,
Set<V>>( this );
+
+ public void addVertexDegree( V v, Integer degree )
+ {
+ Set<V> vertices = orderedVertices.get( degree );
+
+ if ( vertices == null )
+ {
+ vertices = new HashSet<V>();
+ }
+
+ vertices.add( v );
+ orderedVertices.put( degree, vertices );
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int compare( Integer o1, Integer o2 )
+ {
+ return o2.compareTo( o1 );
+ }
+
+ public Iterator<V> iterator()
+ {
+ return new Iterator<V>()
+ {
+
+ private Iterator<Integer> keys =
orderedVertices.keySet().iterator();
+
+ private Iterator<V> pending = null;
+
+ private V next = null;
+
+ public boolean hasNext()
+ {
+ if ( next != null )
+ {
+ return true;
+ }
+
+ while ( ( pending == null ) || !pending.hasNext() )
+ {
+ if ( !keys.hasNext() )
+ {
+ return false;
+ }
+ pending = orderedVertices.get( keys.next() ).iterator();
+ }
+
+ next = pending.next();
+ return true;
+ }
+
+ public V next()
+ {
+ if ( !hasNext() )
+ {
+ throw new NoSuchElementException();
+ }
+ V returned = next;
+ next = null;
+ return returned;
+ }
+
+ public void remove()
+ {
+ pending.remove();
+ }
+
+ };
+ }
+
+}
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
