Author: ruschein
Date: 2010-11-30 10:12:31 -0800 (Tue, 30 Nov 2010)
New Revision: 23053
Added:
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/tsort/
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/tsort/TopoGraphNode.java
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/tsort/TopologicalSort.java
core3/model-impl/trunk/impl/src/test/java/org/cytoscape/model/internal/
core3/model-impl/trunk/impl/src/test/java/org/cytoscape/model/internal/tsort/
core3/model-impl/trunk/impl/src/test/java/org/cytoscape/model/internal/tsort/TopologicalSortTest.java
Removed:
core3/topo-sort/
Modified:
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/AttribTopoGraphNode.java
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/CyTableImpl.java
core3/model-impl/trunk/pom.xml
Log:
Moved everything from topo-sort into model-impl.
Modified:
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/AttribTopoGraphNode.java
===================================================================
---
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/AttribTopoGraphNode.java
2010-11-30 17:58:52 UTC (rev 23052)
+++
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/AttribTopoGraphNode.java
2010-11-30 18:12:31 UTC (rev 23053)
@@ -33,7 +33,7 @@
import java.util.Collection;
import java.util.HashSet;
-import org.cytoscape.util.tsort.TopoGraphNode;
+import org.cytoscape.model.internal.tsort.TopoGraphNode;
/**
Modified:
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/CyTableImpl.java
===================================================================
---
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/CyTableImpl.java
2010-11-30 17:58:52 UTC (rev 23052)
+++
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/CyTableImpl.java
2010-11-30 18:12:31 UTC (rev 23053)
@@ -56,8 +56,8 @@
import org.cytoscape.model.events.ColumnDeletedEvent;
import org.cytoscape.model.events.RowSetMicroListener;
-import org.cytoscape.util.tsort.TopoGraphNode;
-import org.cytoscape.util.tsort.TopologicalSort;
+import org.cytoscape.model.internal.tsort.TopoGraphNode;
+import org.cytoscape.model.internal.tsort.TopologicalSort;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
Copied:
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/tsort/TopoGraphNode.java
(from rev 23050,
core3/topo-sort/trunk/src/main/java/org/cytoscape/util/tsort/TopoGraphNode.java)
===================================================================
---
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/tsort/TopoGraphNode.java
(rev 0)
+++
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/tsort/TopoGraphNode.java
2010-11-30 18:12:31 UTC (rev 23053)
@@ -0,0 +1,42 @@
+/*
+ File: TopoGraphNode.java
+
+ Copyright (c) 2010, The Cytoscape Consortium (www.cytoscape.org)
+
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published
+ by the Free Software Foundation; either version 2.1 of the License, or
+ any later version.
+
+ This library is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY, WITHOUT EVEN THE IMPLIED WARRANTY OF
+ MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. The software and
+ documentation provided hereunder is on an "as is" basis, and the
+ Institute for Systems Biology and the Whitehead Institute
+ have no obligations to provide maintenance, support,
+ updates, enhancements or modifications. In no event shall the
+ Institute for Systems Biology and the Whitehead Institute
+ be liable to any party for direct, indirect, special,
+ incidental or consequential damages, including lost profits, arising
+ out of the use of this software and its documentation, even if the
+ Institute for Systems Biology and the Whitehead Institute
+ have been advised of the possibility of such damage. See
+ the GNU Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library; if not, write to the Free Software Foundation,
+ Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
+*/
+package org.cytoscape.model.internal.tsort;
+
+
+import java.util.Collection;
+
+
+/**
+ * Represents a node in a topological graph.
+ */
+public interface TopoGraphNode {
+ public Collection<TopoGraphNode> getDependents();
+}
+
Copied:
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/tsort/TopologicalSort.java
(from rev 23050,
core3/topo-sort/trunk/src/main/java/org/cytoscape/util/tsort/TopologicalSort.java)
===================================================================
---
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/tsort/TopologicalSort.java
(rev 0)
+++
core3/model-impl/trunk/impl/src/main/java/org/cytoscape/model/internal/tsort/TopologicalSort.java
2010-11-30 18:12:31 UTC (rev 23053)
@@ -0,0 +1,86 @@
+/*
+ File: TopologicalSort.java
+
+ Copyright (c) 2010, The Cytoscape Consortium (www.cytoscape.org)
+
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published
+ by the Free Software Foundation; either version 2.1 of the License, or
+ any later version.
+
+ This library is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY, WITHOUT EVEN THE IMPLIED WARRANTY OF
+ MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. The software and
+ documentation provided hereunder is on an "as is" basis, and the
+ Institute for Systems Biology and the Whitehead Institute
+ have no obligations to provide maintenance, support,
+ updates, enhancements or modifications. In no event shall the
+ Institute for Systems Biology and the Whitehead Institute
+ be liable to any party for direct, indirect, special,
+ incidental or consequential damages, including lost profits, arising
+ out of the use of this software and its documentation, even if the
+ Institute for Systems Biology and the Whitehead Institute
+ have been advised of the possibility of such damage. See
+ the GNU Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library; if not, write to the Free Software Foundation,
+ Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
+*/
+package org.cytoscape.model.internal.tsort;
+
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+
+
+/**
+ * Implements topological sorting of nodes in a graph.
+ * See for example http://en.wikipedia.org/wiki/Topological_sorting (the
Tarjan algorithm)
+ */
+public class TopologicalSort {
+ /**
+ * @param nodes the list of all nodes
+ * @param edges the edges that connect the nodes that need to be
sorted.
+ * @return the topological order
+ * @throws IllegalStateException if a cycle has been detected
+ * N.B. it might be a good idea to make sure that whatever the
concrete type of the nodes in
+ * "nodes" are has a toString() method that returns the name of a node
since this method
+ * will be used if a cycle has been detected to report one of the
nodes in the cycle.
+ */
+ public static List<TopoGraphNode> sort(final Collection<TopoGraphNode>
nodes)
+ throws IllegalStateException
+ {
+ final List<TopoGraphNode> order = new
ArrayList<TopoGraphNode>();
+ final Set<TopoGraphNode> visited = new HashSet<TopoGraphNode>();
+
+ final Set<TopoGraphNode> alreadySeen = new
HashSet<TopoGraphNode>();
+ for (final TopoGraphNode n : nodes) {
+ alreadySeen.clear();
+ visit(n, alreadySeen, visited, order);
+ }
+
+ return order;
+ }
+
+ private static void visit(final TopoGraphNode n, final
Set<TopoGraphNode> alreadySeen,
+ final Set<TopoGraphNode> visited, final
List<TopoGraphNode> order)
+ {
+ if (alreadySeen.contains(n))
+ throw new IllegalStateException("cycle containing " + n
+ " found!");
+ alreadySeen.add(n);
+
+ if (!visited.contains(n)) {
+ visited.add(n);
+ for (final TopoGraphNode m : n.getDependents())
+ visit(m, alreadySeen, visited, order);
+ order.add(n);
+ }
+
+ alreadySeen.remove(n);
+ }
+}
Copied:
core3/model-impl/trunk/impl/src/test/java/org/cytoscape/model/internal/tsort/TopologicalSortTest.java
(from rev 23050,
core3/topo-sort/trunk/src/test/java/org/cytoscape/util/tsort/TopologicalSortTest.java)
===================================================================
---
core3/model-impl/trunk/impl/src/test/java/org/cytoscape/model/internal/tsort/TopologicalSortTest.java
(rev 0)
+++
core3/model-impl/trunk/impl/src/test/java/org/cytoscape/model/internal/tsort/TopologicalSortTest.java
2010-11-30 18:12:31 UTC (rev 23053)
@@ -0,0 +1,187 @@
+/*
+ File: TopologicalSortTest.java
+
+ Copyright (c) 2010, The Cytoscape Consortium (www.cytoscape.org)
+
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published
+ by the Free Software Foundation; either version 2.1 of the License, or
+ any later version.
+
+ This library is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY, WITHOUT EVEN THE IMPLIED WARRANTY OF
+ MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. The software and
+ documentation provided hereunder is on an "as is" basis, and the
+ Institute for Systems Biology and the Whitehead Institute
+ have no obligations to provide maintenance, support,
+ updates, enhancements or modifications. In no event shall the
+ Institute for Systems Biology and the Whitehead Institute
+ be liable to any party for direct, indirect, special,
+ incidental or consequential damages, including lost profits, arising
+ out of the use of this software and its documentation, even if the
+ Institute for Systems Biology and the Whitehead Institute
+ have been advised of the possibility of such damage. See
+ the GNU Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library; if not, write to the Free Software Foundation,
+ Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
+*/
+package org.cytoscape.model.internal.tsort;
+
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Collection;
+import junit.framework.*;
+
+
+class Node implements TopoGraphNode {
+ private final String nodeName;
+ private final Collection<TopoGraphNode> dependents;
+
+ Node(final String nodeName) {
+ this.nodeName = nodeName;
+ this.dependents = new HashSet<TopoGraphNode>();
+ }
+
+ @Override public String toString() { return nodeName; }
+ public Collection<TopoGraphNode> getDependents() { return dependents; }
+ void addDependent(final TopoGraphNode newDependent) {
dependents.add(newDependent); }
+}
+
+
+public class TopologicalSortTest extends TestCase {
+ public void testWikipediaExample() { // Based on the example at
http://en.wikipedia.org/wiki/Topological_sorting
+ final Node node7 = new Node("7");
+ final Node node5 = new Node("5");
+ final Node node3 = new Node("3");
+ final Node node11 = new Node("11");
+ final Node node8 = new Node("8");
+ final Node node2 = new Node("2");
+ final Node node9 = new Node("9");
+ final Node node10 = new Node("10");
+
+ node7.addDependent(node11);
+ node7.addDependent(node8);
+ node5.addDependent(node11);
+ node3.addDependent(node8);
+ node3.addDependent(node10);
+ node11.addDependent(node2);
+ node11.addDependent(node9);
+ node11.addDependent(node10);
+ node8.addDependent(node9);
+
+ final Collection<TopoGraphNode> nodes = new
ArrayList<TopoGraphNode>();
+ nodes.add(node7);
+ nodes.add(node5);
+ nodes.add(node3);
+ nodes.add(node11);
+ nodes.add(node8);
+ nodes.add(node2);
+ nodes.add(node9);
+ nodes.add(node10);
+
+ final Collection<TopoGraphNode> order =
TopologicalSort.sort(nodes);
+ assertTrue(isTopologicalOrder(order));
+ }
+
+ public void testGraphWithSomeUnconnectedNodes() {
+ final Node node7 = new Node("7");
+ final Node node5 = new Node("5");
+ final Node node3 = new Node("3");
+ final Node node11 = new Node("11");
+ final Node node8 = new Node("8");
+ final Node node2 = new Node("2");
+ final Node node9 = new Node("9");
+ final Node node10 = new Node("10");
+ final Node nodeU1 = new Node("U3");
+ final Node nodeU2 = new Node("U2");
+ final Node nodeU3 = new Node("U1");
+
+ node7.addDependent(node11);
+ node7.addDependent(node8);
+ node5.addDependent(node11);
+ node3.addDependent(node8);
+ node3.addDependent(node10);
+ node11.addDependent(node2);
+ node11.addDependent(node9);
+ node11.addDependent(node10);
+ node8.addDependent(node9);
+
+ final Collection<TopoGraphNode> nodes = new
ArrayList<TopoGraphNode>();
+ nodes.add(node7);
+ nodes.add(node5);
+ nodes.add(node3);
+ nodes.add(node11);
+ nodes.add(node8);
+ nodes.add(node2);
+ nodes.add(node9);
+ nodes.add(node10);
+
+ final Collection<TopoGraphNode> order =
TopologicalSort.sort(nodes);
+ assertTrue(isTopologicalOrder(order));
+ }
+
+ public void testIndirectCycle() {
+ final Node nodeA = new Node("A");
+ final Node nodeB = new Node("B");
+ final Node nodeC = new Node("C");
+
+ nodeA.addDependent(nodeB);
+ nodeB.addDependent(nodeC);
+ nodeC.addDependent(nodeA);
+
+ final Collection<TopoGraphNode> nodes = new
ArrayList<TopoGraphNode>();
+ nodes.add(nodeA);
+ nodes.add(nodeB);
+ nodes.add(nodeC);
+
+ boolean failed;
+ try {
+ TopologicalSort.sort(nodes);
+ failed = false;
+ } catch (final IllegalStateException e) {
+ failed = true;
+ }
+
+ assertTrue(failed);
+ }
+
+ public void testSelfLoopCycle() {
+ final Node nodeA = new Node("A");
+ final Node nodeB = new Node("B");
+ final Node nodeC = new Node("C");
+
+ nodeB.addDependent(nodeB);
+
+ final Collection<TopoGraphNode> nodes = new
ArrayList<TopoGraphNode>();
+ nodes.add(nodeA);
+ nodes.add(nodeB);
+ nodes.add(nodeC);
+
+ boolean failed;
+ try {
+ TopologicalSort.sort(nodes);
+ failed = false;
+ } catch (final IllegalStateException e) {
+ failed = true;
+ }
+
+ assertTrue(failed);
+ }
+
+ private boolean isTopologicalOrder(final Collection<TopoGraphNode>
topoOrderCandidate) {
+ final TopoGraphNode[] orderAsArray =
topoOrderCandidate.toArray(new TopoGraphNode[topoOrderCandidate.size()]);
+
+ for (int i = 0; i < orderAsArray.length; ++i) {
+ final Collection<TopoGraphNode> dependents =
orderAsArray[i].getDependents();
+ for (int k = i + 1; k < orderAsArray.length; ++k) {
+ if (dependents.contains(orderAsArray[k]))
+ return false;
+ }
+ }
+
+ return true;
+ }
+}
Modified: core3/model-impl/trunk/pom.xml
===================================================================
--- core3/model-impl/trunk/pom.xml 2010-11-30 17:58:52 UTC (rev 23052)
+++ core3/model-impl/trunk/pom.xml 2010-11-30 18:12:31 UTC (rev 23053)
@@ -104,12 +104,6 @@
<version>1.0-SNAPSHOT</version>
<scope>provided</scope>
</dependency>
- <dependency>
- <groupId>org.cytoscape</groupId>
- <artifactId>topo-sort</artifactId>
- <version>1.0-SNAPSHOT</version>
- <scope>provided</scope>
- </dependency>
</dependencies>
</project>
--
You received this message because you are subscribed to the Google Groups
"cytoscape-cvs" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/cytoscape-cvs?hl=en.
