| 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 | /* | |
| 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 | */ | |
| 43 | 1 | public KNeighborhoodFilter(Set rootNodes, int radiusK, int edgeType) { |
| 44 | 1 | this.rootNodes = rootNodes; |
| 45 | 1 | this.radiusK = radiusK; |
| 46 | 1 | this.edgeType = edgeType; |
| 47 | 1 | } |
| 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 | */ | |
| 54 | 0 | public KNeighborhoodFilter(Vertex rootNode, int radiusK, int edgeType) { |
| 55 | 0 | this.rootNodes = new HashSet(); |
| 56 | 0 | this.rootNodes.add(rootNode); |
| 57 | 0 | this.radiusK = radiusK; |
| 58 | 0 | this.edgeType = edgeType; |
| 59 | 0 | } |
| 60 | ||
| 61 | public String getName() { | |
| 62 | 1 | 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 | |
| 71 | 1 | int currentDepth = 0; |
| 72 | 1 | ArrayList currentVertices = new ArrayList(); |
| 73 | 1 | HashSet visitedVertices = new HashSet(); |
| 74 | 1 | HashSet visitedEdges = new HashSet(); |
| 75 | 1 | Set acceptedVertices = new HashSet(); |
| 76 | //Copy, mark, and add all the root nodes to the new subgraph | |
| 77 | 1 | for (Iterator rootIt = rootNodes.iterator(); rootIt.hasNext();) { |
| 78 | 1 | Vertex currentRoot = (Vertex) rootIt.next(); |
| 79 | 1 | visitedVertices.add(currentRoot); |
| 80 | 1 | acceptedVertices.add(currentRoot); |
| 81 | 1 | currentVertices.add(currentRoot); |
| 82 | } | |
| 83 | 1 | ArrayList newVertices = null; |
| 84 | //Use BFS to locate the neighborhood around the root nodes within distance k | |
| 85 | 3 | while (currentDepth < radiusK) { |
| 86 | 2 | newVertices = new ArrayList(); |
| 87 | 2 | for (Iterator vertexIt = currentVertices.iterator(); |
| 88 | 4 | vertexIt.hasNext(); |
| 89 | ) { | |
| 90 | 2 | Vertex currentVertex = (Vertex) vertexIt.next(); |
| 91 | 2 | Set edges = null; |
| 92 | 2 | switch (edgeType) { |
| 93 | case IN_OUT : | |
| 94 | 2 | edges = currentVertex.getIncidentEdges(); |
| 95 | 2 | break; |
| 96 | case IN : | |
| 97 | 0 | edges = currentVertex.getInEdges(); |
| 98 | 0 | break; |
| 99 | case OUT : | |
| 100 | 0 | edges = currentVertex.getOutEdges(); |
| 101 | break; | |
| 102 | } | |
| 103 | 2 | for (Iterator neighboringEdgeIt = edges.iterator(); |
| 104 | 5 | neighboringEdgeIt.hasNext(); |
| 105 | ) { | |
| 106 | 3 | Edge currentEdge = (Edge) neighboringEdgeIt.next(); |
| 107 | 3 | Vertex currentNeighbor = |
| 108 | currentEdge.getOpposite(currentVertex); | |
| 109 | 3 | if (!visitedEdges.contains(currentEdge)) { |
| 110 | 2 | visitedEdges.add(currentEdge); |
| 111 | 2 | if (!visitedVertices.contains(currentNeighbor)) { |
| 112 | 2 | visitedVertices.add(currentNeighbor); |
| 113 | 2 | acceptedVertices.add(currentNeighbor); |
| 114 | 2 | newVertices.add(currentNeighbor); |
| 115 | } | |
| 116 | } | |
| 117 | } | |
| 118 | } | |
| 119 | 2 | currentVertices = newVertices; |
| 120 | 2 | currentDepth++; |
| 121 | } | |
| 122 | 1 | UnassembledGraph ug = |
| 123 | new UnassembledGraph( | |
| 124 | this, | |
| 125 | acceptedVertices, | |
| 126 | graph.getEdges(), | |
| 127 | graph); | |
| 128 | 1 | return ug; |
| 129 | } | |
| 130 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |