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

LineHitsSource
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      */
422    public ExactFlowCommunity(int cohesionThreshold) {
432        mCohesionThreshold = cohesionThreshold;
442    }
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) {
534        DirectedGraph flowGraph = (DirectedGraph) graph.copy();
544        Vertex source = flowGraph.addVertex(new SparseVertex());
554        Vertex sink = flowGraph.addVertex(new SparseVertex());
56  
574        initializeFlowGraph(flowGraph,source, sink,rootSet);
584        EdmondsKarpMaxFlow maxFlowSolver = new EdmondsKarpMaxFlow(flowGraph,source,sink,"CAPACITY","FLOW");
594        maxFlowSolver.evaluate();
604        Set communityVertices = new HashSet();
614        Set sourceNodes = maxFlowSolver.getNodesInSourcePartition();
624        for (Iterator vIt = sourceNodes.iterator();vIt.hasNext();) {
6322            Vertex v = (Vertex) vIt.next();
6422            if (v.getEqualVertex(flowGraph) != source) {
6518                communityVertices.add(v.getEqualVertex(graph));
66             }
67         }
68  
694        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) {
810        Set members = new HashSet(rootSet);
820        Set newMembers = null;
830        int numPreviousMembers = members.size();
840        int numCurrentMembers = 0;
85  
860        for (int i=0;i<numIterations;i++) {
870            ExactFlowCommunity ecf = new ExactFlowCommunity(members.size());
880            newMembers = ecf.extract(graph,members);
890            numCurrentMembers = newMembers.size();
900            if (numPreviousMembers == numCurrentMembers) {
910                break;
92             }
930            numPreviousMembers = numCurrentMembers;
940            System.out.println(members.size());
950            DoubleArrayList inDegrees = DegreeDistributions.getIndegreeValues(newMembers);
960            int maxIndegree = (int) Descriptive.max(inDegrees);
970            DoubleArrayList outDegrees = DegreeDistributions.getOutdegreeValues(newMembers);
980            int maxOutdegree = (int) Descriptive.max(outDegrees);
99  
1000            for (Iterator vIt = newMembers.iterator(); vIt.hasNext();) {
1010                Vertex v = (Vertex) vIt.next();
1020                if (members.contains(v)) {
1030                    continue;
104                 }
1050                if (v.inDegree() == maxIndegree) {
1060                    members.add(v);
1070                } else if (v.outDegree() == maxOutdegree) {
1080                    members.add(v);
109                 }
110             }
111         }
112  
1130        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  
1264        NumericDecorator capacityDecorator = new NumericDecorator("CAPACITY",UserData.SHARED);
127  
1284        List edgesList = new ArrayList();
1294        edgesList.addAll(flowGraph.getEdges());
130  
13176        for (int idx = 0; idx < edgesList.size(); idx++) {
13272            DirectedEdge currentEdge = (DirectedEdge) edgesList.get(idx);
13372            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.
13772            Edge otherEdge = currentEdge.getDest().findEdge(currentEdge.getSource());
13872            if (otherEdge == null) {
13924                otherEdge = GraphUtils.addEdge(flowGraph,currentEdge.getDest(),currentEdge.getSource());
14024                capacityDecorator.setValue(new MutableInteger(mCohesionThreshold),otherEdge);
141             }
142         }
143  
1444        for (Iterator vIt = flowGraph.getVertices().iterator(); vIt.hasNext();) {
14548            Vertex currentVertex = (Vertex) vIt.next();
14648            if (currentVertex != sink && !rootSet.contains(currentVertex)) {
14736                Edge newEdge = GraphUtils.addEdge(flowGraph,currentVertex,sink);
14836                capacityDecorator.setValue(new MutableInteger(1),newEdge);
149             }
150         }
151  
1524        for (Iterator rootIt = rootSet.iterator(); rootIt.hasNext();) {
1538            Vertex currentRoot = (Vertex) rootIt.next();
1548            currentRoot = (Vertex) currentRoot.getEqualVertex(flowGraph);
1558            Edge e= GraphUtils.addEdge(flowGraph,source,currentRoot);
1568            capacityDecorator.setValue(new MutableInteger(Integer.MAX_VALUE),e);
157         }
1584    }
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.