Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /MLRISC/trunk/graphs/graph.sml
ViewVC logotype

Annotation of /MLRISC/trunk/graphs/graph.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2126 - (view) (download)

1 : monnier 245 (*
2 : monnier 411 * A generic directed graph data structure.
3 :     * Implemented in an ``object oriented style''
4 :     * All graphs are based on this interface.
5 :     *
6 :     * -- Allen
7 : monnier 245 *)
8 :    
9 :     structure Graph : GRAPH =
10 :     struct
11 :    
12 :     exception Graph of string
13 :     exception Subgraph
14 :     exception NotFound
15 :     exception Unimplemented
16 :     exception Readonly
17 : monnier 411 exception NotSingleEntry
18 :     exception NotSingleExit
19 : monnier 245
20 :     fun unimplemented _ = raise Unimplemented
21 :    
22 :     type node_id = int
23 :     type 'n node = node_id * 'n
24 :     type 'e edge = node_id * node_id * 'e
25 :    
26 :     datatype ('n,'e,'g) graph = GRAPH of ('n,'e,'g) graph_methods
27 :     withtype ('n,'e,'g) graph_methods =
28 :     { name : string,
29 :     graph_info : 'g,
30 :    
31 :     (* inserting/removing nodes and edges *)
32 :     new_id : unit -> node_id,
33 :     add_node : 'n node -> unit,
34 :     add_edge : 'e edge -> unit,
35 :     remove_node : node_id -> unit,
36 :     set_out_edges : node_id * 'e edge list -> unit,
37 :     set_in_edges : node_id * 'e edge list -> unit,
38 :     set_entries : node_id list -> unit,
39 :     set_exits : node_id list -> unit,
40 :    
41 :     garbage_collect : unit -> unit,
42 :    
43 :     nodes : unit -> 'n node list,
44 :     edges : unit -> 'e edge list,
45 :     order : unit -> int,
46 :     size : unit -> int,
47 :     capacity : unit -> int,
48 :     succ : node_id -> node_id list,
49 :     pred : node_id -> node_id list,
50 :     out_edges : node_id -> 'e edge list,
51 :     in_edges : node_id -> 'e edge list,
52 :     has_edge : node_id * node_id -> bool,
53 :     has_node : node_id -> bool,
54 :     node_info : node_id -> 'n,
55 :     entries : unit -> node_id list,
56 :     exits : unit -> node_id list,
57 :     entry_edges : node_id -> 'e edge list,
58 :     exit_edges : node_id -> 'e edge list,
59 :    
60 :     forall_nodes : ('n node -> unit) -> unit,
61 :     forall_edges : ('e edge -> unit) -> unit
62 :     }
63 :    
64 :     fun remove_all_edges (GRAPH G) (i,j) =
65 :     #set_out_edges G (i,List.filter (fn (_,k,_) => k = j) (#out_edges G i))
66 :     fun remove_all_edges' (GRAPH G) (i,j,p) =
67 :     #set_out_edges G (i,List.filter (fn (_,k,e) => k = j andalso p e)
68 :     (#out_edges G i))
69 :     fun remove_edge (GRAPH G) (i,j) =
70 :     let fun filter [] = []
71 :     | filter((e as (_,k,_))::es) =
72 :     if j = k then es else e::filter es
73 :     in #set_out_edges G (i,filter(#out_edges G i)) end
74 :     fun remove_edge' (GRAPH G) (i,j,p) =
75 :     let fun filter [] = []
76 :     | filter((e as (_,k,e'))::es) =
77 :     if j = k andalso p e' then es else e::filter es
78 :     in #set_out_edges G (i,filter(#out_edges G i)) end
79 :    
80 :     end
81 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0