2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
11 * Created on Dec 26, 2001
14 package edu.uci.ics.jung.algorithms.filters;
15 import java.util.ArrayList;
16 import java.util.Collection;
17 import java.util.HashSet;
18 import java.util.List;
21 import edu.uci.ics.jung.algorithms.filters.Filter;
22 import edu.uci.ics.jung.graph.Graph;
23 import edu.uci.ics.jung.graph.util.Pair;
26 * A filter used to extract the k-neighborhood around one or more root node(s).
27 * The k-neighborhood is defined as the subgraph induced by the set of
28 * vertices that are k or fewer hops (unweighted shortest-path distance)
29 * away from the root node.
31 * @author Danyel Fisher
33 public class KNeighborhoodFilter<V,E> implements Filter<V,E> {
36 * The type of edge to follow for defining the neighborhood.
38 public static enum EdgeType { IN_OUT, IN, OUT }
39 private Set<V> rootNodes;
41 private EdgeType edgeType;
44 * Constructs a new instance of the filter.
45 * @param rootNodes the set of root nodes
46 * @param radiusK the neighborhood radius around the root set
47 * @param edgeType 0 for in/out edges, 1 for in-edges, 2 for out-edges
49 public KNeighborhoodFilter(Set<V> rootNodes, int radiusK, EdgeType edgeType) {
50 this.rootNodes = rootNodes;
51 this.radiusK = radiusK;
52 this.edgeType = edgeType;
56 * Constructs a new instance of the filter.
57 * @param rootNode the root node
58 * @param radiusK the neighborhood radius around the root set
59 * @param edgeType 0 for in/out edges, 1 for in-edges, 2 for out-edges
61 public KNeighborhoodFilter(V rootNode, int radiusK, EdgeType edgeType) {
62 this.rootNodes = new HashSet<V>();
63 this.rootNodes.add(rootNode);
64 this.radiusK = radiusK;
65 this.edgeType = edgeType;
69 * Constructs an unassembled graph containing the k-neighborhood around the root node(s).
71 @SuppressWarnings("unchecked")
72 public Graph<V,E> transform(Graph<V,E> graph) {
73 // generate a Set of Vertices we want
76 List<V> currentVertices = new ArrayList<V>();
77 Set<V> visitedVertices = new HashSet<V>();
78 Set<E> visitedEdges = new HashSet<E>();
79 Set<V> acceptedVertices = new HashSet<V>();
80 //Copy, mark, and add all the root nodes to the new subgraph
81 for (V currentRoot : rootNodes) {
83 visitedVertices.add(currentRoot);
84 acceptedVertices.add(currentRoot);
85 currentVertices.add(currentRoot);
87 ArrayList<V> newVertices = null;
88 //Use BFS to locate the neighborhood around the root nodes within distance k
89 while (currentDepth < radiusK) {
90 newVertices = new ArrayList<V>();
91 for (V currentVertex : currentVertices) {
93 Collection<E> edges = null;
96 edges = graph.getIncidentEdges(currentVertex);
99 edges = graph.getInEdges(currentVertex);
102 edges = graph.getOutEdges(currentVertex);
105 for (E currentEdge : edges) {
108 graph.getOpposite(currentVertex, currentEdge);
109 if (!visitedEdges.contains(currentEdge)) {
110 visitedEdges.add(currentEdge);
111 if (!visitedVertices.contains(currentNeighbor)) {
112 visitedVertices.add(currentNeighbor);
113 acceptedVertices.add(currentNeighbor);
114 newVertices.add(currentNeighbor);
119 currentVertices = newVertices;
122 Graph<V,E> ug = null;
124 ug = graph.getClass().newInstance();
125 for(E edge : graph.getEdges()) {
126 Pair<V> endpoints = graph.getEndpoints(edge);
127 if(acceptedVertices.containsAll(endpoints)) {
128 ug.addEdge(edge, endpoints.getFirst(), endpoints.getSecond());
132 catch (InstantiationException e)
134 throw new RuntimeException("Unable to create copy of existing graph: ", e);
136 catch (IllegalAccessException e)
138 throw new RuntimeException("Unable to create copy of existing graph: ", e);