source: project/release/4/9ML-toolkit/trunk/sml-lib/graph.sig @ 29995

Last change on this file since 29995 was 29995, checked in by Ivan Raikov, 8 years ago

9ML-toolkit: added SML support libraries

File size: 2.9 KB
Line 
1(* graph.sig
2 *
3 * COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies
4 *
5 *  A generic directed graph data structure. 
6 *  Implemented in an ``object oriented style''
7 *  All graphs are based on this interface.
8 *
9 *  -- Allen
10 *)
11
12signature GRAPH =
13sig
14
15   exception Graph of string (* Bug *)
16   exception Subgraph        (* subgraph constraint failure *)
17   exception NotFound        (* element not located *)
18   exception Unimplemented   (* method is not implemented *)
19   exception Readonly        (* modification fails *)
20   exception NotSingleEntry  (* should be single entry *)
21   exception NotSingleExit   (* should be single exit *)
22
23
24   type node_id = int
25   type 'n node = node_id * 'n
26   type 'e edge = node_id * node_id * 'e
27
28   type ('n,'e,'g) graph_methods =
29       {  name            : string,
30          graph_info      : 'g,
31
32          (* inserting/removing nodes and edges *)
33          new_id          : unit -> node_id,
34          add_node        : 'n node -> unit,
35          add_edge        : 'e edge -> unit,
36          remove_node     : node_id -> unit,
37          set_out_edges   : node_id * 'e edge list -> unit,
38          set_in_edges    : node_id * 'e edge list -> unit,
39          set_entries     : node_id list -> unit,
40          set_exits       : node_id list -> unit,
41
42          (* collect deleted node ids *)
43          garbage_collect : unit -> unit,
44
45          (* selectors *)
46          nodes           : unit -> 'n node list,
47          edges           : unit -> 'e edge list,
48          order           : unit -> int,        (* # nodes *)
49          size            : unit -> int,        (* # edges *)
50          capacity        : unit -> int,        (* max. node_id < capacity *)
51          succ            : node_id -> node_id list,
52          pred            : node_id -> node_id list,
53          out_edges       : node_id -> 'e edge list,
54          in_edges        : node_id -> 'e edge list,
55          has_edge        : node_id * node_id -> bool,
56          has_node        : node_id -> bool,
57          node_info       : node_id -> 'n,
58          entries         : unit -> node_id list,
59          exits           : unit -> node_id list,
60          entry_edges     : node_id -> 'e edge list,
61          exit_edges      : node_id -> 'e edge list,
62
63          (* iterators *)
64          forall_nodes    : ('n node -> unit) -> unit,
65          forall_edges    : ('e edge -> unit) -> unit
66       }
67
68   datatype ('n,'e,'g) graph = GRAPH of ('n,'e,'g) graph_methods
69
70
71   val unimplemented : 'a -> 'b
72
73         (* remove one edge i->j from graph *)
74   val remove_edge : ('n,'e,'g) graph -> node_id * node_id -> unit
75
76   val remove_edge' : ('n,'e,'g) graph -> node_id * node_id *
77                                            ('e -> bool) -> unit
78
79         (* remove all edges i->j from graph *)
80   val remove_all_edges : ('n,'e,'g) graph -> node_id * node_id -> unit
81
82   val remove_all_edges' : ('n,'e,'g) graph ->
83                node_id * node_id * ('e -> bool) -> unit
84end
85
86
Note: See TracBrowser for help on using the repository browser.