[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[ff-cvs] fenfire/org/fenfire/util/lava Traversals.java
From: |
Tuukka Hastrup |
Subject: |
[ff-cvs] fenfire/org/fenfire/util/lava Traversals.java |
Date: |
Wed, 27 Aug 2003 11:52:29 -0400 |
CVSROOT: /cvsroot/fenfire
Module name: fenfire
Branch:
Changes by: Tuukka Hastrup <address@hidden> 03/08/27 11:52:29
Modified files:
org/fenfire/util/lava: Traversals.java
Log message:
added option to get component representatives from a given set
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/fenfire/fenfire/org/fenfire/util/lava/Traversals.java.diff?tr1=1.9&tr2=1.10&r1=text&r2=text
Patches:
Index: fenfire/org/fenfire/util/lava/Traversals.java
diff -u fenfire/org/fenfire/util/lava/Traversals.java:1.9
fenfire/org/fenfire/util/lava/Traversals.java:1.10
--- fenfire/org/fenfire/util/lava/Traversals.java:1.9 Mon Aug 25 17:42:22 2003
+++ fenfire/org/fenfire/util/lava/Traversals.java Wed Aug 27 11:52:29 2003
@@ -211,6 +211,21 @@
*/
public static Object[] findComponents(Iterator nodes, Object property,
ConstGraph g) {
+ return findComponents(nodes, property, g, null);
+ }
+
+ /** From given nodes, finds components disconnected along a given
+ * non-directed property,
+ * and for each component returns the node of highest degree as a
+ * representative. Additionally, gives the representative of the
+ * largest component. The representatives are tried to be found
+ * in the given candidate node set.
+ * @return an array:
+ * the first element is a <code>Set</code> of representatives,
+ * the other element is the representative of largest component
+ */
+ public static Object[] findComponents(Iterator nodes, Object property,
+ ConstGraph g, Set candidates) {
Set visited = new HashSet();
Set components = new HashSet();
Object largest = null;
@@ -223,13 +238,17 @@
int visitedsize = visited.size();
visited.add(node);
representative = recurseDFS(node, property, g, visited,
+ candidates,
new DFSRet()).representative;
int growth = visited.size() - visitedsize;
if(growth > largestsize) {
largestsize = growth;
largest = representative;
}
- components.add(representative);
+ if(candidates == null || representative != null)
+ components.add(representative);
+ else
+ components.add(node);
}
}
return new Object[] {components, largest};
@@ -242,7 +261,7 @@
* <code>degree</code> is the highest degree
*/
static DFSRet recurseDFS(Object start, Object property, ConstGraph g,
- Set visited, DFSRet ret) {
+ Set visited, Set candidates, DFSRet ret) {
Object representative = null;
int representativeDegree = -1;
Iterator conns = findConnected_Iter(g, start, property);
@@ -252,8 +271,9 @@
degree++;
if(!visited.contains(found)) {
visited.add(found);
- ret = recurseDFS(found, property, g, visited, ret);
- if(ret.degree > representativeDegree) {
+ ret = recurseDFS(found, property, g, visited, candidates, ret);
+ if((candidates == null || candidates.contains(found))
+ && ret.degree > representativeDegree) {
representativeDegree = ret.degree;
representative = ret.representative;
}
@@ -262,9 +282,13 @@
if(representativeDegree > degree) {
ret.representative = representative;
ret.degree = representativeDegree;
- } else {
+ } else if (candidates == null || candidates.contains(start)) {
ret.representative = start;
ret.degree = degree;
+ } else {
+ // Not a single node was a candidate, so we have to return null
+ ret.representative = null;
+ ret.degree = -1;
}
return ret;
}