Overview  Package   Class  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

y.algo
Class ShortestPaths

java.lang.Object
  |
  +--y.algo.ShortestPaths
public class ShortestPaths
extends Object

Provides diverse algorithms and helper methods for solving the shortest path problem on weighted graphs.

Method Summary
static boolean acyclic(Graph graph, Node s, DataProvider cost, NodeMap dist, NodeMap pred)
          Like ShortestPaths.acyclic(Graph, Node, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.
static boolean acyclic(Graph graph, Node s, double[] cost, double[] dist)
          This method solves the single-source shortest path problem for acyclic directed graphs.
static boolean acyclic(Graph graph, Node s, double[] cost, double[] dist, Edge[] pred)
          Like ShortestPaths.acyclic(Graph, Node, double[], double[]) but additionally this method yields the path edges of each calculated shortest path.
static boolean allPairs(Graph graph, boolean directed, double[] cost, double[][] dist)
          This method solves the all-pairs shortest path problem for graphs with arbitrary edge costs.
static boolean bellmanFord(Graph graph, Node s, boolean directed, DataProvider cost, NodeMap dist, NodeMap pred)
          Like ShortestPaths.bellmanFord(Graph, Node, boolean, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.
static boolean bellmanFord(Graph graph, Node s, boolean directed, double[] cost, double[] dist)
          This method solves the single-source shortest path problem for arbitrary graphs.
static boolean bellmanFord(Graph graph, Node s, boolean directed, double[] cost, double[] dist, Edge[] pred)
          Like ShortestPaths.bellmanFord(Graph, Node, boolean, double[], double[]) but additionally this method yields the path edges of each calculated shortest path.
static EdgeList constructEdgePath(Node s, Node t, DataProvider pred)
          Like ShortestPaths.constructEdgePath(Node,Node,Edge[]) with the difference that the path edges are given by a DataProvider.
static EdgeList constructEdgePath(Node s, Node t, Edge[] pred)
          Conveniance method that constructs an explicit edge path from the result yielded by one of the shortest paths methods defined in this class.
static NodeList constructNodePath(Node s, Node t, DataProvider pred)
          Like ShortestPaths.constructNodePath(Node,Node,Edge[]) with the difference that the path edges are given by a DataProvider.
static NodeList constructNodePath(Node s, Node t, Edge[] pred)
          Conveniance method that constructs an explicit node path from the result yielded by one of the shortest paths methods defined in this class.
static void dijkstra(Graph graph, Node s, boolean directed, DataProvider cost, NodeMap dist, NodeMap pred)
          Like ShortestPaths.dijkstra(Graph, Node, boolean, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.
static void dijkstra(Graph graph, Node s, boolean directed, double[] cost, double[] dist)
          This method solves the single-source shortest path problem for arbitrary graphs.
static void dijkstra(Graph graph, Node s, boolean directed, double[] cost, double[] dist, Edge[] pred)
          Like ShortestPaths.dijkstra(Graph, Node, boolean, double[], double[]) but additionally this method yields the path edges of each calculated shortest path.
static void findShortestUniformPaths(Graph graph, Node start, Node end, boolean directed, EdgeMap pathMap)
          Marks all edges that belong to a shortest path from start to end node.
static boolean singleSource(Graph graph, Node s, boolean directed, DataProvider cost, NodeMap dist, NodeMap pred)
          Like ShortestPaths.singleSource(Graph, Node, boolean, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.
static boolean singleSource(Graph graph, Node s, boolean directed, double[] cost, double[] dist)
          This method solves the single-source shortest path problem for arbitrary graphs.
static boolean singleSource(Graph graph, Node s, boolean directed, double[] cost, double[] dist, Edge[] pred)
          Like ShortestPaths.singleSource(Graph, Node, boolean, double[], double[]) but additionally this method yields the path edges of each calculated shortest path.
static EdgeList singleSourceSingleSink(Graph graph, Node s, Node t, boolean directed, DataProvider cost)
          Similar to ShortestPaths.singleSourceSingleSink(Graph,Node,Node,boolean,DataProvider,NodeMap) but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned.
static double singleSourceSingleSink(Graph graph, Node s, Node t, boolean directed, DataProvider cost, NodeMap pred)
          Like ShortestPaths.singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.
static EdgeList singleSourceSingleSink(Graph graph, Node s, Node t, boolean directed, double[] cost)
          Similar to ShortestPaths.singleSourceSingleSink(Graph,Node,Node,boolean,double[],Edge[]) but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned.
static double singleSourceSingleSink(Graph graph, Node s, Node t, boolean directed, double[] cost, Edge[] pred)
          This method solves the single-source single-sink shortest path problem for arbitrary graphs.
static void uniform(Graph graph, Node s, boolean directed, double[] dist)
          This method solves the single-source shortest path problem for arbitrary graphs where each edge has a uniform cost of 1.0.
static void uniform(Graph graph, Node s, boolean directed, double[] dist, Edge[] pred)
          Like ShortestPaths.uniform(Graph, Node, boolean, double[]) but additionally this method yields the path edges of each calculated shortest path.
static void uniform(Graph graph, Node s, boolean directed, NodeMap dist, NodeMap pred)
          Like ShortestPaths.uniform(Graph, Node, boolean, double[], Edge[]) but uses NodeMaps instead of arrays.
static double[] uniformCost(Graph graph)
          Conveniance method that returns an array containing uniform edge costs of 1.0 for each edge of the given graph.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

uniform

public static void uniform(Graph graph,
                           Node s,
                           boolean directed,
                           double[] dist)
This method solves the single-source shortest path problem for arbitrary graphs where each edge has a uniform cost of 1.0. This method yields the shortest distance from a given node s to all other nodes.

Precondition:
dist.length == graph.N()
Complexity:
O(graph.N()+graph.E())
Parameters:
graph - the graph being acted upon
s - the start node for the shortest path search
directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
dist - return value that will hold the shortest distance from node s to all other nodes. The distance from s to v is dist[v.index()]. If there is no path from s to v then dist[v.index()] == Double.POSITIVE_INFINITY.

uniform

public static void uniform(Graph graph,
                           Node s,
                           boolean directed,
                           double[] dist,
                           Edge[] pred)
Like ShortestPaths.uniform(Graph, Node, boolean, double[]) but additionally this method yields the path edges of each calculated shortest path.

Precondition:
pred.length == graph.N()
Parameters:
pred - return value that holds for each node t the shortest path edge pred[t.index()] which is the last edge on the shortest path from s to t. If t == s or if there is no shortest path from s to t then pred[t.index()] == null.
See Also:
ShortestPaths.constructNodePath(Node, Node, Edge[]), ShortestPaths.constructEdgePath(Node, Node, Edge[])

uniform

public static void uniform(Graph graph,
                           Node s,
                           boolean directed,
                           NodeMap dist,
                           NodeMap pred)
Like ShortestPaths.uniform(Graph, Node, boolean, double[], Edge[]) but uses NodeMaps instead of arrays.

Parameters:
dist - return value. the map will provide a double value for each node.
pred - return value. the map will provide an Edge for each node.

acyclic

public static boolean acyclic(Graph graph,
                              Node s,
                              double[] cost,
                              double[] dist)
This method solves the single-source shortest path problem for acyclic directed graphs. Associated with each edge is an arbitrary double value that represents the cost of that edge. This method yields the shortest distance from a given node s to all other nodes.

Preconditions:
GraphChecker.isAcyclic(graph)
cost.length == graph.E()
dist.length == graph.N()
Complexity:
O(graph.N()+graph.E())
Parameters:
graph - the graph being acted upon
s - the start node for the shortest path search
cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].
dist - return value that will hold the shortest distance from node s to all other nodes. The distance from s to v is dist[v.index()]. If there is no path from s to v then dist[v.index()] == Double.POSITIVE_INFINITY.
Returns:
false if the input graph was not acyclic.

acyclic

public static boolean acyclic(Graph graph,
                              Node s,
                              double[] cost,
                              double[] dist,
                              Edge[] pred)
Like ShortestPaths.acyclic(Graph, Node, double[], double[]) but additionally this method yields the path edges of each calculated shortest path.

Precondition:
pred.length == graph.N()
Parameters:
pred - return value that holds for each node t the shortest path edge pred[t.index()] which is the last edge on the shortest path from s to t. If t == s or if there is no shortest path from s to t then pred[t.index()] == null.
See Also:
ShortestPaths.constructNodePath(Node, Node, Edge[]), ShortestPaths.constructEdgePath(Node, Node, Edge[])

acyclic

public static boolean acyclic(Graph graph,
                              Node s,
                              DataProvider cost,
                              NodeMap dist,
                              NodeMap pred)
Like ShortestPaths.acyclic(Graph, Node, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.

Parameters:
cost - must provide a double value for each edge.
dist - return value. the map will provide a double value for each node.
pred - return value. the map will provide an Edge for each node.

dijkstra

public static void dijkstra(Graph graph,
                            Node s,
                            boolean directed,
                            double[] cost,
                            double[] dist)
This method solves the single-source shortest path problem for arbitrary graphs. Associated with each edge is a non-negative double value that represents the cost of that edge. This method yields the shortest distance from a given node s to all other nodes.

Preconditions:
For each edge e: cost[e.index()] >= 0
cost.length == graph.E()
dist.length == graph.N()
Complexity:
O(graph.E()+graph.N()*log(graph.N())
Parameters:
graph - the graph being acted upon
s - the start node for the shortest path search
directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].
dist - return value that will hold the shortest distance from node s to all other nodes. The distance from s to v is dist[v.index()]. If there is no path from s to v then dist[v.index()] == Double.POSITIVE_INFINITY.

dijkstra

public static void dijkstra(Graph graph,
                            Node s,
                            boolean directed,
                            double[] cost,
                            double[] dist,
                            Edge[] pred)
Like ShortestPaths.dijkstra(Graph, Node, boolean, double[], double[]) but additionally this method yields the path edges of each calculated shortest path.

Precondition:
pred.length == graph.N()
Parameters:
pred - return value that holds for each node t the shortest path edge pred[t.index()] which is the last edge on the shortest path from s to t. If t == s or if there is no shortest path from s to t then pred[t.index()] == null.
See Also:
ShortestPaths.constructNodePath(Node, Node, Edge[]), ShortestPaths.constructEdgePath(Node, Node, Edge[])

dijkstra

public static void dijkstra(Graph graph,
                            Node s,
                            boolean directed,
                            DataProvider cost,
                            NodeMap dist,
                            NodeMap pred)
Like ShortestPaths.dijkstra(Graph, Node, boolean, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.

Parameters:
cost - must provide a double value for each edge.
dist - return value. the map will provide a double value for each node.
pred - return value. the map will provide an Edge for each node.

singleSourceSingleSink

public static double singleSourceSingleSink(Graph graph,
                                            Node s,
                                            Node t,
                                            boolean directed,
                                            double[] cost,
                                            Edge[] pred)
This method solves the single-source single-sink shortest path problem for arbitrary graphs. Associated with each edge is a non-negative double value that represents the cost of that edge. This method returns the shortest distance from node s to node t. It also returns information to construct the actual path between these to nodes.

Preconditions:
For each edge e: cost[e.index()] >= 0
cost.length == graph.E()
pred.length == graph.N()
Complexity:
O(graph.E()+graph.N()*log(graph.N())
Parameters:
graph - the graph being acted upon
s - the source node for the shortest path search
t - the sink node for the shortest path search
directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].
pred - return value that holds for each node v on the the shortest the path from s to t an edge pred[v.index()] which is the last edge on the shortest path from s to v. If v == s or if there is no shortest path from s to v then pred[v.index()] == null.
Returns:
the distance between s and t if a path between these two nodes exist and Double.POSITIVE_INFINITY otherwise.
See Also:
ShortestPaths.constructNodePath(Node, Node, Edge[]), ShortestPaths.constructEdgePath(Node, Node, Edge[])

singleSourceSingleSink

public static EdgeList singleSourceSingleSink(Graph graph,
                                              Node s,
                                              Node t,
                                              boolean directed,
                                              double[] cost)
Similar to ShortestPaths.singleSourceSingleSink(Graph,Node,Node,boolean,double[],Edge[]) but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned. If the returned path is empty then there is no path between the nodes.

Returns:
a shortest path between source and sink

singleSourceSingleSink

public static EdgeList singleSourceSingleSink(Graph graph,
                                              Node s,
                                              Node t,
                                              boolean directed,
                                              DataProvider cost)
Similar to ShortestPaths.singleSourceSingleSink(Graph,Node,Node,boolean,DataProvider,NodeMap) but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned. If the returned path is empty then there is no path between the nodes.

Returns:
a shortest path between source and sink

singleSourceSingleSink

public static double singleSourceSingleSink(Graph graph,
                                            Node s,
                                            Node t,
                                            boolean directed,
                                            DataProvider cost,
                                            NodeMap pred)
Like ShortestPaths.singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.

Parameters:
cost - must provide a double value for each edge.
pred - return value. the map will provide an Edge for each node.

bellmanFord

public static boolean bellmanFord(Graph graph,
                                  Node s,
                                  boolean directed,
                                  double[] cost,
                                  double[] dist)
This method solves the single-source shortest path problem for arbitrary graphs. Associated with each edge is an arbitrary double value that represents the cost of that edge. In case the given weighted graph contains no negative cost cycles this method will yield the shortest distance from a given node s to all other nodes. If, on the other hand, the given graph contains negative-cost cycles this method will yield no reasonable result which will be indicated by the return value false.

Preconditions:
cost.length == graph.E()
dist.length == graph.N()
Complexity:
O(graph.E()*min(D,graph.N())) where D is the maximal number of edges in any shortest path.
Parameters:
graph - the graph being acted upon
s - the start node for the shortest path search
directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].
dist - return value that will hold the shortest distance from node s to all other nodes. The distance from s to v is dist[v.index()]. If there is no path from s to v then dist[v.index()] == Double.POSITIVE_INFINITY.
Returns:
false if this weighted graph contains a negative cost cycle, true otherwise.

bellmanFord

public static boolean bellmanFord(Graph graph,
                                  Node s,
                                  boolean directed,
                                  double[] cost,
                                  double[] dist,
                                  Edge[] pred)
Like ShortestPaths.bellmanFord(Graph, Node, boolean, double[], double[]) but additionally this method yields the path edges of each calculated shortest path.

Precondition:
pred.length == graph.N()
Parameters:
pred - return value that holds for each node t the shortest path edge pred[t.index()] which is the last edge on the shortest path from s to t. If t == s or if there is no shortest path from s to t then pred[t.index()] == null.
See Also:
ShortestPaths.constructNodePath(Node, Node, Edge[]), ShortestPaths.constructEdgePath(Node, Node, Edge[])

bellmanFord

public static boolean bellmanFord(Graph graph,
                                  Node s,
                                  boolean directed,
                                  DataProvider cost,
                                  NodeMap dist,
                                  NodeMap pred)
Like ShortestPaths.bellmanFord(Graph, Node, boolean, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.

Parameters:
cost - must provide a double value for each edge.
dist - return value. the map will provide a double value for each node.
pred - return value. the map will provide an Edge for each node.

singleSource

public static boolean singleSource(Graph graph,
                                   Node s,
                                   boolean directed,
                                   double[] cost,
                                   double[] dist)
This method solves the single-source shortest path problem for arbitrary graphs. Depending on the structure of the given graph and the values of the given edge costs it delegates its job to the algorithm with the theoretically best running time. Please not that theory does not necessarily reflect practice.

Preconditions:
cost.length == graph.E()
dist.length == graph.N()
Parameters:
graph - the graph being acted upon
s - the start node for the shortest path search
directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].
dist - return value that will hold the shortest distance from node s to all other nodes. The distance from s to v is dist[v.index()]. If there is no path from s to v then dist[v.index()] == Double.POSITIVE_INFINITY.
Returns:
false if this weighted graph contains a negative cost cycle, true otherwise.

singleSource

public static boolean singleSource(Graph graph,
                                   Node s,
                                   boolean directed,
                                   double[] cost,
                                   double[] dist,
                                   Edge[] pred)
Like ShortestPaths.singleSource(Graph, Node, boolean, double[], double[]) but additionally this method yields the path edges of each calculated shortest path.

Precondition:
pred.length == graph.N()
Parameters:
pred - return value that holds for each node t the shortest path edge pred[t.index()] which is the last edge on the shortest path from s to t. If t == s or if there is no shortest path from s to t then pred[t.index()] == null.
See Also:
ShortestPaths.constructNodePath(Node, Node, Edge[]), ShortestPaths.constructEdgePath(Node, Node, Edge[])

singleSource

public static boolean singleSource(Graph graph,
                                   Node s,
                                   boolean directed,
                                   DataProvider cost,
                                   NodeMap dist,
                                   NodeMap pred)
Like ShortestPaths.singleSource(Graph, Node, boolean, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.

Parameters:
cost - must provide a double value for each edge.
dist - return value. the map will provide a double value for each node.
pred - return value. the map will provide an Edge for each node.

allPairs

public static boolean allPairs(Graph graph,
                               boolean directed,
                               double[] cost,
                               double[][] dist)
This method solves the all-pairs shortest path problem for graphs with arbitrary edge costs. If the given graph contains a negative cost cycle, then false is returned and the values returned in dist are left unspecified.

Preconditions:
cost.length == graph.E();
dimension of dist: [graph.N()][graph.N()]]
Complexity:
O(graph.N())*O(singleSource)
Parameters:
graph - the graph being acted upon
directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].
dist - return value that will hold the shortest path distances from all pairs of nodes s and t in the graph. The distance from s to t is dist[s.index()][t.index()]. If there is no path from s to t then dist[s.index()][t.index()] == Double.POSITIVE_INFINITY.
Returns:
whether or not thee given graph contains a negative cost cycle.

findShortestUniformPaths

public static void findShortestUniformPaths(Graph graph,
                                            Node start,
                                            Node end,
                                            boolean directed,
                                            EdgeMap pathMap)
Marks all edges that belong to a shortest path from start to end node. This method assumes that each edge of the input graph has a cost of 1.0.

Complexity:
O(g.N()+g.E())
Parameters:
graph - the input graph
start - the start node
end - the end node
directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
pathMap - the result. For each edge a boolean value will indicate whether or not it belongs to a shortest path connecting the two nodes.

uniformCost

public static double[] uniformCost(Graph graph)
Conveniance method that returns an array containing uniform edge costs of 1.0 for each edge of the given graph.

Returns:
an array cost[] that contains uniform edge costs of 1.0 for each edge e: cost[e.index()] == 1.0.

constructNodePath

public static NodeList constructNodePath(Node s,
                                         Node t,
                                         Edge[] pred)
Conveniance method that constructs an explicit node path from the result yielded by one of the shortest paths methods defined in this class.

Parameters:
s - the start node of the shortest path. This must be the same start node that was specified when pred was calculated.
t - the end node of the path
pred - the shortest path edge result array returned by one of the shortest path edge methods defined in this class.
Returns:
a node list that holds the nodes on the shortest path from s to t in the correct order. If there is no path from s to t then an empty list is returned.

constructNodePath

public static NodeList constructNodePath(Node s,
                                         Node t,
                                         DataProvider pred)
Like ShortestPaths.constructNodePath(Node,Node,Edge[]) with the difference that the path edges are given by a DataProvider.

Parameters:
pred - the shortest path edge result DataProvider returned by one of the shortest path edge methods defined in this class.

constructEdgePath

public static EdgeList constructEdgePath(Node s,
                                         Node t,
                                         Edge[] pred)
Conveniance method that constructs an explicit edge path from the result yielded by one of the shortest paths methods defined in this class.

Parameters:
s - the start node of the shortest path. This must be the same start node that was specified when pred was calculated.
t - the end node of the path
pred - the shortest path edge result array returned by one of the shortest path edge methods defined in this class.
Returns:
an edge list that holds the edges on the shortest path from s to t in the correct order. If there is no path from s to t then an empty list is returned.

constructEdgePath

public static EdgeList constructEdgePath(Node s,
                                         Node t,
                                         DataProvider pred)
Like ShortestPaths.constructEdgePath(Node,Node,Edge[]) with the difference that the path edges are given by a DataProvider.

Parameters:
pred - the shortest path edge result DataProvider returned by one of the shortest path edge methods defined in this class.
Overview  Package   Class  Tree  Deprecated  Index  Help 
© Copyright 2000-2003,
yWorks GmbH.
All rights reserved.
2003
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD