Commits

Anonymous committed 56121e2

move topological sort out to nrgutil

  • Participants
  • Parent commits b334fa9
  • Tags v0.2.0

Comments (0)

Files changed (4)

File ecat-edit/pom.xml

   <groupId>org.nrg</groupId>
   <artifactId>ecat-edit</artifactId>
   <packaging>jar</packaging>
-  <version>0.1.2</version>
+  <version>0.2.0</version>
   <name>ecat-edit</name>
   <parent>
     <groupId>org.nrg</groupId>
     <artifactId>ecat</artifactId>
-    <version>0.1.0</version>
+    <version>0.2.0</version>
   </parent>
   <build>
     <plugins>
       <plugin>
         <groupId>org.apache.maven.plugins</groupId>
 	<artifactId>maven-compiler-plugin</artifactId>
+	<version>2.3.2</version>
 	<configuration>
 	  <source>1.4</source>
 	  <target>1.4</target>
       <version>0.1.0</version>
     </dependency>
     <dependency>
+      <groupId>org.nrg</groupId>
+      <artifactId>nrgutil</artifactId>
+      <version>1.1.0</version>
+    </dependency>
+    <dependency>
       <groupId>org.slf4j</groupId>
       <artifactId>slf4j-api</artifactId>
       <version>[1.5.11,)</version>

File ecat-edit/src/main/java/org/nrg/util/GraphUtils.java

-package org.nrg.util;
-/**
- * Copyright 2009 Washington University
- */
-
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Iterator;
-import java.util.LinkedHashMap;
-import java.util.LinkedHashSet;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-/**
- * @author Kevin A. Archie <karchie@npg.wustl.edu>
- *
- */
-public final class GraphUtils {
-    private GraphUtils() {}	// prevent instantiation
-        
-    /**
-     * Indicates that an algorithm that requires a directed acyclic graph (DAG)
-     * was instead provided a cyclic graph.
-     * @author Kevin A. Archie <karchie@npg.wustl.edu>
-     *
-     */
-    public static class CyclicGraphException extends IllegalArgumentException {
-	private static final long serialVersionUID = 1L;
-	private final Object partial;
-	
-	CyclicGraphException(final String msg, final Object partial) {
-	    super(msg);
-	    this.partial = partial;
-	}
-	
-	CyclicGraphException(final Object partial) {
-	    super();
-	    this.partial = partial;
-	}
-	
-	/**
-	 * Retrieves partial result from algorithm, if one is available.
-	 * @return partial result (type determined by throwing algorithm)
-	 */
-	public Object getPartialResult() { return partial; }
-    }
-    
-
-    /**
-     * Use Kahn's algorithm for topological sort
-     * @param graph Map X -> Collection<X> ; each entry maps from a node to its incoming edges
-     * @return topologically sorted X
-     * @throws CyclicGraphException if graph is cyclic
-     */
-    public static List topologicalSort(final Map graph) throws CyclicGraphException {
-	final Map g = new LinkedHashMap(graph);
-	final List sorted = new ArrayList(g.size());
-	
-	// Extract all nodes with no incoming edges
-	final Set s = new LinkedHashSet();
-	for (final Iterator i = graph.entrySet().iterator(); i.hasNext(); ) {
-	    final Map.Entry me = (Map.Entry)i.next();
-	    if (((Collection)me.getValue()).isEmpty()) {
-		final Object n = me.getKey();
-		s.add(n);
-		g.remove(n);
-	    }
-	}
-	
-	while (!s.isEmpty()) {
-	    final Object n = s.iterator().next();
-	    s.remove(n);
-	    sorted.add(n);
-	    for (final Iterator i = g.entrySet().iterator(); i.hasNext(); ) {
-		final Map.Entry me = (Map.Entry)i.next();
-		final Collection incoming = (Collection)me.getValue();
-		incoming.remove(n);
-		if (incoming.isEmpty()) {
-		    s.add(me.getKey());
-		    i.remove();
-		}
-	    }
-	}
-	
-	if (g.isEmpty()) {
-	    return sorted;
-	} else {
-	    throw new CyclicGraphException("some nodes are in cyclic graph: " + g.keySet(), sorted);
-	}
-    }
-}

File ecat-io/pom.xml

   <parent>
     <groupId>org.nrg</groupId>
     <artifactId>ecat</artifactId>
-    <version>0.1.0</version>
+    <version>0.2.0</version>
   </parent>
   <build>
     <plugins>
   <modelVersion>4.0.0</modelVersion>
   <groupId>org.nrg</groupId>
   <artifactId>ecat</artifactId>
-  <version>0.1.0</version>
+  <version>0.2.0</version>
   <packaging>pom</packaging>
   <name>ECAT</name>
   <description>