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