1(*
2 *  gr.sml - definitions that are shared among different graph implementations
3 *
4 *  COPYRIGHT (c) 1997 by Martin Erwig.  See COPYRIGHT file for details.
5 *)
6
7(*
8   structures and functors defined:
9
10    GraphNode          defines type of graph nodes
11    GraphExceptions    defines graph exceptions
12    GraphTypes         functor for deriving types from graph implementation
13    UnlabGraphTypes    functor for deriving types from graph implementation
14    StampUtil          time stamping utilities
15    SortEdges          utilities to sort successors/predecessors) by edge labels
16 *)
17
18structure GraphNode : GRAPH_NODE =
19struct
20  type node = int
21end
22
23
24structure GraphExceptions : GRAPH_EXCEPTIONS =
25struct
26  exception Node
27  exception Edge
28  exception NotImplemented
29end
30
31
32
33(* functors deriving types from graph implementations *)
34
35functor UnlabGraphTypes (type 'a graph) : UNLAB_GRAPH_TYPES =
36struct
37  type node          = GraphNode.node
38  type 'a graph      = 'a graph
39  type 'a adj        = 'a * node list
40  type 'a context    = node list * node * 'a * node list
41  type 'a decomp     = 'a context * 'a graph
42  type 'a fwd_decomp = 'a adj * 'a graph
43end
44
45
46functor GraphTypes (type ('a,'b) graph) : GRAPH_TYPES =
47struct
48  type node               = GraphNode.node
49  type ('a,'b) graph      = ('a,'b) graph
50  type     'b out         = ('b * node) list
51  type ('a,'b) adj        = 'a * 'b out
52  type ('a,'b) context    = 'b out * node * 'a * 'b out
53  type ('a,'b) decomp     = ('a,'b) context * ('a,'b) graph
54  type ('a,'b) fwd_decomp = ('a,'b) adj * ('a,'b) graph
55end
56