<<-- File: CCG.mesa>> <<-- Last Edited by: CSChow, February 1, 1985 8:07:16 am PST>> <<--Note: CCG = ChannelConstraintGraph>> <<-- This is a bidirectional directed graph. Each node in the graph correspond to one channels. >> <<-- There are two sets of graphs for a layout, viz, a horizontal graph and a vertical graph. >> <<-- Each of which consist of two directed graphs (ie. bottomToTop & topToBottom,>> <<-- and leftToRight & rightToLeft.) These graphs are used to compute the >> <<-- geometrical information of ChannelTopologyGraph.-->> <<>> <<>> CCG: CEDAR DEFINITIONS = BEGIN Ref: TYPE = REF Rep; Rep: TYPE; NodeIndex: TYPE = [1..MaxGraphSize]; MaxGraphSize: NAT = 200; --%Restriction on the maximum number of nodes in the graph %-- MaxEdges: NAT = 20; --%Restriction on the maximum number of edges between nodes%-- GraphDirection: TYPE = {pos, neg}; InvalidNode: ERROR; FindRootError: ERROR[reason: Reasons1]; AssignNodeError: ERROR[reason: Reasons2]; Reasons1: TYPE ={NoRoot, MulitpleRoots}; Reasons2: TYPE ={NotARoot, CyclicGraph}; CleanUpChsProc: TYPE = PROC[chToDestroy, chToMove: REF]; EachChAction: TYPE = PROC[ch: REF] RETURNS [quit: BOOL _ FALSE]; Create: PROC[] RETURNS[Ref]; CreateNode: PROC[grph: Ref, ch: REF _ NIL] RETURNS[NodeIndex]; <<--ch is associated with the node>> <<-- ch is a ref any to make it more general>> DestroyNode: PROC[grph: Ref, node: NodeIndex, p: CleanUpChsProc]; Size: PROC [grph: Ref] RETURNS [NAT]; ConstrainNodes: PROC[grph: Ref, negNd, posNd: NodeIndex, wt: INT]; <<--if there is no edge between negNd and posNd create one with weight wt>> <<-- else set weight of existing edge to max. of wt and previous weight>> <<-- NB: This implies there is at most one edge between any pair of nodes>> CyclicConstrainp: PROC [grph: Ref, negNd, posNd: NodeIndex] RETURNS [cyclic: BOOL]; <<--TRUE iff add constrain between negNd and posNd will result in a cycle in grph>> ResetNode: PROC[grph: Ref, nd: NodeIndex]; -- Clears the nodes so that it can be reused for the next position assignment-- ResetAllNodes: PROC[grph: Ref]; <<-- = {FOR nd: NodeIndex IN [1..grph.size] DO ResetNode[grph, nd] ENDLOOP};>> PosAssignNodePosition: PROC[grph: Ref, root: NodeIndex]; <<-- Do position assignment in positive direction (left-to-right or bottom-to-top)>> NegAssignNodePosition:PROC[grph: Ref, root: NodeIndex]; <<--Do position assignment in negative direction>> NodePosition: PROC[grph: Ref, nd: NodeIndex, which: GraphDirection] RETURNS[INT]; <<--Get position of node (after assignment.)>> SetNodePosition: PROC[grph: Ref, nd: NodeIndex, which: GraphDirection, position: INT]; <<-- Used to set the starting position on root node>> FindRoot: PROC[grph: Ref, which: GraphDirection] RETURNS[nd: NodeIndex]; <<--! ERROR FindRootError>> GetCh: PROC[grph: Ref, nd: NodeIndex] RETURNS [REF]; <<-- Get the ch created associated with the node>> Chs: PROC[grph: Ref, p: EachChAction] RETURNS [BOOL]; --Apply p to ch in all nodes of grph or until p returns True. -- Chs returns true <=> p returns true on none of the ch. END.