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.
10 package edu.uci.ics.jung.algorithms.shortestpath;
13 import java.util.ArrayList;
14 import java.util.Collections;
15 import java.util.HashMap;
16 import java.util.HashSet;
17 import java.util.List;
21 import edu.uci.ics.jung.graph.Hypergraph;
24 * Labels each node in the graph according to the BFS distance from the start node(s). If nodes are unreachable, then
25 * they are assigned a distance of -1.
26 * All nodes traversed at step k are marked as predecessors of their successors traversed at step k+1.
28 * Running time is: O(m)
31 public class BFSDistanceLabeler<V, E> {
33 private Map<V, Number> distanceDecorator = new HashMap<V,Number>();
34 private List<V> mCurrentList;
35 private Set<V> mUnvisitedVertices;
36 private List<V> mVerticesInOrderVisited;
37 private Map<V,HashSet<V>> mPredecessorMap;
40 * Creates a new BFS labeler for the specified graph and root set
41 * The distances are stored in the corresponding Vertex objects and are of type MutableInteger
43 public BFSDistanceLabeler() {
44 mPredecessorMap = new HashMap<V,HashSet<V>>();
48 * Returns the list of vertices visited in order of traversal
49 * @return the list of vertices
51 public List<V> getVerticesInOrderVisited() {
52 return mVerticesInOrderVisited;
56 * Returns the set of all vertices that were not visited
57 * @return the list of unvisited vertices
59 public Set<V> getUnvisitedVertices() {
60 return mUnvisitedVertices;
64 * Given a vertex, returns the shortest distance from any node in the root set to v
65 * @param v the vertex whose distance is to be retrieved
66 * @return the shortest distance from any node in the root set to v
68 public int getDistance(Hypergraph<V,E> g, V v) {
69 if (!g.getVertices().contains(v)) {
70 throw new IllegalArgumentException("Vertex is not contained in the graph.");
73 return distanceDecorator.get(v).intValue();
77 * Returns set of predecessors of the given vertex
78 * @param v the vertex whose predecessors are to be retrieved
79 * @return the set of predecessors
81 public Set<V> getPredecessors(V v) {
82 return mPredecessorMap.get(v);
85 protected void initialize(Hypergraph<V,E> g, Set<V> rootSet) {
86 mVerticesInOrderVisited = new ArrayList<V>();
87 mUnvisitedVertices = new HashSet<V>();
88 for(V currentVertex : g.getVertices()) {
89 mUnvisitedVertices.add(currentVertex);
90 mPredecessorMap.put(currentVertex,new HashSet<V>());
93 mCurrentList = new ArrayList<V>();
95 distanceDecorator.put(v, new Integer(0));
97 mUnvisitedVertices.remove(v);
98 mVerticesInOrderVisited.add(v);
102 private void addPredecessor(V predecessor,V sucessor) {
103 HashSet<V> predecessors = mPredecessorMap.get(sucessor);
104 predecessors.add(predecessor);
108 * Computes the distances of all the node from the starting root nodes. If there is more than one root node
109 * the minimum distance from each root node is used as the designated distance to a given node. Also keeps track
110 * of the predecessors of each node traversed as well as the order of nodes traversed.
111 * @param graph the graph to label
112 * @param rootSet the set of starting vertices to traverse from
114 public void labelDistances(Hypergraph<V,E> graph, Set<V> rootSet) {
116 initialize(graph,rootSet);
120 List<V> newList = new ArrayList<V>();
121 for(V currentVertex : mCurrentList) {
122 if(graph.containsVertex(currentVertex)) {
123 for(V next : graph.getSuccessors(currentVertex)) {
124 visitNewVertex(currentVertex,next, distance, newList);
128 if (newList.size() == 0) break;
129 mCurrentList = newList;
133 for(V v : mUnvisitedVertices) {
134 distanceDecorator.put(v,new Integer(-1));
139 * Computes the distances of all the node from the specified root node. Also keeps track
140 * of the predecessors of each node traversed as well as the order of nodes traversed.
141 * @param graph the graph to label
142 * @param root the single starting vertex to traverse from
144 public void labelDistances(Hypergraph<V,E> graph, V root) {
145 labelDistances(graph, Collections.singleton(root));
148 private void visitNewVertex(V predecessor, V neighbor, int distance, List<V> newList) {
149 if (mUnvisitedVertices.contains(neighbor)) {
150 distanceDecorator.put(neighbor, new Integer(distance));
151 newList.add(neighbor);
152 mVerticesInOrderVisited.add(neighbor);
153 mUnvisitedVertices.remove(neighbor);
155 int predecessorDistance = distanceDecorator.get(predecessor).intValue();
156 int successorDistance = distanceDecorator.get(neighbor).intValue();
157 if (predecessorDistance < successorDistance) {
158 addPredecessor(predecessor,neighbor);
163 * Returns a map from vertices to minimum distances from the original source(s).
164 * Must be called after {@code labelDistances} in order to contain valid data.
166 public Map<V, Number> getDistanceDecorator() {
167 return distanceDecorator;