--- /dev/null
+/*
+* 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.
+*/
+package edu.uci.ics.jung.algorithms.shortestpath;
+
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import edu.uci.ics.jung.graph.Hypergraph;
+
+/**
+ * Labels each node in the graph according to the BFS distance from the start node(s). If nodes are unreachable, then
+ * they are assigned a distance of -1.
+ * All nodes traversed at step k are marked as predecessors of their successors traversed at step k+1.
+ * <p>
+ * Running time is: O(m)
+ * @author Scott White
+ */
+public class BFSDistanceLabeler<V, E> {
+
+ private Map<V, Number> distanceDecorator = new HashMap<V,Number>();
+ private List<V> mCurrentList;
+ private Set<V> mUnvisitedVertices;
+ private List<V> mVerticesInOrderVisited;
+ private Map<V,HashSet<V>> mPredecessorMap;
+
+ /**
+ * Creates a new BFS labeler for the specified graph and root set
+ * The distances are stored in the corresponding Vertex objects and are of type MutableInteger
+ */
+ public BFSDistanceLabeler() {
+ mPredecessorMap = new HashMap<V,HashSet<V>>();
+ }
+
+ /**
+ * Returns the list of vertices visited in order of traversal
+ * @return the list of vertices
+ */
+ public List<V> getVerticesInOrderVisited() {
+ return mVerticesInOrderVisited;
+ }
+
+ /**
+ * Returns the set of all vertices that were not visited
+ * @return the list of unvisited vertices
+ */
+ public Set<V> getUnvisitedVertices() {
+ return mUnvisitedVertices;
+ }
+
+ /**
+ * Given a vertex, returns the shortest distance from any node in the root set to v
+ * @param v the vertex whose distance is to be retrieved
+ * @return the shortest distance from any node in the root set to v
+ */
+ public int getDistance(Hypergraph<V,E> g, V v) {
+ if (!g.getVertices().contains(v)) {
+ throw new IllegalArgumentException("Vertex is not contained in the graph.");
+ }
+
+ return distanceDecorator.get(v).intValue();
+ }
+
+ /**
+ * Returns set of predecessors of the given vertex
+ * @param v the vertex whose predecessors are to be retrieved
+ * @return the set of predecessors
+ */
+ public Set<V> getPredecessors(V v) {
+ return mPredecessorMap.get(v);
+ }
+
+ protected void initialize(Hypergraph<V,E> g, Set<V> rootSet) {
+ mVerticesInOrderVisited = new ArrayList<V>();
+ mUnvisitedVertices = new HashSet<V>();
+ for(V currentVertex : g.getVertices()) {
+ mUnvisitedVertices.add(currentVertex);
+ mPredecessorMap.put(currentVertex,new HashSet<V>());
+ }
+
+ mCurrentList = new ArrayList<V>();
+ for(V v : rootSet) {
+ distanceDecorator.put(v, new Integer(0));
+ mCurrentList.add(v);
+ mUnvisitedVertices.remove(v);
+ mVerticesInOrderVisited.add(v);
+ }
+ }
+
+ private void addPredecessor(V predecessor,V sucessor) {
+ HashSet<V> predecessors = mPredecessorMap.get(sucessor);
+ predecessors.add(predecessor);
+ }
+
+ /**
+ * Computes the distances of all the node from the starting root nodes. If there is more than one root node
+ * the minimum distance from each root node is used as the designated distance to a given node. Also keeps track
+ * of the predecessors of each node traversed as well as the order of nodes traversed.
+ * @param graph the graph to label
+ * @param rootSet the set of starting vertices to traverse from
+ */
+ public void labelDistances(Hypergraph<V,E> graph, Set<V> rootSet) {
+
+ initialize(graph,rootSet);
+
+ int distance = 1;
+ while (true) {
+ List<V> newList = new ArrayList<V>();
+ for(V currentVertex : mCurrentList) {
+ if(graph.containsVertex(currentVertex)) {
+ for(V next : graph.getSuccessors(currentVertex)) {
+ visitNewVertex(currentVertex,next, distance, newList);
+ }
+ }
+ }
+ if (newList.size() == 0) break;
+ mCurrentList = newList;
+ distance++;
+ }
+
+ for(V v : mUnvisitedVertices) {
+ distanceDecorator.put(v,new Integer(-1));
+ }
+ }
+
+ /**
+ * Computes the distances of all the node from the specified root node. Also keeps track
+ * of the predecessors of each node traversed as well as the order of nodes traversed.
+ * @param graph the graph to label
+ * @param root the single starting vertex to traverse from
+ */
+ public void labelDistances(Hypergraph<V,E> graph, V root) {
+ labelDistances(graph, Collections.singleton(root));
+ }
+
+ private void visitNewVertex(V predecessor, V neighbor, int distance, List<V> newList) {
+ if (mUnvisitedVertices.contains(neighbor)) {
+ distanceDecorator.put(neighbor, new Integer(distance));
+ newList.add(neighbor);
+ mVerticesInOrderVisited.add(neighbor);
+ mUnvisitedVertices.remove(neighbor);
+ }
+ int predecessorDistance = distanceDecorator.get(predecessor).intValue();
+ int successorDistance = distanceDecorator.get(neighbor).intValue();
+ if (predecessorDistance < successorDistance) {
+ addPredecessor(predecessor,neighbor);
+ }
+ }
+
+ /**
+ * Returns a map from vertices to minimum distances from the original source(s).
+ * Must be called after {@code labelDistances} in order to contain valid data.
+ */
+ public Map<V, Number> getDistanceDecorator() {
+ return distanceDecorator;
+ }
+}
Code Review / controller.git / blobdiff