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. |