third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/BFSDistanceLabeler.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 package edu.uci.ics.jung.algorithms.shortestpath;
  11
  12
  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;
  18 import java.util.Map;
  19 import java.util.Set;
  20
  21 import edu.uci.ics.jung.graph.Hypergraph;
  22
  23 /**
  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.
  27  * <p>
  28  * Running time is: O(m)
  29  * @author Scott White
  30  */
  31 public class BFSDistanceLabeler<V, E> {
  32
  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;
  38
  39         /**
  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
  42          */
  43         public BFSDistanceLabeler() {
  44                 mPredecessorMap = new HashMap<V,HashSet<V>>();
  45         }
  46
  47     /**
  48      * Returns the list of vertices visited in order of traversal
  49      * @return the list of vertices
  50      */
  51     public List<V> getVerticesInOrderVisited() {
  52         return mVerticesInOrderVisited;
  53     }
  54
  55     /**
  56      * Returns the set of all vertices that were not visited
  57      * @return the list of unvisited vertices
  58      */
  59     public Set<V> getUnvisitedVertices() {
  60         return mUnvisitedVertices;
  61     }
  62
  63     /**
  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
  67      */
  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.");
  71         }
  72
  73         return distanceDecorator.get(v).intValue();
  74     }
  75
  76     /**
  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
  80      */
  81     public Set<V> getPredecessors(V v) {
  82         return mPredecessorMap.get(v);
  83     }
  84
  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>());
  91         }
  92
  93         mCurrentList = new ArrayList<V>();
  94         for(V v : rootSet) {
  95             distanceDecorator.put(v, new Integer(0));
  96             mCurrentList.add(v);
  97             mUnvisitedVertices.remove(v);
  98             mVerticesInOrderVisited.add(v);
  99         }
 100     }
 101
 102     private void addPredecessor(V predecessor,V sucessor) {
 103         HashSet<V> predecessors = mPredecessorMap.get(sucessor);
 104         predecessors.add(predecessor);
 105     }
 106
 107     /**
 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
 113      */
 114     public void labelDistances(Hypergraph<V,E> graph, Set<V> rootSet) {
 115
 116         initialize(graph,rootSet);
 117
 118         int distance = 1;
 119         while (true) {
 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);
 125                         }
 126                 }
 127             }
 128             if (newList.size() == 0) break;
 129             mCurrentList = newList;
 130             distance++;
 131         }
 132
 133         for(V v : mUnvisitedVertices) {
 134             distanceDecorator.put(v,new Integer(-1));
 135         }
 136     }
 137
 138     /**
 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
 143      */
 144     public void labelDistances(Hypergraph<V,E> graph, V root) {
 145         labelDistances(graph, Collections.singleton(root));
 146     }
 147
 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);
 154         }
 155         int predecessorDistance = distanceDecorator.get(predecessor).intValue();
 156         int successorDistance = distanceDecorator.get(neighbor).intValue();
 157         if (predecessorDistance < successorDistance) {
 158             addPredecessor(predecessor,neighbor);
 159         }
 160     }
 161
 162     /**
 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.
 165      */
 166     public Map<V, Number> getDistanceDecorator() {
 167         return distanceDecorator;
 168     }
 169 }