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

   1 /**
   2  *
   3  */
   4 package net.kezvh.algorithms.graph;
   5
   6 import java.util.Collection;
   7 import java.util.HashMap;
   8 import java.util.LinkedList;
   9 import java.util.Map;
  10
  11 import net.kezvh.collections.IntegerRange;
  12 import net.kezvh.collections.graphs.directed.DirectedGraphWithEdgeValues;
  13 import net.kezvh.collections.views.ListSlice;
  14
  15 /**
  16  * @author afflux
  17  * @param <T> Node type
  18  */
  19 public class FloydWarshall<T> implements AllPairsShortestPath<T> {
  20         private final DirectedGraphWithEdgeValues<T, Integer> graph;
  21
  22         private static final class NodeList<T> extends LinkedList<T> implements Path<T> {
  23                 private int length;
  24
  25                 public NodeList() {
  26                         this.length = 0;
  27                 }
  28
  29                 public NodeList(final T a, final T b, final int initialLength) {
  30                         this.add(a, 0);
  31                         this.add(b, initialLength);
  32                 }
  33
  34                 @Deprecated
  35                 @Override
  36                 public boolean add(final T e) {
  37                         throw new UnsupportedOperationException();
  38                 }
  39
  40                 @Deprecated
  41                 @Override
  42                 public boolean addAll(final Collection<? extends T> c) {
  43                         throw new UnsupportedOperationException();
  44                 }
  45
  46                 @Deprecated
  47                 @Override
  48                 public T set(final int index, final T element) {
  49                         throw new UnsupportedOperationException();
  50                 }
  51
  52                 @Deprecated
  53                 @Override
  54                 public boolean addAll(final int index, final Collection<? extends T> c) {
  55                         throw new UnsupportedOperationException();
  56                 }
  57
  58                 @Deprecated
  59                 @Override
  60                 public void add(final int index, final T element) {
  61                         throw new UnsupportedOperationException();
  62                 }
  63
  64                 public void add(final T node, final int addedLength) {
  65                         super.add(node);
  66                         this.length += addedLength;
  67                 }
  68
  69                 public void addAll(final NodeList<T> b, final NodeList<T> c) {
  70                         super.addAll(b);
  71                         super.addAll(new ListSlice<T>(c, new IntegerRange(1, c.size())));
  72                         this.length += b.getLength() + c.getLength();
  73                 }
  74
  75                 public int getLength() {
  76                         return this.length;
  77                 }
  78         }
  79
  80         private final Map<T, Map<T, NodeList<T>>> shortestPaths;
  81
  82         /**
  83          * @param graph a directed graph
  84          */
  85         public FloydWarshall(final DirectedGraphWithEdgeValues<T, Integer> graph) {
  86                 this.graph = graph;
  87                 this.shortestPaths = new HashMap<T, Map<T, NodeList<T>>>(graph.size());
  88                 for (final T t : graph) {
  89                         this.shortestPaths.put(t, new HashMap<T, NodeList<T>>());
  90                         for (final T s : graph)
  91                                 if (this.graph.containsEdge(t, s)) {
  92                                         final NodeList<T> array = new NodeList<T>(t, s, this.graph.getEdgeValue(t, s));
  93                                         this.set(t, s, array);
  94                                 } else {
  95                                         final NodeList<T> empty = new NodeList<T>();
  96                                         this.set(t, s, empty);
  97                                 }
  98                 }
  99
 100                 for (final T k : graph)
 101                         for (final T j : graph)
 102                                 for (final T i : graph)
 103                                         this.set(i, j, this.min(this.get(i, j), this.get(i, k), this.get(k, j)));
 104         }
 105
 106         private NodeList<T> get(final T a, final T b) {
 107                 return this.shortestPaths.get(a).get(b);
 108         }
 109
 110         private void set(final T a, final T b, final NodeList<T> value) {
 111                 this.shortestPaths.get(a).put(b, value);
 112         }
 113
 114         private final NodeList<T> min(final NodeList<T> a, final NodeList<T> b, final NodeList<T> c) {
 115                 if (b.getLength() != 0 && c.getLength() != 0)
 116                         if (a.getLength() == 0) {
 117                                 a.addAll(b, c);
 118                                 return a;
 119                         } else if (b.getLength() + c.getLength() - 1 < a.getLength()) {
 120                                 a.clear();
 121                                 a.addAll(b, c);
 122                                 return a;
 123                         } else
 124                                 return a;
 125                 return a;
 126         }
 127
 128         /**
 129          * @see net.kezvh.algorithms.graph.AllPairsShortestPath#getShortestPath(java.lang.Object,
 130          *      java.lang.Object)
 131          * @param source source node
 132          * @param dest destniation node
 133          * @return shortest path
 134          */
 135         public Path<T> getShortestPath(final T source, final T dest) {
 136                 return this.shortestPaths.get(source).get(dest);
 137         }
 138 }