KezvhLib/src-lib/net/kezvh/algorithms/graph/Dijkstra.java

   1 package net.kezvh.algorithms.graph;
   2
   3 import java.lang.reflect.Array;
   4 import java.util.AbstractList;
   5 import java.util.Comparator;
   6 import java.util.HashMap;
   7 import java.util.LinkedList;
   8 import java.util.List;
   9 import java.util.Map;
  10
  11 import net.kezvh.collections.graphs.directed.DirectedGraphWithEdgeValues;
  12 import net.kezvh.collections.heaps.Heap;
  13 import net.kezvh.lang.AlgorithmException;
  14 import net.kezvh.patterns.AbstractFactory;
  15 import net.kezvh.patterns.AbstractFactory.CreationFailedException;
  16
  17 /**
  18  * @author mjacob
  19  * @param <T> node type
  20  */
  21 public class Dijkstra<T> implements SingleSourceShortestPath<T> {
  22         final T source;
  23         private final Map<T, Integer> dist = new HashMap<T, Integer>();
  24         private final Map<T, T> previous = new HashMap<T, T>();
  25
  26         private final Map<T, ShortestPath> shortestPaths = new HashMap<T, ShortestPath>();
  27
  28         private static final int INFINITY = -1;
  29
  30         /**
  31          * 1 function Dijkstra(Graph, source): 2 for each vertex v in Graph: //
  32          * Initializations 3 dist[v] := infinity // Unknown distance function from
  33          * source to v 4 previous[v] := undefined // Previous node in optimal path
  34          * from source 5 dist[source] := 0 // Distance from source to source 6 Q :=
  35          * the set of all nodes in Graph // All nodes in the graph are unoptimized -
  36          * thus are in Q 7 while Q is not empty: // The main loop 8 u := node in Q
  37          * with smallest dist[] 9 remove u from Q 10 for each neighbor v of u: //
  38          * where v has not yet been removed from Q. 11 alt := dist[u] +
  39          * dist_between(u, v) 12 if alt < dist[v] // Relax (u,v) 13 dist[v] := alt
  40          * 14 previous[v] := u 15 return previous[]
  41          */
  42
  43         private final class ShortestPath extends AbstractList<T> implements Path<T> {
  44                 private final T dest;
  45                 private final T[] nodes;
  46
  47                 @SuppressWarnings("unchecked")
  48                 public ShortestPath(final T dest) {
  49                         super();
  50                         this.dest = dest;
  51
  52                         final List<T> previa = new LinkedList<T>();
  53                         T p = dest;
  54                         while (p != null) {
  55                                 previa.add(0, p);
  56                                 p = Dijkstra.this.previous.get(p);
  57                         }
  58
  59                         this.nodes = previa.toArray((T[]) Array.newInstance(dest.getClass(), previa.size()));
  60
  61                         if (this.nodes[0] != Dijkstra.this.source)
  62                                 throw new AlgorithmException();
  63                         if (dest != Dijkstra.this.source && this.nodes.length == 1)
  64                                 throw new AlgorithmException();
  65                 }
  66
  67                 @Override
  68                 public T get(final int index) {
  69                         return this.nodes[index];
  70                 }
  71
  72                 @Override
  73                 public int size() {
  74                         return this.nodes.length;
  75                 }
  76
  77                 @Override
  78                 public int getLength() {
  79                         return Dijkstra.this.dist.get(this.dest);
  80                 }
  81         }
  82
  83         /**
  84          * @param graph COMMENT
  85          * @param source COMMENT
  86          * @param heapMaker needs to create a heap w/ a priority which ranks -1 as
  87          *            INFINITY
  88          */
  89         public Dijkstra(final DirectedGraphWithEdgeValues<T, Integer> graph, final T source, final AbstractFactory<Heap<T, Integer>> heapMaker) {
  90                 super();
  91                 this.source = source;
  92
  93                 this.dist.put(source, 0);
  94                 final Heap<T, Integer> Q;
  95                 try {
  96                         Q = heapMaker.create();
  97                 } catch (final CreationFailedException e) {
  98                         throw new RuntimeException();
  99                 }
 100
 101                 final Comparator<? super Integer> comparator = Q.comparator();
 102
 103                 for (final T v : graph) { // to break the algorithm, move this { one line down
 104                         if (!source.equals(v))
 105                                 this.dist.put(v, Dijkstra.INFINITY);
 106                         Q.add(v, Dijkstra.INFINITY);
 107                 }
 108
 109                 while (!Q.isEmpty()) {
 110                         final T u = Q.remove();
 111                         for (final T v : graph.adjacentFrom(u)) {
 112                                 final int alt = ((int) this.dist.get(u)) == Dijkstra.INFINITY ? Dijkstra.INFINITY : this.dist.get(u) + graph.getEdgeValue(u, v);
 113                                 if (comparator.compare(alt, this.dist.get(v)) < 0) {
 114                                         if (Q.contains(v))
 115                                                 Q.reweight(v, alt);
 116                                         this.dist.put(v, alt);
 117                                         this.previous.put(v, u);
 118                                 }
 119                         }
 120                 }
 121         }
 122
 123         @Override
 124         public Path<T> getShortestPath(final T dest) {
 125                 if (!this.dist.containsKey(dest))
 126                         throw new IllegalArgumentException("Node " + dest + " is not in the graph");
 127                 if (this.dist.get(dest) == Dijkstra.INFINITY)
 128                         return null;
 129
 130                 if (this.shortestPaths.containsKey(dest))
 131                         return this.shortestPaths.get(dest);
 132
 133                 final ShortestPath shortestPath = new ShortestPath(dest);
 134                 this.shortestPaths.put(dest, shortestPath);
 135                 return shortestPath;
 136         }
 137
 138         public boolean connected(final T dest) {
 139                 if (!this.dist.containsKey(dest))
 140                         throw new IllegalArgumentException("Node " + dest + " is not in the graph");
 141                 return this.dist.get(dest) != Dijkstra.INFINITY;
 142         }
 143
 144         /**
 145          * @see net.kezvh.algorithms.graph.SingleSourceShortestPath#getSource()
 146          * @return the source of the sssp
 147          */
 148         @Override
 149         public T getSource() {
 150                 return this.source;
 151         }
 152 }