incremental_single_pair_shortest_path(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Modified, -Path)

Graph

a graph structure

DistanceArg

which argument of EdgeData to use as distance: integer

SourceNode

source node number (integer)

SinkNode

sink node number (integer)

Modified

list of e/3 edge structures whose DistanceArg argument has been modified

Path

Length-EdgeList structure

Description

Incrementally computes shortest paths from SourceNode to SinkNode. Alternative paths are generated on backtracking. Fails if there is no path at all.

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 positive 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.

Modified is the list of e/3 edge structures whose DistanceArg argument has been modified since the last computation for this SourceNode.

All paths returned will have the same length and will be shortest paths from SourceNode to SinkNode. Note that the solutions are not generated in any specific order.

A resulting path is returned as a Length-EdgeList structure where Length is the length of the path and EdgeList is the path in reverse order, i.e. starting with the edge reaching SinkNode and ending with the edge starting from SourceNode.

Modes and Determinism

• incremental_single_pair_shortest_path(+, +, +, +, +, -) is nondet

Fail Conditions

Examples

    ?- sample_graph(G), incremental_single_pair_shortest_path(G, 0, 1, M, P).
    P = 2 - [e(2, 3, 1), e(1, 2, 1)]
    

See Also