com.yworks.yfiles.algorithms

Class ShortestPaths

java.lang.Object

com.yworks.yfiles.algorithms.ShortestPaths

public final class ShortestPaths
extends Object

This class provides diverse algorithms and helper methods for solving the shortest path problem on weighted graphs.

Definitions

Given a weighted directed/undirected graph:

• The shortest path problem is the problem of finding a shortest path between a source node s and a target node t such that the sum of the edge costs is minimized.
• The k-shortest path problem is the problem of finding k shortest paths between a source node s and a target node t such that the sum of the edge costs is minimized.
• The single-source shortest path problem is the problem of finding shortest paths from a source node s to all other nodes such that the sum of the edge costs is minimized.
• The single-source single-sink shortest path problem is the problem of finding shortest paths from a source node s to a target node t such that the sum of the edge costs is minimized.
• The all-pairs shortest path problem is the problem of finding shortest paths between every pair of nodes such that the sum of the edge costs is minimized.

Method Summary

Modifier and Type	Method and Description
static boolean	acyclic(Graph graph, Node s, double[] cost, double[] dist) Solves the single-source shortest path problem for acyclic directed graphs.
static boolean	acyclic(Graph graph, Node s, double[] cost, double[] dist, Edge[] pred) Solves the single-source shortest path problem for acyclic directed graphs.
static boolean	acyclic(Graph graph, Node s, IDataProvider cost, INodeMap dist, INodeMap pred) Each edge is associated with an arbitrary double value that represents the cost of that edge.
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, double[] cost, double[] dist) 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) Solves the single-source shortest path problem for arbitrary graphs.
static boolean	bellmanFord(Graph graph, Node s, boolean directed, IDataProvider cost, INodeMap dist, INodeMap pred) Solves the single-source shortest path problem for arbitrary graphs.
static EdgeList	constructEdgePath(Node s, Node t, Edge[] pred) Convenience method that constructs an explicit path of edges from the result returned by one of the shortest paths methods defined in this class.
static EdgeList	constructEdgePath(Node s, Node t, IDataProvider pred) Like constructEdgePath(Node, Node, Edge[]) but the path edges are given by a IDataProvider.
static NodeList	constructNodePath(Node s, Node t, Edge[] pred) Convenience method that constructs an explicit path of nodes from the result returned by one of the shortest paths methods defined in this class.
static NodeList	constructNodePath(Node s, Node t, IDataProvider pred) Like constructNodePath(Node, Node, Edge[]) but the path edges are given by a IDataProvider.
static void	dijkstra(Graph graph, Node s, boolean directed, double[] cost, double[] dist) 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) Solves the single-source shortest path problem for arbitrary graphs.
static void	dijkstra(Graph graph, Node s, boolean directed, IDataProvider cost, INodeMap dist, INodeMap pred) Solves the single-source shortest path problem for arbitrary graphs.
static void	findShortestUniformPaths(Graph graph, Node start, IDataProvider targetMap, boolean directed, int maxLength, EdgeList pathEdges, NodeList pathNodes) Finds all nodes and edges that belong to a shortest path from a start node to a set of target nodes in the graph not farther away than a given distance.
static void	findShortestUniformPaths(Graph graph, Node start, Node end, boolean directed, IEdgeMap pathMap) Marks all edges that belong to a shortest path from start node to target node.
static YList	kShortestPaths(Graph graph, IDataProvider costDP, Node start, Node end, int k) This method finds the k shortest paths connecting a pair of nodes in a directed graph with non-negative edge costs.
static ICursor	kShortestPathsCursor(Graph graph, IDataProvider costDP, Node start, Node end, int k) A variant of kShortestPaths(Graph, IDataProvider, Node, Node, int) that returns the result as a special cursor that calculates the next path in the sequence only when needed.
static EdgeList[]	shortestPair(Graph graph, Node source, Node target, boolean directed, IDataProvider costDP) Returns two edge-disjoint paths in a non-negatively weighted directed graph, such that both paths connect nodes s and t and have minimum total length.
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) This method solves the single-source shortest path problem for arbitrary graphs.
static boolean	singleSource(Graph graph, Node s, boolean directed, IDataProvider cost, INodeMap dist, INodeMap pred) This method solves the single-source shortest path problem for arbitrary graphs.
static EdgeList	singleSourceSingleSink(Graph graph, Node s, Node t, boolean directed, double[] cost) Similar to 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 EdgeList	singleSourceSingleSink(Graph graph, Node s, Node t, boolean directed, IDataProvider cost) Similar to singleSourceSingleSink(Graph, Node, Node, boolean, IDataProvider, INodeMap) 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, IDataProvider cost, INodeMap pred) Like singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[]) but uses INodeMaps and IDataProviders instead of arrays.
static void	uniform(Graph graph, Node s, boolean directed, double[] dist) Solves the single-source shortest path problem for arbitrary graphs in which each edge has a uniform cost of 1.0.
static void	uniform(Graph graph, Node s, boolean directed, double[] dist, Edge[] pred) Solves the single-source shortest path problem for arbitrary graphs in which each edge has a uniform cost of 1.0.
static void	uniform(Graph graph, Node s, boolean directed, INodeMap dist, INodeMap pred) Like uniform(Graph, Node, boolean, double[], Edge[]) but uses INodeMaps instead of arrays.
static double[]	uniformCost(Graph graph) Convenience 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

acyclic

public static final boolean acyclic(Graph graph,
                                    Node s,
                                    double[] cost,
                                    double[] dist)

Solves the single-source shortest path problem for acyclic directed graphs.

Each edge is associated with 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.

Precondition:

pred.length == graph.N()

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

dist - an array of values that will be filled during the execution and returns 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:

true if the input graph is acyclic, false otherwise

See Also:

acyclic(Graph, Node, double[], double[], Edge[]), constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

acyclic

public static final boolean acyclic(Graph graph,
                                    Node s,
                                    double[] cost,
                                    double[] dist,
                                    Edge[] pred)

Solves the single-source shortest path problem for acyclic directed graphs.

Each edge is associated with 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.

Precondition:

pred.length == graph.N()

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

dist - an array of values that will be filled during the execution and returns 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.

pred - an array of Edges that will be filled during the execution and returns 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.

Returns:

true if the input graph is acyclic, false otherwise

See Also:

acyclic(Graph, Node, double[], double[], Edge[]), constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

acyclic

public static final boolean acyclic(Graph graph,
                                    Node s,
                                    IDataProvider cost,
                                    INodeMap dist,
                                    INodeMap pred)

Each edge is associated with 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.

Precondition:

pred.length == graph.N()

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

cost - the IDataProvider that returns the double value (cost) for traversing each edge

dist - the INodeMap that will be filled during the execution and returns a double value (shortest distance) from node s to all other nodes or Double.POSITIVE_INFINITY if no such paths exist

pred - the INodeMap that will be filled during the execution and returns for each node t the last edge on the shortest path from s to t or null if t == s or no shortest path from s to t exists

Returns:

true if the input graph is acyclic, false otherwise

See Also:

acyclic(Graph, Node, double[], double[], Edge[])

allPairs

public static final 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.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Preconditions:

cost.length == graph.E()

Dimension of dist: [graph.N()] [graph.N()]]

Complexity:

O(graph.N()) * O(singleSource)

Parameters:

graph - the input graph

directed - true if the graph should be considered as directed, false otherwise

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

dist - an array of values that will be filled during the execution and returns 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:

true if the given graph does not contain a negative-cost cycle, false otherwise

bellmanFord

public static final boolean bellmanFord(Graph graph,
                                        Node s,
                                        boolean directed,
                                        double[] cost,
                                        double[] dist)

Solves the single-source shortest path problem for arbitrary graphs.

Each edge is associated with an arbitrary double value that represents the cost of this 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.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Precondition:

pred.length == graph.N()

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

directed - true if the graph should be considered as directed, false otherwise

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

dist - an array of values that will be filled during the execution and returns 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.

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[]), bellmanFord(Graph, Node, boolean, IDataProvider, INodeMap, INodeMap)

bellmanFord

public static final boolean bellmanFord(Graph graph,
                                        Node s,
                                        boolean directed,
                                        double[] cost,
                                        double[] dist,
                                        Edge[] pred)

Solves the single-source shortest path problem for arbitrary graphs.

Each edge is associated with an arbitrary double value that represents the cost of this 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.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Precondition:

pred.length == graph.N()

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

directed - true if the graph should be considered as directed, false otherwise

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

dist - an array of values that will be filled during the execution and returns 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.

pred - an array of Edges that will be filled during the execution and returns 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:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[]), bellmanFord(Graph, Node, boolean, IDataProvider, INodeMap, INodeMap)

bellmanFord

public static final boolean bellmanFord(Graph graph,
                                        Node s,
                                        boolean directed,
                                        IDataProvider cost,
                                        INodeMap dist,
                                        INodeMap pred)

Solves the single-source shortest path problem for arbitrary graphs.

Each edge is associated with an arbitrary double value that represents the cost of this 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.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Parameters:

graph - the input graph

s - the source node

directed - true if the graph should be considered as directed, false otherwise

cost - the IDataProvider that returns the double value (cost) for traversing each edge

dist - the INodeMap that will be filled during the execution and returns a double value (shortest distance) from node s to all other nodes or Double.POSITIVE_INFINITY if no such paths exist

pred - the INodeMap that will be filled during the execution and returns for each node t the last edge on the shortest path from s to t or null if t == s or no shortest path from s to t exists

See Also:

bellmanFord(Graph, Node, boolean, double[], double[], Edge[])

constructEdgePath

public static final EdgeList constructEdgePath(Node s,
                                               Node t,
                                               Edge[] pred)

Convenience method that constructs an explicit path of edges from the result returned by one of the shortest paths methods defined in this class.

If there is no path from node s to t, then an empty list is returned.

Parameters:

s - the start node of the shortest path which must be the same start node that was specified when pred was calculated

t - the target node of the path

pred - an array of Edges that will be filled during the execution and returns 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.

Returns:

a list containing the edges on the shortest path from s to t in the correct order

See Also:

constructEdgePath(Node, Node, IDataProvider)

constructEdgePath

public static final EdgeList constructEdgePath(Node s,
                                               Node t,
                                               IDataProvider pred)

Like constructEdgePath(Node, Node, Edge[]) but the path edges are given by a IDataProvider.

If there is no path from node s to t, then an empty list is returned.

Parameters:

s - the start node of the shortest path which must be the same start node that was specified when pred was calculated

t - the target node of the path

pred - the INodeMap that will be filled during the execution and returns for each node t the last edge on the shortest path from s to t or null if t == s or no shortest path from s to t exists

Returns:

a list containing the edges on the shortest path from s to t in the correct order

See Also:

constructEdgePath(Node, Node, Edge[])

constructNodePath

public static final NodeList constructNodePath(Node s,
                                               Node t,
                                               Edge[] pred)

Convenience method that constructs an explicit path of nodes from the result returned by one of the shortest paths methods defined in this class.

If there is no path from node s to t, then an empty list is returned.

Parameters:

s - the start node of the shortest path which must be the same start node that was specified when pred was calculated

t - the target node of the path

pred - an array of Edges that will be filled during the execution and returns 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.

Returns:

a list containing the nodes on the shortest path from s to t in the correct order

See Also:

constructNodePath(Node, Node, IDataProvider)

constructNodePath

public static final NodeList constructNodePath(Node s,
                                               Node t,
                                               IDataProvider pred)

Like constructNodePath(Node, Node, Edge[]) but the path edges are given by a IDataProvider.

If there is no path from node s to t, then an empty list is returned.

Parameters:

s - the start node of the shortest path which must be the same start node that was specified when pred was calculated

t - the target node of the path

pred - the INodeMap that will be filled during the execution and returns for each node t the last edge on the shortest path from s to t or null if t == s or no shortest path from s to t exists

Returns:

a list containing the nodes on the shortest path from s to t in the correct order

See Also:

constructNodePath(Node, Node, Edge[])

dijkstra

public static final void dijkstra(Graph graph,
                                  Node s,
                                  boolean directed,
                                  double[] cost,
                                  double[] dist)

Solves the single-source shortest path problem for arbitrary graphs.

Each edge is associated with a non-negative double value that represents the cost of the edge.

This method yields the shortest distance from a given node s to all other nodes.

The costs should be non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Precondition:

pred.length == graph.N()

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

directed - true if the graph should be considered as directed, false otherwise

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

dist - an array of values that will be filled during the execution and returns 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.

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[]), dijkstra(Graph, Node, boolean, IDataProvider, INodeMap, INodeMap)

dijkstra

public static final void dijkstra(Graph graph,
                                  Node s,
                                  boolean directed,
                                  double[] cost,
                                  double[] dist,
                                  Edge[] pred)

Solves the single-source shortest path problem for arbitrary graphs.

Each edge is associated with a non-negative double value that represents the cost of the edge.

This method yields the shortest distance from a given node s to all other nodes.

The costs should be non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Precondition:

pred.length == graph.N()

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

directed - true if the graph should be considered as directed, false otherwise

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

dist - an array of values that will be filled during the execution and returns 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.

pred - an array of Edges that will be filled during the execution and returns 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:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[]), dijkstra(Graph, Node, boolean, IDataProvider, INodeMap, INodeMap)

dijkstra

public static final void dijkstra(Graph graph,
                                  Node s,
                                  boolean directed,
                                  IDataProvider cost,
                                  INodeMap dist,
                                  INodeMap pred)

Solves the single-source shortest path problem for arbitrary graphs.

Each edge is associated with a non-negative double value that represents the cost of the edge.

This method yields the shortest distance from a given node s to all other nodes.

The costs should be non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

directed - true if the graph should be considered as directed, false otherwise

cost - the IDataProvider that returns the double value (cost) for traversing each edge

dist - the INodeMap that will be filled during the execution and returns a double value (shortest distance) from node s to all other nodes or Double.POSITIVE_INFINITY if no such paths exist

pred - the INodeMap that will be filled during the execution and returns for each node t the last edge on the shortest path from s to t or null if t == s or no shortest path from s to t exists

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[]), dijkstra(Graph, Node, boolean, double[], double[], Edge[])

findShortestUniformPaths

public static final void findShortestUniformPaths(Graph graph,
                                                  Node start,
                                                  IDataProvider targetMap,
                                                  boolean directed,
                                                  int maxLength,
                                                  EdgeList pathEdges,
                                                  NodeList pathNodes)

Finds all nodes and edges that belong to a shortest path from a start node to a set of target nodes in the graph not farther away than a given distance.

This method assumes that each edge of the input graph has a cost of 1.0.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Shortest paths longer than maxLength will not be considered.

Complexity:

O(graph.N() + graph.E())

Parameters:

graph - the input graph

start - the start node

targetMap - the IDataProvider that returns a boolean value indicating whether or not a node belongs to the set of target nodes

directed - true if the graph should be considered as directed, false otherwise

maxLength - the maximum edge length of the shortest paths

pathEdges - a list that will be filled during the execution and returns the edges on the shortest path from s to t in the correct order

pathNodes - a list that will be filled during the execution and returns the nodes on the shortest path from s to t in the correct order

findShortestUniformPaths

public static final void findShortestUniformPaths(Graph graph,
                                                  Node start,
                                                  Node end,
                                                  boolean directed,
                                                  IEdgeMap pathMap)

Marks all edges that belong to a shortest path from start node to target node.

This method assumes that each edge of the input graph has a cost of 1.0.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Complexity:

O(graph.N() + graph.E())

Parameters:

graph - the input graph

start - the start node

end - the target node

directed - true if the graph should be considered as directed, false otherwise

pathMap - the IEdgeMap that will be filled during the execution and returns a boolean value indicating whether or not the edge belongs to a shortest path connecting the two nodes

kShortestPaths

public static final YList kShortestPaths(Graph graph,
                                         IDataProvider costDP,
                                         Node start,
                                         Node end,
                                         int k)

This method finds the k shortest paths connecting a pair of nodes in a directed graph with non-negative edge costs.

The result will be returned as a list of EdgeList objects.

The cost should be non-negative.

The returned paths are not required to be simple, i.e. they may contain a node or an edge multiple times.

Complexity:

O(graph.E() + graph.N() * log(graph.N()) + k)

Parameters:

graph - the input graph

costDP - the IDataProvider that returns a double value (cost) for traversing each edge

start - the given start node

end - the given target node

k - a non-negative integer value

Returns:

a list of EdgeList objects each of which represents a path from start node to target node. The i-th path in the list contains the i-th shortest path between the start and target node.

kShortestPathsCursor

public static final ICursor kShortestPathsCursor(Graph graph,
                                                 IDataProvider costDP,
                                                 Node start,
                                                 Node end,
                                                 int k)

A variant of kShortestPaths(Graph, IDataProvider, Node, Node, int) that returns the result as a special cursor that calculates the next path in the sequence only when needed.

The returned cursor only supports the operation Ok, Current and ICursor.next().

The cost should be non-negative.

The returned paths are not required to be simple, i.e. they may contain a node or an edge multiple times.

Complexity:

O(graph.E() + graph.N() * log(graph.N()) + k)

Parameters:

graph - the input graph

costDP - the IDataProvider that returns a double value (cost) for traversing each edge

start - the given start node

end - the given target node

k - a non-negative integer value

Returns:

a cursor that calculates the next path in the sequence only when needed

shortestPair

public static final EdgeList[] shortestPair(Graph graph,
                                            Node source,
                                            Node target,
                                            boolean directed,
                                            IDataProvider costDP)

Returns two edge-disjoint paths in a non-negatively weighted directed graph, such that both paths connect nodes s and t and have minimum total length.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Parameters:

graph - the input graph

source - the source node of the shortest pair

target - the target node of the shortest pair

directed - true if the graph should be considered as directed, false otherwise

costDP - the IDataProvider that returns a double value (cost) for traversing each edge

Returns:

a two-dimensional array of EdgeLists holding the resulting edge-disjoint paths or null if no such edge-disjoint paths exist

singleSource

public static final 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 work to the algorithm with the theoretically best running time. Please note that theory does not necessarily reflect practice.

Precondition:

pred.length == graph.N()

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

directed - true if the graph should be considered as directed, false otherwise

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

dist - an array of values that will be filled during the execution and returns 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:

true if the weighted graph does not contain a negative-cost cycle, false otherwise

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[]), singleSource(Graph, Node, boolean, IDataProvider, INodeMap, INodeMap)

singleSource

public static final boolean singleSource(Graph graph,
                                         Node s,
                                         boolean directed,
                                         double[] cost,
                                         double[] dist,
                                         Edge[] pred)

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 work to the algorithm with the theoretically best running time. Please note that theory does not necessarily reflect practice.

Precondition:

pred.length == graph.N()

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

directed - true if the graph should be considered as directed, false otherwise

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

dist - an array of values that will be filled during the execution and returns 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.

pred - an array of Edges that will be filled during the execution and returns 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.

Returns:

true if the weighted graph does not contain a negative-cost cycle, false otherwise

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[]), singleSource(Graph, Node, boolean, IDataProvider, INodeMap, INodeMap)

singleSource

public static final boolean singleSource(Graph graph,
                                         Node s,
                                         boolean directed,
                                         IDataProvider cost,
                                         INodeMap dist,
                                         INodeMap pred)

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 work to the algorithm with the theoretically best running time. Please note that theory does not necessarily reflect practice.

Parameters:

graph - the input graph

s - the source node

directed - true if the graph should be considered as directed, false otherwise

cost - the IDataProvider that returns the double value (cost) for traversing each edge

dist - the INodeMap that will be filled during the execution and returns a double value (shortest distance) from node s to all other nodes or Double.POSITIVE_INFINITY if no such paths exist

pred - the INodeMap that will be filled during the execution and returns for each node t the last edge on the shortest path from s to t or null if t == s or no shortest path from s to t exists

Returns:

true if the weighted graph does not contain a negative-cost cycle, false otherwise

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[]), singleSource(Graph, Node, boolean, double[], double[], Edge[])

singleSourceSingleSink

public static final EdgeList singleSourceSingleSink(Graph graph,
                                                    Node s,
                                                    Node t,
                                                    boolean directed,
                                                    double[] cost)

Similar to 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.

Each edge is associated with a non-negative double value that represents the cost of the edge.

If the returned path is empty, then there is no path between the nodes.

The costs should be non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Parameters:

graph - the input graph

s - the source node

t - the sink node

directed - true if the graph should be considered as directed, false otherwise

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

Returns:

a shortest path of edges between source and sink

See Also:

singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[]), singleSourceSingleSink(Graph, Node, Node, boolean, IDataProvider), singleSourceSingleSink(Graph, Node, Node, boolean, IDataProvider, INodeMap)

singleSourceSingleSink

public static final 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.

Each edge is associated with a non-negative double value that represents the cost of the edge.

This method returns the shortest distance from node s to node t. It also returns information to construct the actual path between these two nodes.

The costs should be non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Preconditions:

cost.length == graph.E()

pred.length == graph.N()

Complexity:

O(graph.E() + graph.N() * log(graph.N())

Parameters:

graph - the input graph

s - the source node

t - the sink node

directed - true if the graph should be considered as directed, false otherwise

cost - an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

pred - an array of Edges that will be filled during the execution and returns 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.

Returns:

the distance between sand t if a path between these two nodes exists or Double.POSITIVE_INFINITY otherwise

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[]), singleSourceSingleSink(Graph, Node, Node, boolean, IDataProvider), singleSourceSingleSink(Graph, Node, Node, boolean, IDataProvider, INodeMap), singleSourceSingleSink(Graph, Node, Node, boolean, double[])

singleSourceSingleSink

public static final EdgeList singleSourceSingleSink(Graph graph,
                                                    Node s,
                                                    Node t,
                                                    boolean directed,
                                                    IDataProvider cost)

Similar to singleSourceSingleSink(Graph, Node, Node, boolean, IDataProvider, INodeMap) but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned.

Each edge is associated with a non-negative double value that represents the cost of the edge.

If the returned path is empty, then there is no path between the nodes.

The costs should be non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Parameters:

graph - the input graph

s - the source node

t - the sink node

directed - true if the graph should be considered as directed, false otherwise

cost - the IDataProvider that returns the double value (cost) for traversing each edge

Returns:

a shortest path of edges between source and sink

See Also:

singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[]), singleSourceSingleSink(Graph, Node, Node, boolean, IDataProvider, INodeMap), singleSourceSingleSink(Graph, Node, Node, boolean, double[])

singleSourceSingleSink

public static final double singleSourceSingleSink(Graph graph,
                                                  Node s,
                                                  Node t,
                                                  boolean directed,
                                                  IDataProvider cost,
                                                  INodeMap pred)

Like singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[]) but uses INodeMaps and IDataProviders instead of arrays.

Each edge is associated with a non-negative double value that represents the cost of the edge.

The costs should be non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Parameters:

graph - the input graph

s - the source node

t - the sink node

directed - true if the graph should be considered as directed, false otherwise

cost - the IDataProvider that returns the double value (cost) for traversing each edge

pred - the INodeMap that will be filled during the execution and returns for each node t the last edge on the shortest path from s to t or null if t == s or no shortest path from s to t exists

Returns:

a shortest path of edges between source and sink

See Also:

singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[]), singleSourceSingleSink(Graph, Node, Node, boolean, IDataProvider), singleSourceSingleSink(Graph, Node, Node, boolean, double[])

uniform

public static final void uniform(Graph graph,
                                 Node s,
                                 boolean directed,
                                 double[] dist)

Solves the single-source shortest path problem for arbitrary graphs in which each edge has a uniform cost of 1.0.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Precondition:

pred.length == graph.N()

Complexity:

O(graph.N() + graph.E())

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

directed - true if the graph should be considered as directed, false otherwise

dist - an array of values that will be filled during the execution and returns 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.

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

uniform

public static final void uniform(Graph graph,
                                 Node s,
                                 boolean directed,
                                 double[] dist,
                                 Edge[] pred)

Solves the single-source shortest path problem for arbitrary graphs in which each edge has a uniform cost of 1.0.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Precondition:

pred.length == graph.N()

Complexity:

O(graph.N() + graph.E())

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

directed - true if the graph should be considered as directed, false otherwise

dist - an array of values that will be filled during the execution and returns 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.

pred - an array of Edges that will be filled during the execution and returns 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:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

uniform

public static final void uniform(Graph graph,
                                 Node s,
                                 boolean directed,
                                 INodeMap dist,
                                 INodeMap pred)

Like uniform(Graph, Node, boolean, double[], Edge[]) but uses INodeMaps instead of arrays.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Precondition:

pred.length == graph.N()

Complexity:

O(graph.N() + graph.E())

Parameters:

graph - the input graph

s - the node from which the shortest path search starts

directed - true if the graph should be considered as directed, false otherwise

dist - the INodeMap that will be filled during the execution and returns a double value (shortest distance) from node s to all other nodes or Double.POSITIVE_INFINITY if no such paths exist

pred - the INodeMap that will be filled during the execution and returns for each node t the last edge on the shortest path from s to t or null if t == s or no shortest path from s to t exists

See Also:

uniform(Graph, Node, boolean, double[], Edge[]), constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

uniformCost

public static final double[] uniformCost(Graph graph)

Convenience method that returns an array containing uniform edge costs of 1.0 for each edge of the given graph.

Parameters:

graph - the input graph

Returns:

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