third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/ShortestPathUtils.java

   1 /*
   2  * Created on Jul 10, 2005
   3  *
   4  * Copyright (c) 2005, the JUNG Project and the Regents of the University
   5  * of California
   6  * All rights reserved.
   7  *
   8  * This software is open-source under the BSD license; see either
   9  * "license.txt" or
  10  * http://jung.sourceforge.net/license.txt for a description.
  11  */
  12 package edu.uci.ics.jung.algorithms.shortestpath;
  13
  14 import java.util.LinkedList;
  15 import java.util.List;
  16 import java.util.Map;
  17
  18 import edu.uci.ics.jung.graph.Graph;
  19 import edu.uci.ics.jung.graph.util.Pair;
  20
  21 /**
  22  * Utilities relating to the shortest paths in a graph.
  23  */
  24 public class ShortestPathUtils
  25 {
  26     /**
  27      * Returns a <code>List</code> of the edges on the shortest path from
  28      * <code>source</code> to <code>target</code>, in order of their
  29      * occurrence on this path.
  30      */
  31     public static <V, E> List<E> getPath(Graph<V,E> graph, ShortestPath<V,E> sp, V source, V target)
  32     {
  33         LinkedList<E> path = new LinkedList<E>();
  34
  35         Map<V,E> incomingEdges = sp.getIncomingEdgeMap(source);
  36
  37         if (incomingEdges.isEmpty() || incomingEdges.get(target) == null)
  38             return path;
  39         V current = target;
  40         while (!current.equals(source))
  41         {
  42             E incoming = incomingEdges.get(current);
  43             path.addFirst(incoming);
  44             Pair<V> endpoints = graph.getEndpoints(incoming);
  45             if(endpoints.getFirst().equals(current)) {
  46                 current = endpoints.getSecond();
  47             } else {
  48                 current = endpoints.getFirst();
  49             }
  50                         //incoming.getOpposite(current);
  51         }
  52         return path;
  53     }
  54 }