Initial opendaylight infrastructure commit!!

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

diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.java
new file mode 100644 (file)
index 0000000..62bcfc2
--- /dev/null
+++ b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.java
@@ -0,0 +1,142 @@
+/*
+ * Copyright (c) 2003, the JUNG Project and the Regents of the University 
+ * of California
+ * All rights reserved.
+ *
+ * This software is open-source under the BSD license; see either
+ * "license.txt" or
+ * http://jung.sourceforge.net/license.txt for a description.
+ */
+/*
+ * Created on Dec 26, 2001
+ *
+ */
+package edu.uci.ics.jung.algorithms.filters;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import edu.uci.ics.jung.algorithms.filters.Filter;
+import edu.uci.ics.jung.graph.Graph;
+import edu.uci.ics.jung.graph.util.Pair;
+
+/**
+ * A filter used to extract the k-neighborhood around one or more root node(s).
+ * The k-neighborhood is defined as the subgraph induced by the set of 
+ * vertices that are k or fewer hops (unweighted shortest-path distance)
+ * away from the root node.
+ * 
+ * @author Danyel Fisher
+ */
+public class KNeighborhoodFilter<V,E> implements Filter<V,E> {
+
+       /**
+        * The type of edge to follow for defining the neighborhood.
+        */
+       public static enum EdgeType { IN_OUT, IN, OUT }
+       private Set<V> rootNodes;
+       private int radiusK;
+       private EdgeType edgeType;
+       
+       /**
+        * Constructs a new instance of the filter.
+        * @param rootNodes the set of root nodes
+        * @param radiusK the neighborhood radius around the root set
+        * @param edgeType 0 for in/out edges, 1 for in-edges, 2  for out-edges
+        */
+       public KNeighborhoodFilter(Set<V> rootNodes, int radiusK, EdgeType edgeType) {
+               this.rootNodes = rootNodes;
+               this.radiusK = radiusK;
+               this.edgeType = edgeType;
+       }
+       
+       /**
+        * Constructs a new instance of the filter.
+        * @param rootNode the root node
+        * @param radiusK the neighborhood radius around the root set
+        * @param edgeType 0 for in/out edges, 1 for in-edges, 2  for out-edges
+        */
+       public KNeighborhoodFilter(V rootNode, int radiusK, EdgeType edgeType) {
+               this.rootNodes = new HashSet<V>();
+               this.rootNodes.add(rootNode);
+               this.radiusK = radiusK;
+               this.edgeType = edgeType;
+       }
+       
+       /**
+        * Constructs an unassembled graph containing the k-neighborhood around the root node(s).
+        */
+       @SuppressWarnings("unchecked")
+       public Graph<V,E> transform(Graph<V,E> graph) {
+               // generate a Set of Vertices we want
+               // add all to the UG
+               int currentDepth = 0;
+               List<V> currentVertices = new ArrayList<V>();
+               Set<V> visitedVertices = new HashSet<V>();
+               Set<E> visitedEdges = new HashSet<E>();
+               Set<V> acceptedVertices = new HashSet<V>();
+               //Copy, mark, and add all the root nodes to the new subgraph
+               for (V currentRoot : rootNodes) {
+
+                       visitedVertices.add(currentRoot);
+                       acceptedVertices.add(currentRoot);
+                       currentVertices.add(currentRoot);
+               }
+               ArrayList<V> newVertices = null;
+               //Use BFS to locate the neighborhood around the root nodes within distance k
+               while (currentDepth < radiusK) {
+                       newVertices = new ArrayList<V>();
+                       for (V currentVertex : currentVertices) {
+
+                               Collection<E> edges = null;
+                               switch (edgeType) {
+                                       case IN_OUT :
+                                               edges = graph.getIncidentEdges(currentVertex);
+                                               break;
+                                       case IN :
+                                               edges = graph.getInEdges(currentVertex);
+                                               break;
+                                       case OUT :
+                                               edges = graph.getOutEdges(currentVertex);
+                                               break;
+                               }
+                               for (E currentEdge : edges) {
+
+                                       V currentNeighbor =
+                                               graph.getOpposite(currentVertex, currentEdge);
+                                       if (!visitedEdges.contains(currentEdge)) {
+                                               visitedEdges.add(currentEdge);
+                                               if (!visitedVertices.contains(currentNeighbor)) {
+                                                       visitedVertices.add(currentNeighbor);
+                                                       acceptedVertices.add(currentNeighbor);
+                                                       newVertices.add(currentNeighbor);
+                                               }
+                                       }
+                               }
+                       }
+                       currentVertices = newVertices;
+                       currentDepth++;
+               }
+               Graph<V,E> ug = null;
+               try {
+                       ug = graph.getClass().newInstance();
+                       for(E edge : graph.getEdges()) {
+                               Pair<V> endpoints = graph.getEndpoints(edge);
+                               if(acceptedVertices.containsAll(endpoints)) {
+                                       ug.addEdge(edge, endpoints.getFirst(), endpoints.getSecond());
+                               }
+                       }
+               } 
+        catch (InstantiationException e)
+        {
+            throw new RuntimeException("Unable to create copy of existing graph: ", e);
+        }
+        catch (IllegalAccessException e)
+        {
+            throw new RuntimeException("Unable to create copy of existing graph: ", e);
+        }
+               return ug;
+       }
+}