all_short_paths_as_edges(+Graph, +DistanceArg, +SourceNode, +Tolerance, -Lengths, -Predecessors)

Graph

a graph structure

DistanceArg

which argument of EdgeData to use as distance (integer)

SourceNode

source node number (integer)

Tolerance

tolerable deviation from minimal length (non-negative number)

Lengths

array of numbers (minimum path lengths)

Predecessors

array of lists of e/3 edge structures

Description

Computes all shortest paths from the single source node SourceNode to every sink node which is reachable from it. The result is returned in the form of the Predecessors array which contains all relevant edges.

DistanceArg refers to the graph's EdgeData information that was specified when the graph was constructed. If EdgeData is a simple number, then DistanceArg should be 0 and EdgeData will be taken as the length of the edge. If EdgeData is a compound data structure, DistanceArg should be a number between 1 and the arity of that structure and determines which argument of the EdgeData structure will be interpreted as the edge's length. Important: the distance information in EdgeData must be a non-negative number.

If DistanceArg is given as -1, then any EdgeData is ignored and the length of every edge is assumed to be equal to 1.

SourceNode is the common starting point for the computed paths.

Tolerance should be zero in order to find only the shortest paths. If Tolerance is greater than zero, then all paths that are within this tolerance of the shortest path length will be found.

The result is returned in the form of two arrays, whose indices range over the possible sink nodes. The Lengths array indicates the length of a shortest path from SourceNode to the corresponding sink node. The Predecessors array is an array of edge lists, each list containing the alternative edges that are part of a shortest path from SourceNode to the corresponding sink node.

If there is no path from SourceNode to a sink node J, then both Lengths[J] and Predecessors[J] are uninstantiated. Otherwise, Lengths[J] contains the length of a shortest path from SourceNode to J. Predecessors[J] is contains a list of alternative edges that lead from some predecessor node to J in a shortest path from SourceNode to J. Predecessors[SourceNode] is always the empty list [].

Assembling Actual Paths

To generate an actual path from the Predecessors array, start from the sink node J, select one of the alternative edges in Predecessors[J] to find a predecessor node, and continue this process until the SourceNode is reached. Depending on the parameters, the following 3 cases can occur:

1. Tolerance is zero, and Graph did not contain zero-length edges: in this case, SubGraph is cycle-free and shortest paths can be found by simply selecting arbitrary incoming edges until SourceNode is reached.
2. Tolerance is zero, and Graph did contain zero-length edges: in this case, SubGraph may contain (zero-length) cycles which one may want to exclude when constructing paths.
3. Tolerance is nonzero: in this case, SubGraph may contain cycles (of maximum length Tolerance). Moreover, it may be possible to use the edges in SubGraph to construct cycle-free paths whose total length is greater than the shortest path length plus the tolerance. These may need to be excluded explicitly.

Modes and Determinism

• all_short_paths_as_edges(+, +, +, +, -, -) is det

Examples

    ?- sample_graph(G), all_short_paths_as_edges(G, 0, 1, 0, L, E).
    L = [](0, 1, 2, 3, 2, 1, 1, _326, _327, 2, 3, 3, 3)
    E = []([], [e(1, 2, 1)], [e(7, 3, 1)], [e(5, 4, 1)],
	   [e(7, 5, 1), e(6, 5, 1)], [e(1, 6, 1)], [e(1, 7, 1)],
	   _342, _343, [e(7, 10, 1)], [e(10, 11, 1)], [e(10, 12, 1)],
	   [e(10, 13, 1)])
    

See Also