<> <> <> <> <<>> DIRECTORY Graphs0, Process, PropertyLists, Random, RefTab, SafeStorage; Graphs0Impl: CEDAR MONITOR IMPORTS Process, Random, RefTab, SafeStorage EXPORTS Graphs0 = BEGIN OPEN Graphs0; <<>> GraphPrivateRep: PUBLIC TYPE = RECORD [nodes: RefTab.Ref]; Create: PUBLIC PROC [graphInfo: REF _ NIL] RETURNS [graph: Graph] = { graph _ NEW[Graphs0.GraphRec_[ graphInfo: graphInfo, graphPrivate: NEW[GraphPrivateRep_[nodes: RefTab.Create[]]] ]]; SafeStorage.EnableFinalization[graph]; }; <<>> CreateNode: PUBLIC PROC [nodeInfo: REF _ NIL] RETURNS [node: Node] = { node _ NEW[NodeRec_[nodeInfo: nodeInfo]] }; IncludeNode: PUBLIC PROC [graph: Graph, node: Node] = { IF node.incl THEN ERROR; node.incl _ TRUE; IF ~RefTab.Insert[graph.graphPrivate.nodes, node, $TRUE] THEN ERROR }; InternalRemArc: PROC [node: Node, arc: Arc] = { <<--removes arc from a nodes list of arcs>> IF node.arcs=NIL THEN ERROR; IF node.arcs.first=arc THEN node.arcs _ node.arcs.rest ELSE { FOR list: ArcList _ node.arcs, list.rest WHILE list.rest#NIL DO IF list.rest.first=arc THEN {list.rest _ list.rest.rest; RETURN}; ENDLOOP; ERROR --arc was not member of nodes arc list } }; RemoveNode: PUBLIC PROC [graph: Graph, node: Node] RETURNS [removedArcs: ArcList] = { IF ~node.incl THEN ERROR; node.incl _ FALSE; IF ~RefTab.Delete[graph.graphPrivate.nodes, node] THEN ERROR; removedArcs _ node.arcs; FOR list: ArcList _ node.arcs, list.rest WHILE list#NIL DO IF list.first.node1#node THEN InternalRemArc[list.first.node1, list.first]; IF list.first.node2#node THEN InternalRemArc[list.first.node2, list.first]; ENDLOOP; }; AddNewNode: PUBLIC PROC [graph: Graph, nodeInfo: REF _ NIL] RETURNS [node: Node] = { node _ CreateNode[nodeInfo]; IncludeNode[graph, node] }; CreateArc: PUBLIC PROC [arcInfo: REF _ NIL] RETURNS [arc: Arc] = { arc _ NEW[ArcRec_[arcInfo: arcInfo]] }; IncludeArc: PUBLIC PROC [graph: Graph, arc: Arc, node1, node2: Node] = { IF arc.incl OR ~node1.incl OR ~node2.incl THEN ERROR; --implicite nil test for nodes arc.incl _ TRUE; arc.node1 _ node1; arc.node2 _ node2; node1.arcs _ CONS[arc, node1.arcs]; node2.arcs _ CONS[arc, node2.arcs]; }; RemoveArc: PUBLIC PROC [graph: Graph, arc: Arc] = { IF ~arc.incl OR ~arc.node1.incl OR ~arc.node2.incl THEN ERROR; arc.incl _ FALSE; InternalRemArc[arc.node1, arc]; InternalRemArc[arc.node2, arc]; }; AddNewArc: PUBLIC PROC [graph: Graph, arcInfo: REF _ NIL, node1, node2: Node] RETURNS [arc: Arc] = { arc _ CreateArc[arcInfo]; IncludeArc[graph, arc, node1, node2]; }; <<>> EnumNodes: PUBLIC PROC [graph: Graph, enumNode: EnumNodeProc, data: REF_NIL] RETURNS [quit: BOOL _ FALSE] = { Each: RefTab.EachPairAction = {quit _ enumNode[graph, NARROW[key], data]}; quit _ RefTab.Pairs[graph.graphPrivate.nodes, Each] }; EnumArcs: PUBLIC PROC [graph: Graph, enumArc: EnumArcProc, data: REF_NIL] RETURNS [quit: BOOL _ FALSE] = { checkTab: RefTab.Ref _ RefTab.Create[RefTab.GetSize[graph.graphPrivate.nodes]]; EachNode: EnumNodeProc = { FOR list: ArcList _ node.arcs, list.rest WHILE list#NIL DO IF RefTab.Insert[checkTab, list.first, $TRUE] THEN IF enumArc[graph, list.first, data].quit THEN RETURN [quit_TRUE] ENDLOOP }; quit _ EnumNodes[graph, EachNode, data]; }; HasNode: PUBLIC PROC [graph: Graph, node: Node] RETURNS [BOOL] = { IF ~node.incl THEN RETURN [graph=NIL]; RETURN [RefTab.Fetch[graph.graphPrivate.nodes, node].found] }; <<>> HasArc: PUBLIC PROC [graph: Graph, arc: Arc] RETURNS [yes: BOOL] = { IF ~arc.incl THEN RETURN [graph=NIL]; yes _ HasNode[graph, arc.node1]; IF yes#HasNode[graph, arc.node2] THEN ERROR; }; <<>> Check: PUBLIC PROC [graph: Graph] = { EachNode: EnumNodeProc = { IF ~node.incl THEN ERROR; FOR list: ArcList _ node.arcs, list.rest WHILE list#NIL DO IF ~HasArc[graph, list.first] THEN ERROR; IF ~(list.first.node1=node OR list.first.node2=node) THEN ERROR; IF ~HasNode[graph, list.first.node1] THEN ERROR; IF ~HasNode[graph, list.first.node2] THEN ERROR; ENDLOOP }; [] _ EnumNodes[graph, EachNode, NIL] }; NodesInGraph: PUBLIC PROC [graph: Graph] RETURNS [INT] = { RETURN [RefTab.GetSize[graph.graphPrivate.nodes]] }; ArcListLength: PROC [al: ArcList] RETURNS [i: INT_0] = { WHILE al#NIL DO al_al.rest; i_i+1 ENDLOOP }; ArcsInGraph: PUBLIC PROC [graph: Graph] RETURNS [n: INT_0] = { EachNode: EnumNodeProc = { n _ n+ArcListLength[node.arcs]; }; [] _ EnumNodes[graph, EachNode, NIL]; n _ n/2 }; RandomShuffle: PUBLIC PROC [graph: Graph, randomStream: REF] = { rs: Random.RandomStream _ NARROW[randomStream]; EachNode: EnumNodeProc = { <<--goal: O(Num(arcs)), but don't care about optimal shuffling>> <<--in global routing typical node has 4 or less arcs>> num: INT = 6; a: ARRAY [0..num) OF ArcList _ ALL[NIL]; <<--split list randomly into num lists>> FOR l: ArcList _ node.arcs, l.rest WHILE l#NIL DO n: INT _ Random.ChooseInt[rs, 0, num-1]; a[n] _ CONS[l.first, a[n]]; ENDLOOP; <<--merge the num lists >> FOR i: INT DECREASING IN [1..num) DO n: INT _ Random.ChooseInt[rs, 1, i]; FOR l: ArcList _ a[n], l.rest WHILE l#NIL DO a[0] _ CONS[l.first, a[0]]; ENDLOOP; a[n] _ a[i] ENDLOOP; node.arcs _ a[0]; }; [] _ EnumNodes[graph, EachNode, NIL] }; Destroy: PUBLIC PROC [graph: Graph] = { EachNode: EnumNodeProc = { node.nodeInfo _ $DELETED; node.props _ NIL; FOR list: ArcList _ node.arcs, list.rest WHILE list#NIL DO list.first.arcInfo _ $DELETED; list.first.props _ NIL; list.first.node1 _ list.first.node2 _ NIL; ENDLOOP; node.arcs _ NIL; }; [] _ EnumNodes[graph, EachNode]; graph.graphInfo _ $DELETED; graph.props _ NIL; graph.graphPrivate _ NIL; }; FinalizerProcess: PROC[fooFQ: SafeStorage.FinalizationQueue] = { DO Destroy[NARROW[SafeStorage.FQNext[fooFQ]]]; ENDLOOP }; fooFQ: SafeStorage.FinalizationQueue = SafeStorage.NewFQ[]; SafeStorage.EstablishFinalization[CODE[Graphs0.GraphRec], 0, fooFQ]; TRUSTED {Process.Detach[FORK FinalizerProcess[fooFQ]]}; END.