Graphs0Path.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Created by: Christian Jacobi, September 15, 1986 11:07:56 am PDT
Last edited by: Christian Jacobi, October 18, 1986 1:25:53 pm PDT
DIRECTORY Graphs0;
Graphs0Path: CEDAR DEFINITIONS =
BEGIN
Simple path finding in undirected graphs.
Not optional. (Neither speed nor quality of result).
Does not care about different "power" requirements.
Graph: TYPE = Graphs0.Graph;
Arc: TYPE = Graphs0.Arc;
EnumArcProc: TYPE = Graphs0.EnumArcProc;
NodeSetList: TYPE = LIST OF Graphs0.NodeList;
ArcCostProc:
TYPE =
PROC [arc: Arc, graph: Graph, data:
REF]
RETURNS [cost:
INT←infinite];
The sum of the costs of all arcs in graph with cost #infinite must be smaller
then LAST[INT]. (to prevent arithmetic overflow).
infinite: INT = LAST[INT];
NotConnected: ERROR;
FindPath:
PROC [graph: Graph, nodeSets: NodeSetList, arcCostProc: ArcCostProc, arcDeliverProc: EnumArcProc, data:
REF←
NIL, effort:
NAT ← 1, random:
BOOL←
FALSE]
RETURNS [quit:
BOOL←
FALSE];
Procedure finds a path (tree) to connect all the node sets. All the nodes in a node set
are considered connected with high impedance: the path may connect any node in set
but no pass throughs are made, unless a zero cost arc explicitely allows it.
Procedure returns segments of connection in unspecified order.
Raises NotConnected if the nodes are not connected; may raise other errors on bad input.
Tries to find a good path connecting the node sets, but does not guarantee optimum.
effort: (hint only) small number for fast execution; larger number for good results
random: introduce limited randomness
Restrictions: (may or may not be checked)
The graph topology must not change during path finding.
The cost of arcs must not change except when an(y) arc is delivered.
All arcs must have non negative cost.
The graph must not have arcs making self loops.
END.