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 /sml/trunk/src/MLRISC/graphs/uniongraph.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/graphs/uniongraph.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 411 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/graphs/uniongraph.sml

1 : monnier 245 (*
2 : monnier 411 * The union of two graphs.
3 :     *
4 :     * -- Allen
5 : monnier 245 *)
6 :    
7 :     signature UNION_GRAPH_VIEW =
8 :     sig
9 :    
10 :     val union_view : ('g1 * 'g2 -> 'g3) ->
11 :     ('n,'e,'g1) Graph.graph * ('n,'e,'g2) Graph.graph ->
12 :     ('n,'e,'g3) Graph.graph
13 :    
14 :     end
15 :    
16 :     structure UnionGraphView : UNION_GRAPH_VIEW =
17 :     struct
18 :    
19 :     structure G = Graph
20 :     structure Sort = Sorting
21 :    
22 :     fun union_view f (G.GRAPH A, G.GRAPH B) =
23 :     let
24 :     fun merge_nodes ns =
25 :     Sort.sort_uniq (fn ((i,_),(j,_)) => Int.<(i,j))
26 :     (fn ((i,_),(j,_)) => i = j) ns
27 :     fun merge_node_ids ns =
28 :     Sort.sort_uniq (fn (i,j) => Int.<(i,j))
29 :     (fn (i,j) => i = j) ns
30 :     fun merge_edges es =
31 :     Sort.sort_uniq (fn ((i,j,_),(m,n,_)) => Int.<(i,m)
32 :     orelse i = m andalso j < n)
33 :     (fn ((i,j,_),(m,n,_)) => i = m andalso j = n) es
34 :     fun new_id () = Int.max(#capacity A (), #capacity B ())
35 :     fun add_node n = (#add_node A n; #add_node B n)
36 :     fun add_edge e = (#add_edge A e; #add_edge B e)
37 :     fun remove_node i = (#remove_node A i; #remove_node B i)
38 :     fun set_out_edges e = (#set_out_edges A e; #set_out_edges B e)
39 :     fun set_in_edges e = (#set_in_edges A e; #set_in_edges B e)
40 :     fun garbage_collect() = (#garbage_collect A (); #garbage_collect B ())
41 :     fun nodes() = merge_nodes (#nodes A() @ #nodes B())
42 :     fun edges() = merge_edges (#edges A() @ #edges B())
43 :     fun order() = length(nodes())
44 :     fun size() = length(edges())
45 :     fun capacity() = #capacity A() + #capacity B()
46 :     fun out_edges i = merge_edges(#out_edges A i @ #out_edges B i)
47 :     fun in_edges i = merge_edges(#in_edges A i @ #in_edges B i)
48 :     fun succ i = merge_node_ids(#succ A i @ #succ B i)
49 :     fun pred i = merge_node_ids(#pred A i @ #pred B i)
50 :     fun has_edge e = #has_edge A e orelse #has_edge B e
51 :     fun has_node n = #has_node A n orelse #has_node B n
52 :     fun node_info n = #node_info A n handle _ => #node_info B n
53 :     fun entries() = merge_node_ids(#entries A () @ #entries B ())
54 :     fun exits() = merge_node_ids(#exits A () @ #exits B ())
55 :     fun entry_edges i = merge_edges(#entry_edges A i @ #entry_edges B i)
56 :     fun exit_edges i = merge_edges(#exit_edges A i @ #exit_edges B i)
57 :     fun forall_nodes f = app f (nodes())
58 :     fun forall_edges f = app f (edges())
59 :     (*
60 :     fun fold_nodes f u = List.foldr f u (nodes())
61 :     fun fold_edges f u = List.foldr f u (edges())
62 :     *)
63 :     in
64 :     G.GRAPH
65 :     { name = #name A ^ "+" ^ #name B,
66 :     graph_info = f(#graph_info A, #graph_info B),
67 :     new_id = new_id,
68 :     add_node = add_node,
69 :     add_edge = add_edge,
70 :     remove_node = remove_node,
71 :     set_in_edges = set_in_edges,
72 :     set_out_edges = set_out_edges,
73 :     set_entries = G.unimplemented,
74 :     set_exits = G.unimplemented,
75 :     garbage_collect = garbage_collect,
76 :     nodes = nodes,
77 :     edges = edges,
78 :     order = order,
79 :     size = size,
80 :     capacity = capacity,
81 :     out_edges = out_edges,
82 :     in_edges = in_edges,
83 :     succ = pred,
84 :     pred = succ,
85 :     has_edge = has_edge,
86 :     has_node = has_node,
87 :     node_info = node_info,
88 :     entries = entries,
89 :     exits = exits,
90 :     entry_edges = entry_edges,
91 :     exit_edges = exit_edges,
92 :     forall_nodes = forall_nodes,
93 :     forall_edges = forall_edges
94 :     (*
95 :     fold_nodes = fold_nodes,
96 :     fold_edges = fold_edges
97 :     *)
98 :     }
99 :     end
100 :     end
101 :    

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