# Coverage details for edu.uci.ics.jung.algorithms.cluster.ExactFlowCommunity

Line | Hits | Source
--- | --- | ---
1 |  | `/*`
2 |  | `* Copyright (c) 2003, the JUNG Project and the Regents of the University`
3 |  | `* of California`
4 |  | `* All rights reserved.`
5 |  | `*`
6 |  | `* This software is open-source under the BSD license; see either`
7 |  | `* "license.txt" or`
8 |  | `* http://jung.sourceforge.net/license.txt for a description.`
9 |  | `*/`
10 |  | `package edu.uci.ics.jung.algorithms.cluster;`
11 |  | ``
12 |  | `import java.util.*;`
13 |  | ``
14 |  | `import cern.colt.list.DoubleArrayList;`
15 |  | `import cern.jet.stat.Descriptive;`
16 |  | `import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;`
17 |  | `import edu.uci.ics.jung.graph.*;`
18 |  | `import edu.uci.ics.jung.graph.decorators.NumericDecorator;`
19 |  | `import edu.uci.ics.jung.graph.impl.SparseVertex;`
20 |  | `import edu.uci.ics.jung.statistics.DegreeDistributions;`
21 |  | `import edu.uci.ics.jung.utils.GraphUtils;`
22 |  | `import edu.uci.ics.jung.utils.MutableInteger;`
23 |  | `import edu.uci.ics.jung.utils.UserData;`
24 |  | ``
25 |  | `/**`
26 |  | `* ExactFlowCommunity is an algorithm that uses a set of root nodes that are`
27 |  | `* supposed to be representative of a community to find the entire community`
28 |  | `* using principles based on max-flow/min-cut.`
29 |  | `* @author Scott White`
30 |  | `* @see "Self-Organization of the Web and Identification of Communities by Gary`
31 |  | `* Flake, Steve Lawrence, Lee Giles, and Frans Coetzee, 2002"`
32 |  | `* @see "http://www.neci.nec.com/~lawrence/papers/web-computer02/web-computer02.pdf"`
33 |  | `*/`
34 |  | `public class ExactFlowCommunity {`
35 |  | `private int mCohesionThreshold;`
36 |  | ``
37 |  | `/**`
38 |  | `* Constructs and initializes the algorithm`
39 |  | `* @param cohesionThreshold a heuristic value that determines the`
40 |  | `* level of cohesion for the community to be extracted`
41 |  | `*/`
42 | 2 | `public ExactFlowCommunity(int cohesionThreshold) {`
43 | 2 | `mCohesionThreshold = cohesionThreshold;`
44 | 2 | `}`
45 |  | ``
46 |  | `/**`
47 |  | `* Extracts the community according to the cohesion threshold`
48 |  | `* @param graph the original graph`
49 |  | `* @param rootSet the set of nodes used to see the community`
50 |  | `* @return a set of nodes representative of the community used to seed the algorithm`
51 |  | `*/`
52 |  | `public Set extract(DirectedGraph graph, Set rootSet) {`
53 | 4 | `DirectedGraph flowGraph = (DirectedGraph) graph.copy();`
54 | 4 | `Vertex source = flowGraph.addVertex(new SparseVertex());`
55 | 4 | `Vertex sink = flowGraph.addVertex(new SparseVertex());`
56 |  | ``
57 | 4 | `initializeFlowGraph(flowGraph,source, sink,rootSet);`
58 | 4 | `EdmondsKarpMaxFlow maxFlowSolver = new EdmondsKarpMaxFlow(flowGraph,source,sink,"CAPACITY","FLOW");`
59 | 4 | `maxFlowSolver.evaluate();`
60 | 4 | `Set communityVertices = new HashSet();`
61 | 4 | `Set sourceNodes = maxFlowSolver.getNodesInSourcePartition();`
62 | 4 | `for (Iterator vIt = sourceNodes.iterator();vIt.hasNext();) {`
63 | 22 | `Vertex v = (Vertex) vIt.next();`
64 | 22 | `if (v.getEqualVertex(flowGraph) != source) {`
65 | 18 | `communityVertices.add(v.getEqualVertex(graph));`
66 |  | `}`
67 |  | `}`
68 |  | ``
69 | 4 | `return communityVertices;`
70 |  | `}`
71 |  | ``
72 |  | `/**`
73 |  | `* Implements the "ApproximateFlowCommunity" algorithm. Repeatedly`
74 |  | `* finds the community at low distances from the starting set, and`
75 |  | `* grows outward. UNDERTESTED.`
76 |  | `* @param graph the original graph`
77 |  | `* @param rootSet the set of nodes used to see the community`
78 |  | `* @return a set of nodes representative of the community used to seed the algorithm`
79 |  | `*/`
80 |  | `public static Set extract(DirectedGraph graph, Set rootSet, int numIterations) {`
81 | 0 | `Set members = new HashSet(rootSet);`
82 | 0 | `Set newMembers = null;`
83 | 0 | `int numPreviousMembers = members.size();`
84 | 0 | `int numCurrentMembers = 0;`
85 |  | ``
86 | 0 | `for (int i=0;i<numIterations;i++) {`
87 | 0 | `ExactFlowCommunity ecf = new ExactFlowCommunity(members.size());`
88 | 0 | `newMembers = ecf.extract(graph,members);`
89 | 0 | `numCurrentMembers = newMembers.size();`
90 | 0 | `if (numPreviousMembers == numCurrentMembers) {`
91 | 0 | `break;`
92 |  | `}`
93 | 0 | `numPreviousMembers = numCurrentMembers;`
94 | 0 | `System.out.println(members.size());`
95 | 0 | `DoubleArrayList inDegrees = DegreeDistributions.getIndegreeValues(newMembers);`
96 | 0 | `int maxIndegree = (int) Descriptive.max(inDegrees);`
97 | 0 | `DoubleArrayList outDegrees = DegreeDistributions.getOutdegreeValues(newMembers);`
98 | 0 | `int maxOutdegree = (int) Descriptive.max(outDegrees);`
99 |  | ``
100 | 0 | `for (Iterator vIt = newMembers.iterator(); vIt.hasNext();) {`
101 | 0 | `Vertex v = (Vertex) vIt.next();`
102 | 0 | `if (members.contains(v)) {`
103 | 0 | `continue;`
104 |  | `}`
105 | 0 | `if (v.inDegree() == maxIndegree) {`
106 | 0 | `members.add(v);`
107 | 0 | `} else if (v.outDegree() == maxOutdegree) {`
108 | 0 | `members.add(v);`
109 |  | `}`
110 |  | `}`
111 |  | `}`
112 |  | ``
113 | 0 | `return newMembers;`
114 |  | ``
115 |  | `}`
116 |  | ``
117 |  | `/**`
118 |  | `* Initialize the flow graph`
119 |  | `* @param flowGraph the flow graph`
120 |  | `* @param source the source node`
121 |  | `* @param sink the sink node`
122 |  | `* @param rootSet the set of nodes used to seed the community`
123 |  | `*/`
124 |  | `protected void initializeFlowGraph(DirectedGraph flowGraph,Vertex source, Vertex sink,Set rootSet) {`
125 |  | ``
126 | 4 | `NumericDecorator capacityDecorator = new NumericDecorator("CAPACITY",UserData.SHARED);`
127 |  | ``
128 | 4 | `List edgesList = new ArrayList();`
129 | 4 | `edgesList.addAll(flowGraph.getEdges());`
130 |  | ``
131 | 76 | `for (int idx = 0; idx < edgesList.size(); idx++) {`
132 | 72 | `DirectedEdge currentEdge = (DirectedEdge) edgesList.get(idx);`
133 | 72 | `capacityDecorator.setValue(new MutableInteger(mCohesionThreshold),currentEdge);`
134 |  | ``
135 |  | `// finds edges that aren't reciprocated`
136 |  | `// that is, this is an edge from (A to B). This looks for the edge that runs from B to A.`
137 | 72 | `Edge otherEdge = currentEdge.getDest().findEdge(currentEdge.getSource());`
138 | 72 | `if (otherEdge == null) {`
139 | 24 | `otherEdge = GraphUtils.addEdge(flowGraph,currentEdge.getDest(),currentEdge.getSource());`
140 | 24 | `capacityDecorator.setValue(new MutableInteger(mCohesionThreshold),otherEdge);`
141 |  | `}`
142 |  | `}`
143 |  | ``
144 | 4 | `for (Iterator vIt = flowGraph.getVertices().iterator(); vIt.hasNext();) {`
145 | 48 | `Vertex currentVertex = (Vertex) vIt.next();`
146 | 48 | `if (currentVertex != sink && !rootSet.contains(currentVertex)) {`
147 | 36 | `Edge newEdge = GraphUtils.addEdge(flowGraph,currentVertex,sink);`
148 | 36 | `capacityDecorator.setValue(new MutableInteger(1),newEdge);`
149 |  | `}`
150 |  | `}`
151 |  | ``
152 | 4 | `for (Iterator rootIt = rootSet.iterator(); rootIt.hasNext();) {`
153 | 8 | `Vertex currentRoot = (Vertex) rootIt.next();`
154 | 8 | `currentRoot = (Vertex) currentRoot.getEqualVertex(flowGraph);`
155 | 8 | `Edge e= GraphUtils.addEdge(flowGraph,source,currentRoot);`
156 | 8 | `capacityDecorator.setValue(new MutableInteger(Integer.MAX_VALUE),e);`
157 |  | `}`
158 | 4 | `}`
159 |  | `}`

this report was generated by version 1.0.5 of jcoverage. visit www.jcoverage.com for updates. | copyright © 2003, jcoverage ltd. all rights reserved. Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.