DIRECTORY Graphs0; Graphs0Path: CEDAR DEFINITIONS = BEGIN 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]; 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]; END. \Graphs0Path.mesa Copyright c 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 Simple path finding in undirected graphs. Not optional. (Neither speed nor quality of result). Does not care about different "power" requirements. The sum of the costs of all arcs in graph with cost #infinite must be smaller then LAST[INT]. (to prevent arithmetic overflow). 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. Κ†˜codešœ™Kšœ Οmœ1™KšœY™YK™SKšœT™TKšœ%™%Kšœ)™)Kšœ:™:KšœG™GKšœ(™(Kšœ2™2K™—Kšžœ˜—…—ώ