third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/UnweightedShortestPath.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 import java.util.HashMap;
  13 import java.util.Map;
  14
  15 import edu.uci.ics.jung.graph.Hypergraph;
  16
  17 /**
  18  * Computes the shortest path distances for graphs whose edges are not weighted (using BFS).
  19  *
  20  * @author Scott White
  21  */
  22 public class UnweightedShortestPath<V, E>
  23     implements ShortestPath<V,E>, Distance<V>
  24 {
  25         private Map<V,Map<V,Number>> mDistanceMap;
  26         private Map<V,Map<V,E>> mIncomingEdgeMap;
  27         private Hypergraph<V,E> mGraph;
  28     private Map<V, Number> distances = new HashMap<V,Number>();
  29
  30         /**
  31          * Constructs and initializes algorithm
  32          * @param g the graph
  33          */
  34         public UnweightedShortestPath(Hypergraph<V,E> g)
  35         {
  36                 mDistanceMap = new HashMap<V,Map<V,Number>>();
  37                 mIncomingEdgeMap = new HashMap<V,Map<V,E>>();
  38                 mGraph = g;
  39         }
  40
  41     /**
  42      * @see edu.uci.ics.jung.algorithms.shortestpath.Distance#getDistance(Object, Object)
  43      */
  44         public Number getDistance(V source, V target)
  45         {
  46                 Map<V, Number> sourceSPMap = getDistanceMap(source);
  47                 return sourceSPMap.get(target);
  48         }
  49
  50     /**
  51      * @see edu.uci.ics.jung.algorithms.shortestpath.Distance#getDistanceMap(Object)
  52      */
  53         public Map<V,Number> getDistanceMap(V source)
  54         {
  55                 Map<V,Number> sourceSPMap = mDistanceMap.get(source);
  56                 if (sourceSPMap == null)
  57                 {
  58                         computeShortestPathsFromSource(source);
  59                         sourceSPMap = mDistanceMap.get(source);
  60                 }
  61                 return sourceSPMap;
  62         }
  63
  64         /**
  65          * @see edu.uci.ics.jung.algorithms.shortestpath.ShortestPath#getIncomingEdgeMap(Object)
  66          */
  67         public Map<V,E> getIncomingEdgeMap(V source)
  68         {
  69                 Map<V,E> sourceIEMap = mIncomingEdgeMap.get(source);
  70                 if (sourceIEMap == null)
  71                 {
  72                         computeShortestPathsFromSource(source);
  73                         sourceIEMap = mIncomingEdgeMap.get(source);
  74                 }
  75                 return sourceIEMap;
  76         }
  77
  78
  79         /**
  80          * Computes the shortest path distances from a given node to all other nodes.
  81          * @param source the source node
  82          */
  83         private void computeShortestPathsFromSource(V source)
  84         {
  85                 BFSDistanceLabeler<V,E> labeler = new BFSDistanceLabeler<V,E>();
  86                 labeler.labelDistances(mGraph, source);
  87         distances = labeler.getDistanceDecorator();
  88                 Map<V,Number> currentSourceSPMap = new HashMap<V,Number>();
  89                 Map<V,E> currentSourceEdgeMap = new HashMap<V,E>();
  90
  91         for(V vertex : mGraph.getVertices()) {
  92
  93                         Number distanceVal = distances.get(vertex);
  94             // BFSDistanceLabeler uses -1 to indicate unreachable vertices;
  95             // don't bother to store unreachable vertices
  96             if (distanceVal != null && distanceVal.intValue() >= 0)
  97             {
  98                 currentSourceSPMap.put(vertex, distanceVal);
  99                 int minDistance = distanceVal.intValue();
 100                 for(E incomingEdge : mGraph.getInEdges(vertex))
 101                 {
 102                         for (V neighbor : mGraph.getIncidentVertices(incomingEdge))
 103                         {
 104                                 if (neighbor.equals(vertex))
 105                                         continue;
 106 //                          V neighbor = mGraph.getOpposite(vertex, incomingEdge);
 107
 108                             Number predDistanceVal = distances.get(neighbor);
 109
 110                             int pred_distance = predDistanceVal.intValue();
 111                             if (pred_distance < minDistance && pred_distance >= 0)
 112                             {
 113                                 minDistance = predDistanceVal.intValue();
 114                                 currentSourceEdgeMap.put(vertex, incomingEdge);
 115                             }
 116                         }
 117                 }
 118             }
 119                 }
 120                 mDistanceMap.put(source, currentSourceSPMap);
 121                 mIncomingEdgeMap.put(source, currentSourceEdgeMap);
 122         }
 123
 124     /**
 125      * Clears all stored distances for this instance.
 126      * Should be called whenever the graph is modified (edge weights
 127      * changed or edges added/removed).  If the user knows that
 128      * some currently calculated distances are unaffected by a
 129      * change, <code>reset(V)</code> may be appropriate instead.
 130      *
 131      * @see #reset(Object)
 132      */
 133     public void reset()
 134     {
 135         mDistanceMap.clear();
 136         mIncomingEdgeMap.clear();
 137     }
 138
 139     /**
 140      * Clears all stored distances for the specified source vertex
 141      * <code>source</code>.  Should be called whenever the stored distances
 142      * from this vertex are invalidated by changes to the graph.
 143      *
 144      * @see #reset()
 145      */
 146     public void reset(V v)
 147     {
 148         mDistanceMap.remove(v);
 149         mIncomingEdgeMap.remove(v);
 150     }
 151 }