mentor/src/pktroute/GraphRep.i3


 Copyright 1993 Digital Equipment Corporation.                             
 Distributed only by permission.                                           
                                                                           
 Last modified on Fri Jul 30 09:03:31 PDT 1993 by heydon                   

INTERFACE GraphRep;
The GraphRep interface reveals the representation of the default implementations declared in the Graph interface.

IMPORT Graph;

REVEAL
  Graph.T <: TRep;

TYPE
  TRep = Graph.TPublic BRANDED OBJECT
    nodeCnt: CARDINAL
  END;
The allocated nodes are [0, nodeCnt), so nodeCnt is the total number of allocated nodes.

TYPE
  NodeList = REF RECORD
    node: CARDINAL;
    weight: REAL;
    next: NodeList := NIL
  END;

REVEAL
  Graph.Sparse <: SparseRep;

TYPE
  SparseRep = Graph.SparsePublic BRANDED OBJECT
    adj: REF ARRAY OF NodeList;
  END;
A Graph.Sparse is represented by adjacency lists. For any node i in the sparse graph g, g.adj[i] is a list of the adjacent nodes (and the weight of the corresponding edges) to i.

END GraphRep.