Coverage details for edu.uci.ics.jung.graph.filters.impl.KNeighborhoodFilter

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 /*
11  * Created on Dec 26, 2001
12  *
13  */
14 package edu.uci.ics.jung.graph.filters.impl;
15 import java.util.ArrayList;
16 import java.util.HashSet;
17 import java.util.Iterator;
18 import java.util.Set;
19 import edu.uci.ics.jung.graph.Edge;
20 import edu.uci.ics.jung.graph.Graph;
21 import edu.uci.ics.jung.graph.Vertex;
22 import edu.uci.ics.jung.graph.filters.Filter;
23 import edu.uci.ics.jung.graph.filters.UnassembledGraph;
24 /**
25  * A filter used to extract the k-neighborhood around one or more root node(s)
26  * @author Danyel Fisher
27  *
28  */
29 public class KNeighborhoodFilter implements Filter {
30     public static final int IN_OUT = 0;
31     public static final int IN = 1;
32     public static final int OUT = 2;
33     private Set rootNodes;
34     private int radiusK;
35     private int edgeType;
36     
37     /**
38      * Constructs a new instance of the filter
39      * @param rootNodes the set of root nodes
40      * @param radiusK the neighborhood radius around the root set
41      * @param edgeType 0 for in/out edges, 1 for in-edges, 2 for out-edges
42      */
431    public KNeighborhoodFilter(Set rootNodes, int radiusK, int edgeType) {
441        this.rootNodes = rootNodes;
451        this.radiusK = radiusK;
461        this.edgeType = edgeType;
471    }
48     /**
49      * Constructs a new instance of the filter
50      * @param rootNode the root node
51      * @param radiusK the neighborhood radius around the root set
52      * @param edgeType 0 for in/out edges, 1 for in-edges, 2 for out-edges
53      */
540    public KNeighborhoodFilter(Vertex rootNode, int radiusK, int edgeType) {
550        this.rootNodes = new HashSet();
560        this.rootNodes.add(rootNode);
570        this.radiusK = radiusK;
580        this.edgeType = edgeType;
590    }
60     
61     public String getName() {
621        return "KNeighborhood(" + radiusK + "," + edgeType + ")";
63     }
64     
65     /**
66      * Constructs an unassembled graph containing the k-neighbhood around the root node(s)
67      */
68     public UnassembledGraph filter(Graph graph) {
69         // generate a Set of Vertices we want
70         // add all to the UG
711        int currentDepth = 0;
721        ArrayList currentVertices = new ArrayList();
731        HashSet visitedVertices = new HashSet();
741        HashSet visitedEdges = new HashSet();
751        Set acceptedVertices = new HashSet();
76         //Copy, mark, and add all the root nodes to the new subgraph
771        for (Iterator rootIt = rootNodes.iterator(); rootIt.hasNext();) {
781            Vertex currentRoot = (Vertex) rootIt.next();
791            visitedVertices.add(currentRoot);
801            acceptedVertices.add(currentRoot);
811            currentVertices.add(currentRoot);
82         }
831        ArrayList newVertices = null;
84         //Use BFS to locate the neighborhood around the root nodes within distance k
853        while (currentDepth < radiusK) {
862            newVertices = new ArrayList();
872            for (Iterator vertexIt = currentVertices.iterator();
884                vertexIt.hasNext();
89                 ) {
902                Vertex currentVertex = (Vertex) vertexIt.next();
912                Set edges = null;
922                switch (edgeType) {
93                     case IN_OUT :
942                        edges = currentVertex.getIncidentEdges();
952                        break;
96                     case IN :
970                        edges = currentVertex.getInEdges();
980                        break;
99                     case OUT :
1000                        edges = currentVertex.getOutEdges();
101                         break;
102                 }
1032                for (Iterator neighboringEdgeIt = edges.iterator();
1045                    neighboringEdgeIt.hasNext();
105                     ) {
1063                    Edge currentEdge = (Edge) neighboringEdgeIt.next();
1073                    Vertex currentNeighbor =
108                         currentEdge.getOpposite(currentVertex);
1093                    if (!visitedEdges.contains(currentEdge)) {
1102                        visitedEdges.add(currentEdge);
1112                        if (!visitedVertices.contains(currentNeighbor)) {
1122                            visitedVertices.add(currentNeighbor);
1132                            acceptedVertices.add(currentNeighbor);
1142                            newVertices.add(currentNeighbor);
115                         }
116                     }
117                 }
118             }
1192            currentVertices = newVertices;
1202            currentDepth++;
121         }
1221        UnassembledGraph ug =
123             new UnassembledGraph(
124                 this,
125                 acceptedVertices,
126                 graph.getEdges(),
127                 graph);
1281        return ug;
129     }
130 }

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.