[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[ff-cvs] fenfire/org/fenfire/util/lava Traversals.java T...
From: |
Tuukka Hastrup |
Subject: |
[ff-cvs] fenfire/org/fenfire/util/lava Traversals.java T... |
Date: |
Sun, 24 Aug 2003 15:01:42 -0400 |
CVSROOT: /cvsroot/fenfire
Module name: fenfire
Branch:
Changes by: Tuukka Hastrup <address@hidden> 03/08/24 15:01:42
Modified files:
org/fenfire/util/lava: Traversals.java Traversals.test
Log message:
findComponents gives the largest component as well
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/fenfire/fenfire/org/fenfire/util/lava/Traversals.java.diff?tr1=1.5&tr2=1.6&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/fenfire/fenfire/org/fenfire/util/lava/Traversals.test.diff?tr1=1.3&tr2=1.4&r1=text&r2=text
Patches:
Index: fenfire/org/fenfire/util/lava/Traversals.java
diff -u fenfire/org/fenfire/util/lava/Traversals.java:1.5
fenfire/org/fenfire/util/lava/Traversals.java:1.6
--- fenfire/org/fenfire/util/lava/Traversals.java:1.5 Sun Aug 17 15:55:02 2003
+++ fenfire/org/fenfire/util/lava/Traversals.java Sun Aug 24 15:01:41 2003
@@ -143,19 +143,30 @@
* representative.
* @return set of representatives, one for each component
*/
- public static Set findComponents(Iterator nodes, Object property,
- ConstGraph g) {
+ public static Object[] findComponents(Iterator nodes, Object property,
+ ConstGraph g) {
Set visited = new HashSet();
Set components = new HashSet();
+ Object largest = null;
+ int largestsize = -1;
+
while(nodes.hasNext()) {
Object node = nodes.next();
if(!visited.contains(node)) { // If found a new component
+ Object representative;
+ int visitedsize = visited.size();
visited.add(node);
- components.add(recurseDFS(node, property, g, visited,
- new DFSRet()).representative);
+ representative = recurseDFS(node, property, g, visited,
+ new DFSRet()).representative;
+ int growth = visited.size() - visitedsize;
+ if(growth > largestsize) {
+ largestsize = growth;
+ largest = representative;
+ }
+ components.add(representative);
}
}
- return components;
+ return new Object[] {components, largest};
}
/** Recurses depth-first search from a given node, and finds the node
Index: fenfire/org/fenfire/util/lava/Traversals.test
diff -u fenfire/org/fenfire/util/lava/Traversals.test:1.3
fenfire/org/fenfire/util/lava/Traversals.test:1.4
--- fenfire/org/fenfire/util/lava/Traversals.test:1.3 Sat Aug 16 07:45:39 2003
+++ fenfire/org/fenfire/util/lava/Traversals.test Sun Aug 24 15:01:42 2003
@@ -72,27 +72,30 @@
fen.graph.add(b,q,c)
fen.graph.add(d,q,a)
- result = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
+ reps, lrep = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
for x in a, b, c, d: # all single nodes are components
- assert result.contains(x)
+ assert reps.contains(x)
+ assert lrep in [a, b, c, d] # one of the components is largest
fen.graph.add(a,p,b)
- result = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
- assert result.contains(a) != result.contains(b) # Either is representative
+ reps, lrep = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
+ assert reps.contains(a) != reps.contains(b) # Either is representative
+ assert lrep in [a, b] # [a, b] is largest component
fen.graph.add(a,p,c)
- result = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
- assert result.contains(a) # a has higher degree than b or c
- assert not result.contains(b)
- assert not result.contains(c)
+ reps, lrep = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
+ assert reps.contains(a) # a has higher degree than b or c
+ assert not reps.contains(b)
+ assert not reps.contains(c)
+ assert lrep == a # a is in the largest component
fen.graph.add(c,p,b)
fen.graph.add(d,p,b)
- result = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
- assert result.contains(b) # b has highest degree
+ reps, lrep = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
+ assert reps.contains(b) # b has highest degree
for x in a, c, d:
- assert not result.contains(x)
+ assert not reps.contains(x)