third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.java

   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.algorithms.filters;
  15 import java.util.ArrayList;
  16 import java.util.Collection;
  17 import java.util.HashSet;
  18 import java.util.List;
  19 import java.util.Set;
  20
  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;
  24
  25 /**
  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.
  30  *
  31  * @author Danyel Fisher
  32  */
  33 public class KNeighborhoodFilter<V,E> implements Filter<V,E> {
  34
  35         /**
  36          * The type of edge to follow for defining the neighborhood.
  37          */
  38         public static enum EdgeType { IN_OUT, IN, OUT }
  39         private Set<V> rootNodes;
  40         private int radiusK;
  41         private EdgeType edgeType;
  42
  43         /**
  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
  48          */
  49         public KNeighborhoodFilter(Set<V> rootNodes, int radiusK, EdgeType edgeType) {
  50                 this.rootNodes = rootNodes;
  51                 this.radiusK = radiusK;
  52                 this.edgeType = edgeType;
  53         }
  54
  55         /**
  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
  60          */
  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;
  66         }
  67
  68         /**
  69          * Constructs an unassembled graph containing the k-neighborhood around the root node(s).
  70          */
  71         @SuppressWarnings("unchecked")
  72         public Graph<V,E> transform(Graph<V,E> graph) {
  73                 // generate a Set of Vertices we want
  74                 // add all to the UG
  75                 int currentDepth = 0;
  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) {
  82
  83                         visitedVertices.add(currentRoot);
  84                         acceptedVertices.add(currentRoot);
  85                         currentVertices.add(currentRoot);
  86                 }
  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) {
  92
  93                                 Collection<E> edges = null;
  94                                 switch (edgeType) {
  95                                         case IN_OUT :
  96                                                 edges = graph.getIncidentEdges(currentVertex);
  97                                                 break;
  98                                         case IN :
  99                                                 edges = graph.getInEdges(currentVertex);
 100                                                 break;
 101                                         case OUT :
 102                                                 edges = graph.getOutEdges(currentVertex);
 103                                                 break;
 104                                 }
 105                                 for (E currentEdge : edges) {
 106
 107                                         V currentNeighbor =
 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);
 115                                                 }
 116                                         }
 117                                 }
 118                         }
 119                         currentVertices = newVertices;
 120                         currentDepth++;
 121                 }
 122                 Graph<V,E> ug = null;
 123                 try {
 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());
 129                                 }
 130                         }
 131                 }
 132         catch (InstantiationException e)
 133         {
 134             throw new RuntimeException("Unable to create copy of existing graph: ", e);
 135         }
 136         catch (IllegalAccessException e)
 137         {
 138             throw new RuntimeException("Unable to create copy of existing graph: ", e);
 139         }
 140                 return ug;
 141         }
 142 }