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/Doc/graphs.html
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/Doc/graphs.html

Parent Directory Parent Directory | Revision Log Revision Log


Revision 499 - (view) (download) (as text)

1 : monnier 409 <!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
2 :     <HTML>
3 :     <HEAD>
4 :     <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
5 :     <META NAME="GENERATOR" CONTENT="Mozilla/4.07 [en] (X11; I; Linux 2.2.7 i686) [Netscape]">
6 :     </HEAD>
7 :     <BODY bgcolor="#FFFFFF">
8 :    
9 :     <CENTER>
10 :     <H1>
11 :     <FONT COLOR="#aa0000">The Graph Library</FONT></H1></CENTER>
12 :    
13 :     <h2> Overview </h2>
14 :    
15 :     Graphs are the most fundamental data structure in the MLRISC system.
16 :     MLRISC now contains an extensive library for working with graphs.
17 :     <p>
18 :     All graphs in MLRISC
19 :     are modeled as edge- and node-labeled directed multi-graphs.
20 :     Briefly, this means that nodes and edges can carry user supplied data, and
21 :     multiple directed edges can be attached between any two nodes.
22 :     Self-loops are also allowed.
23 :    
24 :     <p>
25 :     A node is uniquely identified by its <tt>>node_id</tt>, which is
26 :     simply an integer. Node ids can be assigned externally
27 :     by the user, or else generated automatically by a graph. All graphs
28 :     keep track of all node ids that are currently used,
29 :     and the method <tt>new_id : unit -> node_id</tt> generates a new unused id.
30 :    
31 :     <p>
32 :     A node is modeled as a node id and node label pair, (i,l).
33 :     An edge is modeled as a triple <em>i -> j</em>, which contains
34 :     the <font color="#ff0000">source</font> and <font color="#ff0000">target</font> node ids <em>i</em> and <em>j</em>,
35 :     and the edge label <em>l</em>. These types are defined as follows:
36 :     <pre>
37 :     type 'n node = node_id * 'n
38 :     type 'e edge = node_id * node_id * 'e
39 :     </pre>
40 :    
41 :     <h3>The graph signature</h3>
42 :    
43 :     All graphs are accessed through an abstract interface
44 :     of the polymorphic type <tt>('n,'e,'g) graph</tt>.
45 :     Here, <tt>'n</tt> is the type of the node labels, <tt>'e</tt> is the type
46 :     of the edge labels, and <tt>'g</tt> is the type of any extra information
47 :     embedded in a graph. We call the latter <tt>graph info</tt>.
48 :    
49 :     Formally, a graph <em>G</em> is a quadruple <em>(V,L,E,I)</em>
50 :     where <em>V</em> is a set of node ids, <em>L : V \to \alpha</em> is a node labeling
51 :     function from vertices to node labels, <em>E</em> is a multi-set
52 :     of labeled-edges of type <em>V \times V \times \beta</em>, and <em>I: \gamma</em>
53 :     is the graph info.
54 :    
55 :     The interface of a graph is packaged into a
56 :     record of methods that manipulate the base representation:
57 :     <pre>
58 :     signature <a href="../graphs/graph.sig" target=code>GRAPH</a> = sig
59 :     type node_id = int
60 :     type 'n node = node_id * 'n
61 :     type 'e edge = node_id * node_id * 'e
62 :    
63 :     exception Graph of string
64 :     exception Subgraph
65 :     exception NotFound
66 :     exception Unimplemented
67 :     exception Readonly
68 :    
69 :     datatype ('n,'e,'g) graph = GRAPH of ('n,'e,'g) graph_methods
70 :     withtype ('n,'e,'g) graph_methods =
71 :     { name : string,
72 :     graph_info : 'g,
73 :     (* selectors *)
74 :     (* mutators *)
75 :     (* iterators *)
76 :     }
77 :     end
78 :     </pre>
79 :    
80 :     A few exceptions are predefined in this signature, which have
81 :     the following informal interpretation.
82 :     Exception <tt>Graph</tt> is raised when a bug is encountered.
83 :     The exception <tt>Subgraph</tt> is raised if certain semantics constraints
84 :     imposed on a graph are violated.
85 :     The exception <tt>NotFound</tt> is raised if lookup of a node id fails.
86 :     The exception <tt>Unimplemented</tt> is raised if a certain feature
87 :     is accessed but is undefined on the graph. The exception
88 :     <tt>Readonly</tt> is raised if the graph is readonly and an update operation
89 :     is attempted.
90 :    
91 :     <h3>Selectors</h3>
92 :    
93 :     Methods that access the structure of a graph are listed below:
94 :     <pre>
95 :     nodes : unit -> <em>\alpha</em> node list &
96 :     Return a list of all nodes in a graph \\
97 :     edges : unit -> <em>\beta</em> edge list &
98 :     Return a list of all edges in a graph \\
99 :     order : unit -> int &
100 :     Return the number of nodes in a graph. The graph is empty
101 :     if its order is zero \\
102 :     size : unit -> int &
103 :     Return the number of edges in a graph \\
104 :     capacity : unit -> int &
105 :     Return the maximum node id in the graph, plus 1.
106 :     This can be used as a new id \\
107 :     succ : node_id -> node_id list &
108 :     Given a node id <em>i</em>, return the node ids of all its successors,
109 :     i.e. <em>{ j | i \edge{l} j \in E}</em>. \\
110 :     pred : node_id -> node_id list &
111 :     Given a node id <em>j</em>, return the node ids of all its predecessors,
112 :     i.e. <em>{ i | i \edge{l} j \in E}</em>. \\
113 :     out_edges : node_id -> <em>\beta</em> edge list &
114 :     Given a node id <em>i</em>, return all the out-going edges from node <em>i</em>,
115 :     i.e. all edges whose source is <em>i</em>. \\
116 :     in_edges : node_id -> <em>\beta</em> edge list &
117 :     Given a node id <em>j</em>, return all the in-coming edges from node <em>j</em>,
118 :     i.e. all edges whose target is <em>j</em>. \\
119 :     has_edge : node_id * node_id -> bool &
120 :     Given two node ids <em>i</em> and <em>j</em>, find out if an edge
121 :     with source <em>i</em> and target <em>j</em> exists. \\
122 :     has_node : node_id -> bool &
123 :     Given a node id <em>i</em>, find out if a node of id <em>i</em> exists. \\
124 :     node_info : node_id -> <em>\alpha</em> &
125 :     Given a node id, return its node label. If the node does not
126 :     exist, raise exception <tt>NotFound</tt>. \\
127 :     </pre>
128 :    
129 :     <h3>Graph hierarchy</h3>
130 :    
131 :     A graph <em>G</em> may in fact be a subgraph of a <font color="#ff0000">base graph</font> <em>G'</em>, or
132 :     obtained from <em>G'</em> via some transformation <em>T</em>.
133 :     In such cases the following methods may be used to determine of the
134 :     relationship between <em>G</em> and <em>G'</em>.
135 :     An <font color="#ff0000">entry edge</font> is an edge
136 :     in <em>G'</em> that terminates at a node in <em>G</em>, but is not an edge in <em>G</em>.
137 :     Similarly, an <font color="#ff0000">exit edge</font> is an edge in <em>G'</em> that originates from
138 :     a node in <em>G</em>, but is not an edge in <em>G</em>. An <font color="#ff0000">entry node</font>
139 :     is a node in <em>G</em> that has an incoming entry edge. An \define{exit
140 :     node} is a node in <em>G</em> that has an out-going exit edge. If <em>G</em> is not
141 :     a subgraph, all these methods will return nil.
142 :     \begin{methods}
143 :     entries : unit -> node_id list &
144 :     Return the node ids of all the entry nodes. \\
145 :     exits : unit -> node_id list &
146 :     Return the node ids of all the exit nodes. \\
147 :     entry_edges : node_id -> <em>\beta</em> edge list &
148 :     Given a node id <em>i</em>, return all the entry edges whose sources are
149 :     <em>i</em>. \\
150 :     exit_edges : node_id -> <em>\beta</em> edge list &
151 :     Given a node id <em>i</em>, return all the exit edges whose targets are <em>i</em>.
152 :     \end{methods}
153 :    
154 :     \pagebreak
155 :     <h3>Mutators</h3>
156 :    
157 :     Methods to update a graph are listed below:
158 :     \begin{methods}
159 :     new_id : unit -> node_id &
160 :     Return a unique node id guaranteed to be
161 :     absent in the current graph. \\
162 :     add_node : <em>\alpha</em> node -> unit &
163 :     Insert node into the graph. If a node of the same node id
164 :     already exists, replace the old node with the new. \\
165 :     add_edge : <em>\beta</em> edge -> unit &
166 :     Insert an edge into the graph. \\
167 :     remove_node : node_id -> unit &
168 :     Given a node id <em>n</em>, remove the node with the node id from the graph.
169 :     This also automatically removes all edges with source or target <em>n</em>. \\
170 :     set_out_edges : node_id * <em>\beta</em> edge list -> unit &
171 :     Given a node id <em>n</em>, and a list of edges <em>e_1,\ldots,e_n</em>
172 :     with sources <em>n</em>, replace all out-edges of <em>n</em> by <em>e_1,\ldots,e_n</em>. \\
173 :     set_in_edges : node_id * <em>\beta</em> edge list -> unit &
174 :     Given a node id <em>n</em>, and a list of edges <em>e_1,\ldots,e_n</em>
175 :     with targets <em>n</em>, replace all in-edges of <em>n</em> by <em>e_1,\ldots,e_n</em>. \\
176 :     set_entries : node_id list -> unit &
177 :     Set the entry nodes of a graph. \\
178 :     set_exits : node_id list -> unit &
179 :     Set the exit nodes of a graph. \\
180 :     garbage_collect : unit -> unit &
181 :     Reclaim all node ids of nodes that have been removed by
182 :     <tt>remove_node}. Subsequent \sml{new_id</tt> will reuse these
183 :     node ids. \\
184 :     \end{methods}
185 :    
186 :     <h3>Iterators</h3>
187 :    
188 :     Two primitive iterators are supported in the graph interface.
189 :     Method <tt>forall_nodes</tt> iterates over all the nodes in a graph,
190 :     while method <tt>forall_edges</tt> iterates over all the edges.
191 :     Other more complex iterators can be found in other modules.
192 :     \begin{methods}
193 :     forall_nodes : (<em>\alpha</em> node -> unit) -> unit &
194 :     Given a function <em>f</em> on nodes, apply <em>f</em> on all the nodes in the graph. \\
195 :     forall_edges : (<em>\beta</em> edge -> unit) -> unit &
196 :     Given a function <em>f</em> on edges, apply <em>f</em> on all the edges in the graph.
197 :     \end{methods}
198 :    
199 :     <h3>Manipulating a graph</h3>
200 :    
201 :     Since operations on the graph type are packaged into
202 :     a record, an ``object oriented'' style of graph manipulation should be used.
203 :     For example, if <tt>G</tt> is a graph object, then we can obtain all the
204 :     nodes and edges of <tt>G</tt> as follows.
205 :     <pre>
206 :     val GRAPH g = G
207 :     val edges = #edges g ()
208 :     val nodes = #nodes g ()
209 :     </pre>
210 :     We can view <tt>#edges g} as sending the message to \sml{G</tt>.
211 :     While all this seems like mere syntactic deviation from the usual
212 :     signature/structure approach, there are two crucial differences which
213 :     we will exploit:
214 :     {\em (i)} records are first class objects
215 :     while structures are not (consequently
216 :     late binding of ``methods'' and cannot be easily simulated on the
217 :     structure level); {\em (ii)} recursion
218 :     is possible on the type level, while recursive structures are not available.
219 :     The extra flexibility of this choice becomes apparent with the
220 :     introduction of views later.
221 :    
222 :     <h3>Creating a Graph</h3>
223 :    
224 :     A graph implementation has the following signature
225 :     <pre>
226 :     signature <a href="../graphs/graphimpl.sig" target=code>GRAPH_IMPLEMENTATION</a> = sig
227 :     val graph : string * 'g * int -> ('n,'e,'g) graph
228 :     end
229 :     </pre>
230 :     The function <tt>graph</tt> takes a string (the name of the graph),
231 :     graph info, and a default size as arguments and create an empty graph.
232 :    
233 :     The functor <tt>DirectedGraphFn</tt>:
234 :     <pre>
235 :     functor DirectedGraphFn(A : ARRAY_SIG) : GRAPH_IMPLEMENTATION
236 :     </pre>
237 :     implements a graph using adjacency lists as internal representation.
238 :     It takes an array type as a parameter. For graphs with
239 :     node ids that are dense enumerations, the <tt>DynamicArray</tt> structure
240 :     should be used as the parameter to this functor.
241 :     The structure <tt>DirectedGraph</tt> is predefined as follows:
242 :     <pre>
243 :     structure <a href="../graphs/digraph.sml" target=code>DirectedGraph</a> = DirectedGraphFn(DynamicArray)
244 :     </pre>
245 :    
246 :     For node ids that are sparse enumerations, the structure <tt>HashArray</tt>,
247 :     which implements integer-keyed hash tables
248 :     with the signature of arrays, can be used
249 :     as argument to <tt>DirectedGraphFn</tt>.
250 :     For graphs with fixed sizes determined at creation time,
251 :     the structure <tt>Array</tt> can be used (see also
252 :     functor <a href="../library/undoable-array.sml" target=code>/tt UndoableArrayFn</a>,
253 :     which creates arrays with undoable updates, and transaction-like semantics.)
254 :    
255 :     <h3>Basic Graph Algorithms</h3>
256 :    
257 :     <h3>Depth-/Breath-First Search</h3>
258 :    
259 :     <pre>
260 :     val dfs : ('n,'e,'g) graph ->
261 :     (node_id -> unit) ->
262 :     ('e edge -> unit) ->
263 :     node_id list -> unit
264 :     </pre>
265 :     The function <tt>dfs</tt> takes as arguments a graph,
266 :     a function <tt>f : node_id -> unit</tt>, a function
267 :     <tt>g : 'e edge -> unit</tt>, and a
268 :     set of source vertices. It performs depth first search on the
269 :     graph. The function <tt>f</tt> is invoked
270 :     whenever a new node is being visited, while the function <tt>g</tt>
271 :     is invoked whenever a new edge is being traversed.
272 :     This algorithm has running time <em>O(|V|+|E|)</em>.
273 :    
274 :     <pre>
275 :     val dfsfold : ('n,'e,'g) graph ->
276 :     (node_id * 'a -> 'a) ->
277 :     ('e edge * 'b -> 'a) ->
278 :     node_id list -> 'a * 'b -> 'a * 'b
279 :     val dfsnum : ('n,'e,'g) graph ->
280 :     (node_id * 'a -> 'a) ->
281 :     { dfsnum : int array, compnum : int array }
282 :     </pre>
283 :    
284 :     The function <tt>bfs} is similar to \sml{dfs</tt>
285 :     except that breath first search is performed.
286 :     <pre>
287 :     val bfs : ('n,'e,'g) graph ->
288 :     (node_id -> unit) ->
289 :     ('e edge -> unit) ->
290 :     node_id list -> unit
291 :     val bfsdist : ('n,'e,'g) graph -> node_id list -> int array
292 :     </pre>
293 :    
294 :     <h3>Preorder/Postorder numbering</h3>
295 :     <pre>
296 :     val preorder_numbering : ('n,'e,'g) graph -> int -> int array
297 :     val postorder_numbering : ('n,'e,'g) graph -> int -> int array
298 :     </pre>
299 :     Both these functions take a tree <em>T</em> and a root <em>v</em>, and return
300 :     the preorder numbering and the postorder numbering of the tree respectively.
301 :    
302 :     <h3>Topological Sort</h3>
303 :     <pre>
304 :     val topsort : ('n,'e,'g) graph -> node_id list -> node_id list
305 :     </pre>
306 :     The function
307 :     <tt>topsort</tt> takes a graph <em>G</em> and a set of source vertices <em>S</em>
308 :     as arguments. It returns a topological sort of all the nodes reachable from
309 :     the set <em>S</em>.
310 :     This algorithm has running time <em>O(|S|+|V|+|E|)</em>.
311 :    
312 :     <h3>Strongly Connected Components</h3>
313 :     <pre>
314 :     val strong_components : ('n,'e,'g) graph ->
315 :     (node_id list * 'a -> 'a) -> 'a -> 'a
316 :     </pre>
317 :     The function <tt>strong_components</tt> takes a graph <em>G</em> and
318 :     an aggregate function <em>f</em> with type
319 :     <pre>
320 :     node_id list * 'a -> 'a
321 :     </pre>
322 :     \noindent and an identity element <tt>x : 'a</tt> as arguments.
323 :     Function <em>f</em> is invoked with a strongly connected component
324 :     (represented as a list of node ids) as each is discovered.
325 :     That is, the function <tt>strong_components</tt> computes
326 :     \[ f(SCC_n,f(SCC_{n-1},\ldots f(SCC_1,x))) \]
327 :     where <em>SCC_1,\ldots,SCC_n</em> are the strongly connected components
328 :     in topological order. This algorithm has running time <em>O(|V|+|E|)</em>.
329 :    
330 :     <h3>Biconnected Components</h3>
331 :     <pre>
332 :     val biconnected_components : ('n,'e,'g) graph ->
333 :     ('e edge list * 'a -> 'a) -> 'a -> 'a
334 :     </pre>
335 :     The function <tt>biconnected_components</tt> takes a graph <em>G</em> and
336 :     an aggregate function <em>f</em> with type
337 :     <pre>
338 :     'e edge list * 'a -> 'a
339 :     </pre>
340 :     \noindent and an identity element <tt>x : 'a</tt> as arguments.
341 :     Function <em>f</em> is invoked with a biconnected component
342 :     (represented as a list of edges) as each is discovered.
343 :     That is, the function <tt>biconnected_components</tt> computes
344 :     \[ f(BCC_n,f(BCC_{n-1},\ldots f(BCC_1,x))) \]
345 :     where <em>BCC_1,\ldots,BCC_n</em> are the biconnected components.
346 :     This algorithm has running time <em>O(|V|+|E|)</em>.
347 :    
348 :     <h3>Cyclic Test</h3>
349 :     <pre>
350 :     val is_cyclic : ('n,'e,'g) graph -> bool
351 :     </pre>
352 :     Function <tt>is_cyclic</tt> tests if a graph is cyclic.
353 :     This algorithm has running time <em>O(|V|+|E|)</em>.
354 :    
355 :     <h3>Enumerate Simple Cycles</h3>
356 :     <pre>
357 :     val cycles : ('n,'e,'g) graph -> ('e edge list * 'a -> 'a) -> 'a ->'a
358 :     </pre>
359 :     A simple cycle is a circuit that visits each vertex only once.
360 :     The function <tt>cycles</tt> enumerates all simple cycles in a graph <em>G</em>.
361 :     It takes as argument an aggregate function <em>f</em> of type
362 :     <pre>
363 :     'e edge list * 'a -> 'a
364 :     </pre>
365 :     and an identity element <em>e</em>, and computes as result the expression
366 :     \[ f(c_n,f(c_{n-1},f(c_{n-2},\ldots f(c_1,e)))) \]
367 :     where <em>c_1,\ldots,c_n</em> are all the simple cycles in the graph.
368 :     All cycles <em>c_1,\ldots,c_n</em> are guaranteed to be distinct.
369 :     A cycle is represented as a sequence of
370 :     adjacent edges, i.e. in the order of
371 :     \[ v_1 \to v_2, v_2 \to v_3, v_3 \to v_4, \ldots, v_{n-1} \to v_n,
372 :     v_n \to v_1 \]
373 :     Our implementation works by first decomposing the graph into
374 :     its strongly connected components, then uses backtracking to enumerate
375 :     simple cycles in each component.
376 :     <h3>Minimal Cost Spanning Tree</h3>
377 :     <pre>
378 :     signature MIN_COST_SPANNING_TREE = sig
379 :     exception Unconnected
380 :    
381 :     val spanning_tree : { weight : 'e edge -> 'a,
382 :     < : 'a * 'a -> bool
383 :     } -> ('n, 'e, 'g) graph
384 :     -> ('e edge * 'a -> 'a) -> 'a -> 'a
385 :     end
386 :     structure Kruskal : MIN_COST_SPANNING_TREE
387 :     </pre>
388 :    
389 :     Structure <tt>Kruskal</tt> implements Kruskal's algorithm for
390 :     computing a minimal cost spanning tree of a graph.
391 :     The function <tt>spanning_tree</tt> takes as arguments:
392 :     <ul>
393 :     <li> a <tt>weight</tt> function which when given an edge returns its weight
394 :     <li> an ordering function <tt><</tt>, which is used to compare the weights
395 :     <li> a graph <em>G</em>
396 :     <li> an accumulator function <em>f</em>, and
397 :     <li> an identity element <em>x</em>
398 :     </ul>
399 :     The function <tt>spanning_tree</tt> computes
400 :     \[ f(e_{n},f(e_{n-1},\ldots f(e_1,x))) \]
401 :     where <em>e_1,\ldots,e_n</em> are the edges in a minimal cost spanning tree
402 :     of the graph.
403 :     The exception <tt>Unconnected</tt> is raised if the graph is unconnected.
404 :    
405 :     <h3>Abelian Groups</h3>
406 :     Graph algorithms that deal with numeric weights or distances
407 :     are parameterized with respect to the signatures
408 :     <tt>ABELIAN_GROUP} or \sml{ABELIAN_GROUP_WITH_INF</tt>.
409 :     These are defined as follows:
410 :     <pre>
411 :     signature <a href="../graphs/groups.sig" target=code>ABELIAN_GROUP</a> = sig
412 :     type elem
413 :     val + : elem * elem -> elem
414 :     val - : elem * elem -> elem
415 :     val : elem -> elem
416 :     val zero : elem
417 :     val < : elem * elem -> bool
418 :     val == : elem * elem -> bool
419 :     end
420 :     signature <a href="../graphs/groups.sig" target=code>ABELIAN_GROUP_WITH_INF</a> = sig
421 :     include ABELIAN_GROUP
422 :     val inf : elem
423 :     end
424 :     </pre>
425 :     Signature <tt>ABELIAN_GROUP</tt> specifies an ordered commutative group,
426 :     while signature <tt>ABELIAN_GROUP_WITH_INF</tt> specifies an ordered commutative
427 :     group with an infinity element <tt>inf</tt> which satisfies
428 :     {\em(i)} <em>-\mbox{<tt>inf}} \le x \le \mbox{<tt>inf</tt>}</em> for all <em>x</em>, and {\em (ii)</tt>
429 :     <em>x + \mbox{<tt>inf}} = \mbox{<tt>inf</tt></tt></em> for all <em>x</em>.
430 :    
431 :     <h3>Single Source Shortest Paths</h3>
432 :     <pre>
433 :     signature <a href="../graphs/shortest-paths.sig" target=code>SINGLE_SOURCE_SHORTEST_PATHS</a> = sig
434 :     structure Num : ABELIAN_GROUP_WITH_INF
435 :     val single_source_shortest_paths :
436 :     { graph : ('n,'e,'g) graph,
437 :     weight : 'e edge -> Num.elem,
438 :     s : node_id
439 :     } ->
440 :     { dist : Num.elem array,
441 :     pred : node_id array
442 :     }
443 :     end
444 :     functor <a href="../graphs/dijkstra.sml" target=code>DijkstraFn</a>(Num : ABELIAN_GROUP_WITH_INF)
445 :     : SINGLE_SOURCE_SHORTEST_PATHS
446 :     </pre>
447 :     The functor <tt>DijkstraFn</tt> implements Dijkstra's algorithm
448 :     for single source shortest paths. The function \linebreak
449 :     <tt>single_source_shortest_paths</tt> takes as arguments:
450 :     <ul>
451 :     <li> a graph <em>G</em>,
452 :     <li> a <tt>weight</tt> function on edges, and
453 :     <li> the source vertex <em>s</em>.
454 :     </ul>
455 :     It returns two arrays <tt>dist</tt> and <tt>pred</tt>
456 :     indexed by vertices. These arrays have the following
457 :     interpretation. Given a vertex <em>v</em>,
458 :     <ul>
459 :     <li> <tt>dist</tt>[<em>v</em>] contains the distance of <em>v</em> from the source <em>s</em>
460 :     <li> <tt>pred</tt>[<em>v</em>] contains the predecessor of <em>v</em> in the shortest
461 :     path from <em>s</em> to <em>v</em>, or <em>-1</em> if <em>v=s</em>.
462 :     </ul>
463 :    
464 :     Dijkstra's algorithm fails to work on graphs that have
465 :     negative edge weights.
466 :     To handle negative weights, Bellman-Ford's algorithm can be used.
467 :     The exception <tt>NegativeCycle</tt> is raised if a cycle of
468 :     negative total weight is detected.
469 :     <pre>
470 :     functor <a href="../graphs/bellman-ford.sml" target=code>BellmanFordFn</a>(Num : ABELIAN_GROUP_WITH_INF) : sig
471 :     include SINGLE_SOURCE_SHORTEST_PATHS
472 :     exception NegativeCycle
473 :     end
474 :     </pre>
475 :     <h3>All Pairs Shortest Paths</h3>
476 :     <pre>
477 :     signature <a href="../graphs/shortest-paths.sig" target=code>ALL_PAIRS_SHORTEST_PATHS</a> = sig
478 :     structure Num : ABELIAN_GROUP_WITH_INF
479 :     val all_pairs_shortest_paths :
480 :     { graph : ('n,'e,'g) graph,
481 :     weight : 'e edge -> Num.elem
482 :     } ->
483 :     { dist : Num.elem Array2.array,
484 :     pred : node_id Array2.array
485 :     }
486 :     end
487 :     functor <a href="../graphs/floyd-warshall.sml" target=code>FloydWarshallFn</a>(Num : ABELIAN_GROUP_WITH_INF)
488 :     : ALL_PAIRS_SHORTEST_PATHS
489 :     </pre>
490 :     The functor <tt>FloydWarshallFn</tt> implements Floyd-Warshall's algorithm
491 :     for all pairs shortest paths. The function
492 :     <tt>all_pairs_shortest_paths</tt> takes as arguments:
493 :     <ul>
494 :     <li a graph <em>G</em>, and
495 :     <li> a <tt>weight</tt> function on edges
496 :     </ul>
497 :     It returns two 2-dimensional arrays <tt>dist} and \sml{pred</tt>
498 :     indexed by vertices <em>(u,v)</em>. These arrays have the following
499 :     interpretation. Given a pair <em>(u,v)</em>,
500 :     <ul>
501 :     <li> <tt>dist</tt>[<em>u,v</em>] contains the distance from <em>u</em> to <em>v</em>.
502 :     <li. <tt>pred</tt>[<em>u,v</em>] contains the predecessor of <em>v</em> in the shortest
503 :     path from <em>u</em> to <em>v</em>, or <em>-1</em> if <em>u=v</em>.
504 :     </ul>
505 :     This algorithm runs in time <em>O(|V|^3+|E|)</em>.
506 :    
507 :     An alternative implementation is available that uses Johnson's algorithm,
508 :     which works better for sparse graphs:
509 :     <pre>
510 :     functor <a href="../graphs/johnson.sml" target=code>JohnsonFn</a>(Num : ABELIAN_GROUP_WITH_INF)
511 :     : sig include ALL_PAIRS_SHORTEST_PATHS
512 :     exception Negative Cycle
513 :     end
514 :     </pre>
515 :    
516 :     <h3>Transitive Closure</h3>
517 :     <pre>
518 :     signature <a href="../graphs/trans-closure.sml" target=code>TRANSITIVE_CLOSURE</a> = sig
519 :     val acyclic_transitive_closure : { + : ('e * 'e -> 'e), simple : bool }
520 :     -> ('n,'e,'g) graph -> unit
521 :     val acyclic_transitive_closure2 :
522 :     { + : 'e * 'e -> 'e,
523 :     max : 'e * 'e -> 'e
524 :     } -> ('n,'e,'g) graph -> unit
525 :     val transitive_closure : ('e * 'e -> 'e) -> ('n,'e,'g) graph -> unit
526 :     structure <a href="../graphs/trans-closure.sml" target=code>TransitiveClosure</a> : TRANSITIVE_CLOSURE
527 :     </pre>
528 :     Structure <tt>TransitiveClosure</tt> implements
529 :     in-place transitive closures on graphs. Three functions are implemented.
530 :     Functions <tt>acyclic_transitive_closure</tt> and
531 :     <tt>acyclic_transitive_closure2</tt> can be used
532 :     to compute the transitive closure of an acyclic graph, whereas the
533 :     function <tt>transitive_closure</tt> computes the transitive closure of
534 :     a cyclic graph. All take a binary function
535 :     <pre>
536 :     + : 'e * 'e -> 'e
537 :     </pre>
538 :     defined on edge labels.
539 :     Transitive edges are inserted in the following manner:
540 :    
541 :     <ul>
542 :     <li> <tt>acyclic_transitive_closure</tt>:
543 :     given <em>u \edge{l} v</em> and <em>v \edge{l'} w</em>,
544 :     if the flag <tt>simple</tt> is false or if
545 :     the transitive edge <em>u \edge{} w</em> does not exists,
546 :     then <em>u \edge{l + l'} w</em> is added to the graph.
547 :     <li> <tt>acyclic_transitive_closure2</tt>:
548 :     given <em>u \edge{l} v</em> and <em>v \edge{l'} w</em>,
549 :     the transitive <em>u \edge{l + l'} w</em> is added to the graph.
550 :     Furthermore, all parallel edges
551 :     \[ u \edge{l_1} w, \ldots, u \edge{l_n} w \]
552 :     are coalesced into a single edge <em>u \edge{l} w</em>, where
553 :     <em>l = {/tt max}_{i = 1\ldots n} l_i</em>
554 :     </ul>
555 :    
556 :     <h3>Max Flow</h3>
557 :    
558 :     The function <tt>max_flow</tt> computes the
559 :     maximum flow between the source vertex <tt>s</tt> and the sink vertex
560 :     <tt>t} in the <tt>graph</tt> when given a \sml{capacity</tt> function.
561 :     <pre>
562 :     signature <a href="../graphs/max-flow.sig" target=code>MAX_FLOW</a> = sig
563 :     structure Num : ABELIAN_GROUP
564 :     val max_flow : { graph : ('n,'e,'g) graph,
565 :     s : node_id,
566 :     t : node_id,
567 :     capacity : 'e edge -> Num.elem,
568 :     flows : 'e edge * Num.elem -> unit
569 :     } -> Num.elem
570 :     end
571 :     functor <a href="../graphs/max-flow.sml" target=code>MaxFlowFn</a>(Num : ABELIAN_GROUP) : MAX_FLOW
572 :     </pre>
573 :     The function <tt>max_flow</tt> returns its result in the follow manner:
574 :     The function returns the total flow as its result value.
575 :     Furthermore, the function <tt>flows</tt> is called once for each edge <em>e</em> in the
576 :     graph with its associated flow <em>f_e</em>.
577 :    
578 :     This algorithm uses Goldberg's preflow-push approach, and runs
579 :     in <em>O(|V|^2|E|)</em> time.
580 :     <h3>Min Cut</h3>
581 :     The function <tt>min_cut</tt> computes the
582 :     minimum (undirected) cut in a <tt>graph} when given a \sml{weight</tt> function on
583 :     its edges.
584 :     <pre>
585 :     signature <a href="../graphs/min-cut.sig" target=code>MIN_CUT</a> = sig
586 :     structure Num : ABELIAN_GROUP
587 :     val min_cut : { graph : ('n,'e,'g) graph,
588 :     weight : 'e edge -> Num.elem
589 :     } -> node_id list * Num.elem
590 :     end
591 :     functor <a href="../graphs/min-cut.sml" target=code>MinCutFn</a>(Num : ABELIAN_GROUP) : MIN_CUT
592 :     </pre>
593 :     The function <tt>min_cut</tt> returns a list of node ids denoting
594 :     one side of the cut <em>C</em> (the other side of the cut is <em>V - C</em>) and
595 :     the weight cut.
596 :    
597 :     <h3>Max Cardinality Matching</h3>
598 :    
599 :     <pre>
600 :     val matching : ('n,'e,'g) graph -> ('e edge * 'a -> 'a) -> 'a -> 'a * int
601 :     </pre>
602 :    
603 :     The function <tt>BipartiteMatching.matching</tt> computes the
604 :     maximal cardinality matching of a bipartite graph. As result,
605 :     the function iterates over all the matched edges and returns the
606 :     number of matched edges. The algorithm runs in time <em>O(|V||E|)</em>.
607 :    
608 :     <h3>Node Partition</h3>
609 :     <pre>
610 :     signature NODE_PARTITION = sig
611 :     type 'n node_partition
612 :    
613 :     val node_partition : ('n,'e,'g) graph -> 'n node_partition
614 :     val !! : 'n node_partition -> node_id -> 'n node
615 :     val == : 'n node_partition -> node_id * node_id -> bool
616 :     val union : 'n node_partition -> ('n node * 'n node -> 'n node) ->
617 :     node_id * node_id -> bool
618 :     val union': 'n node_partition -> node_id * node_id -> bool
619 :    
620 :     end
621 :     </pre>
622 :    
623 :     <h3>Node Priority Queue</h3>
624 :     <pre>
625 :     signature NODE_PRIORITY_QUEUE = sig
626 :     type node_priority_queue
627 :    
628 :     exception EmptyPriorityQueue
629 :    
630 :     val create : (node_id * node_id -> bool) -> node_priority_queue
631 :     val fromGraph : (node_id * node_id -> bool) ->
632 :     ('n,'e,'g) graph -> node_priority_queue
633 :     val isEmpty : node_priority_queue -> bool
634 :     val clear : node_priority_queue -> unit
635 :     val min : node_priority_queue -> node_id
636 :     val deleteMin : node_priority_queue -> node_id
637 :     val decreaseWeight : node_priority_queue * node_id -> unit
638 :     val insert : node_priority_queue * node_id -> unit
639 :     val toList : node_priority_queue -> node_id list
640 :     end
641 :     </pre>
642 :    
643 :     <h2>Views}\label{sec:views</h2>
644 :     Simply put, a view is an alternative presentation
645 :     of a data structure to a client. A graph, such as the control flow
646 :     graph, frequently has to be presented in different ways in a compiler.
647 :     For example, when global scheduling is applied on a region
648 :     (a subgraph of the CFG),
649 :     we want to be able to concentrate on just the region and ignore all
650 :     nodes and edges that are not part of the current focus.
651 :     All transformations that are applied on the current region view should be
652 :     automatically reflected back to the entire CFG as a whole.
653 :     Furthermore, we want to be able to freely intermix
654 :     graphs and subgraphs of the same type in our program, without having
655 :     to introducing sums in our type representations.
656 :    
657 :     The <tt>subgraph_view} view combinator accomplishes this. \sml{Subgraph</tt>
658 :     takes a list of nodes and produces a graph object which is a view of the
659 :     node induced subgraph of the original graph.
660 :     All modification to the subgraph are automatically
661 :     reflected back to the original graph. From the client point of view,
662 :     a graph and a subgraph are entirely indistinguishable, and furthermore,
663 :     graphs and subgraphs can be freely mixed together (they are the same
664 :     type from ML's point of view.)
665 :    
666 :     This transparency is obtained by selective method overriding, composition,
667 :     and delegation. For example, a generic graph object provides the
668 :     following methods for setting and looking up the entries and exits
669 :     from a graph.
670 :     <pre>
671 :     set_entries : node_id list -> unit
672 :     set_exits : node_id list -> unit
673 :     entries : unit -> node_id list
674 :     exits : unit -> node_id list
675 :     </pre>
676 :    
677 :     For example, a CFG usually has a single entry and a single exit.
678 :     These methods allow the client to destinate one node as the
679 :     entry and another as
680 :     the exit. In the case of subgraph view, these methods are overridden so
681 :     that the proper conventions are preserved:
682 :     a node in a subgraph is an entry (exit) iff there is an in-edge (out-edge)
683 :     from (to) outside the (sub-)graph.
684 :     Similarly, the methods <tt>entry_edges} and \sml{exit_edges</tt> can be used
685 :     return the entry and exit edges associated with a node in a subgraph.
686 :     <pre>
687 :     entry_edges : node_id -> 'e edge list
688 :     exit_edges : node_id -> 'e edge list
689 :     </pre>
690 :     These methods are initially defined to return <tt>[]</tt> in a graph and
691 :     subsequently overridden in a subgraph.
692 :    
693 :     <h3> Update Transparency </h3>
694 :    
695 :     Suppose a view <em>G'</em> is created from some base graphs or views.
696 :     <font color="#ff0000">Update transparency</font> refers to the fact that <em>G'</em> behaves
697 :     consistently according to its conventions and semantics when updates
698 :     are performed. There are 4 different type of update transparencies:
699 :     <ul>
700 :     <li><font color="#ff0000">update opaque</font> A update opaque view disallows updates to both
701 :     itself and its base graphs.
702 :     <li><font color="#ff0000">globally update transparent</font> A globally update transparent
703 :     view allows updates to its base graphs but not to itself. Changes
704 :     will then be automatically reflected in the view.
705 :     <li><font color="#ff0000">locally update transparent</font> A locally update transparent
706 :     view allows updates to itself but not to its base graphs.
707 :     Changes will be automatically reflected to the base graphs.
708 :     <li><font color="#ff0000">fully update transparent</font> A fully update transparent
709 :     view allows updates through its methods or through its base
710 :     graphs'.
711 :     </ul>
712 :    
713 :     <h3>Structural Views}\label{sec:structural-views</h3>
714 :    
715 :     <h3>Reversal</h3>
716 :     <pre>
717 :     <a href="../graphs/revgraph.sml" target=code>ReversedGraphView.rev_view</a> : ('n,'e,'g) graph -> ('n,'e,'g) graph
718 :     </pre>
719 :     This combinator takes a graph <em>G</em> and produces a view <em>G^R</em>
720 :     which reverses the direction
721 :     of all its edges, including entry and exit edges. Thus
722 :     the edge <em>i \edge{l} j</em> in <em>G</em> becomes the edge
723 :     <em>j \edge{l} i</em> in <em>G^R</em>. This view is fully update transparent.
724 :    
725 :     <h3>Readonly</h3>
726 :     <pre>
727 :     <a href="../graphs/readonly.sml" target=code>ReadOnlyGraphView.readonly_view</a> : ('n,'e,'g) graph -> ('n,'e,'g) graph
728 :     </pre>
729 :     This function takes a graph <em>G</em> and produces a view <em>G'</em>
730 :     in which no mutator methods can be used. Invoking a mutator
731 :     method raises the exception <tt>Readonly</tt>.
732 :     This view is globally update transparent.
733 :    
734 :     <h3>Snapshot</h3>
735 :     <pre>
736 :     functor <a href="../graphs/snap-shot.sml" target=code>GraphSnapShotFn</a>(GI : GRAPH_IMPLEMENTATION) : GRAPH_SNAPSHOT
737 :     signature GRAPH_SNAPSHOT = sig
738 :     val snapshot : ('n,'e,'g) graph ->
739 :     { picture : ('n,'e,'g) graph, button : unit -> unit }
740 :     end
741 :     </pre>
742 :    
743 :     The function <tt>snapshot</tt> can be used to keep a cached copy
744 :     of a view a.k.a the <tt>picture</tt>. This cached copy
745 :     can be updated locally but the modification will not be reflected back
746 :     to the base graph. The function <tt>button</tt> can be used to
747 :     keep the view and the base graph up-to-date.
748 :    
749 :     <h3>Map</h3>
750 :     <pre>
751 :     <a href="../graphs/isograph.sml" target=code>IsomorphicGraphView.map</a> :
752 :     ('n node -> \(\alpha'\)) -> ('e edge -> \(\beta'\)) -> ('g -> \(\gamma'\)) ->
753 :     ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph
754 :     </pre>
755 :     The function <tt>map} is a generalization of the \sml{map</tt>
756 :     function on lists. It takes three functions
757 :     <tt>\(f\) : 'n node -> \(\alpha'\)}, \sml{\(g\) : 'e edge -> \(\beta'\)</tt>,
758 :     <tt>\(h\) : 'g -> \(\gamma\)'</tt> and a graph <em>G=(V,L,E,I)</em> as arguments.
759 :     It computes the view <em>G'=(V,L',E',I')</em> where
760 :     \begin{eqnarray*}
761 :     L'(v) & = & f(v,L(v)) \mbox{\ for all <em>v \in V</em>} \\
762 :     E' & = & { i \edge{g(i,j,l)} j | i \edge{l} j \in E } \\
763 :     I' & = & h(I)
764 :     \end{eqnarray*}
765 :    
766 :     <h3>Singleton</h3>
767 :     <pre>
768 :     <a href="../graphs/singleton.sml" target=code>SingletonGraphView.singleton_view</a> : ('n,'e,'g) graph -> node_id -> ('n,'e,'g) graph
769 :     </pre>
770 :     Function <tt>singleton_view</tt>
771 :     takes a graph <em>G</em> and a node id <em>v</em> (which must exists in <em>G</em>)
772 :     and return an edge-free graph with only one node (<em>v</em>).
773 :     This view is opaque.
774 :    
775 :     <h3>Node id renaming</h3>
776 :     <pre>
777 :     <a href="../graphs/renamegraph.sml" target=code>RenamedGraphView.rename_view</a> : int -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph
778 :     </pre>
779 :     The function <tt>rename_view</tt> takes an integer <em>n</em> and
780 :     a graph <em>G</em> and create a fully update transparent
781 :     view where all node ids are incremented by <em>n</em>. Formally,
782 :     given graph <em>G=(V,E,L,I)</em> it computes the view <em>G'=(V',E',L',I)</em>
783 :     where
784 :     \begin{eqnarray*}
785 :     V' & = & { v + n | v \in V } \\
786 :     E' & = & { i+n \edge{l} j+n | i \edge{l} j \in E } \\
787 :     L' & = & \lambda v. L(v-n)
788 :     \end{eqnarray*}
789 :    
790 :     <h3>Union and Sum</h3>
791 :     <pre>
792 :     <a href="../graphs/uniongraph.sml" target=code>UnionGraphView.union_view</a> : ('g * \(\gamma'\)) -> \(\gamma''\)) ->
793 :     ('n,'e,'g) graph * (\(\alpha,\beta,\gamma'\)) graph -> (\(\alpha',\beta',\gamma''\)) graph
794 :     GraphCombinations.unions : ('n,'e,'g) graph list -> (\(\alpha',\beta',\gamma\)) graph
795 :     GraphCombinations.sum : ('n,'e,'g) graph * ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma\)) graph
796 :     GraphCombinations.sums : ('n,'e,'g) graph list -> (\(\alpha',\beta',\gamma\)) graph
797 :     </pre>
798 :    
799 :     Function <tt>union_view</tt> takes as arguments
800 :     a function <em>f</em>, and two graphs
801 :     <em>G=(V,L,E,I)</em> and <em>G'=(V',L',E',I')</em>, it computes the union <em>G+G'</em> of
802 :     these graphs. Formally, <em>G \union G'=(V'',L'',E'',I'')</em> where
803 :     \begin{eqnarray*}
804 :     V'' & = & V \union V' \\
805 :     L'' & = & L \overrides L' \\
806 :     E'' & = & E \union E' \\
807 :     I'' & = & f(I,I')
808 :     \end{eqnarray*}
809 :    
810 :     The function <tt>sum} constructs a \define{disjoint sum</tt> of two
811 :     graphs.
812 :     <h3>Simple Graph View</h3>
813 :     <pre>
814 :     <a href="../graphs/simple-graph.sml" target=code>SimpleGraph.simple_graph</a> : (node_id * node_id * 'e list -> 'e) ->
815 :     ('n,'e,'g) graph -> ('n,'e,'g) graph
816 :     </pre>
817 :     Function <tt>simple_graph</tt> takes a merge function <em>f</em>
818 :     and a multi-graph <em>G</em> as arguments and return a view in which
819 :     all parallel multi-edges (edges with the same source and target) are combined
820 :     into a single edge: i.e. any collection of multi-edges between
821 :     the same source <em>s</em> and target <em>t</em> and with labels <em>l_1,\ldots,l_n</em>,
822 :     are replaced by the edge <em>s \edge{l_{st}} t</em> in the view, where
823 :     <em>l_{st} = f(s,t,[l_1,\ldots,l_n])</em>. The function <em>f</em> is assumed
824 :     to satisfy the equality <em>l = f(s,t,[l])</em> for all <em>l</em>, <em>s</em> and <em>t</em>.
825 :    
826 :     <h3>No Entry or No Exit</h3>
827 :     <pre>
828 :     <a href="../graphs/no-exit.sml" target=code>NoEntryView.no_entry_view</a> : ('n,'e,'g) graph -> ('n,'e,'g) graph
829 :     NoEntryView.no_exit_view : ('n,'e,'g) graph -> ('n,'e,'g) graph
830 :     </pre>
831 :    
832 :     The function <tt>no_entry_view</tt> creates a view in which
833 :     all entry edges (and thus entry nodes) are removed. The function
834 :     <tt>no_exit_view</tt> is the dual of this and creates a view in which
835 :     all exit edges are removed. This view is fully update transparent.
836 :     It is possible to remove all entry and exit edges by composing these
837 :     two functions.
838 :    
839 :     <h3>Subgraphs</h3>
840 :     <pre>
841 :     <a href="../graphs/subgraph.sml" target=code>SubgraphView.subgraph_view</a> : node_id list -> ('e edge -> bool) ->
842 :     ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph
843 :     </pre>
844 :    
845 :     The function <tt>subgraph_view</tt> takes as arguments a set of node ids
846 :     <em>S</em>, an edge predicate <em>p</em> and a graph <em>G=(V,L,E,I)</em>. It
847 :     returns a view in which only the visible nodes are <em>S</em> and
848 :     the only visible edges <em>e</em> are those that satisfy <em>p(e)</em> and
849 :     with sources and targets in <em>S</em>. <em>S</em> must be a subset of <em>V</em>.
850 :    
851 :     <pre>
852 :     <a href="../graphs/subgraph-p.sml" target=code>Subgraph_P_View.subgraph_p_view</a> : node_id list ->
853 :     (node_id -> bool) -> (node_id * node_id -> bool) ->
854 :     ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph
855 :     </pre>
856 :    
857 :     The function <tt>subgraph_view</tt> takes as arguments a set of node ids
858 :     <em>S</em>, a node predicate <em>p</em>, an edge predicate <em>q</em> and a graph <em>G=(V,L,E,I)</em>. It
859 :     returns a view in which only the visible nodes <em>v</em> are those
860 :     in <em>S</em> satisfying <em>p(v)</em>, and
861 :     the only visible edges <em>e</em> are those that satisfy <em>q(e)</em> and
862 :     with sources and targets in <em>S</em>. <em>S</em> must be a subset of <em>V</em>.
863 :    
864 :     <h3>Trace</h3>
865 :     <pre>
866 :     <a href="../graphs/trace-graph.sml" target=code>TraceView.trace_view</a> : node_id list -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph
867 :     </pre>
868 :    
869 :     \begin{wrapfigure}{r}{3in}
870 :     \begin{Boxit}
871 :     \psfig{figure=trace.eps,width=2.8in}
872 :     \end{Boxit}
873 :     \caption{\label{fig:trace-view} A trace view}
874 :     \end{wrapfigure}
875 :     A <font color="#ff0000">trace</font> is an acyclic path in a graph.
876 :     The function <tt>trace_view</tt> takes a trace of node ids
877 :     <em>v_1,\ldots,v_n</em> and a graph <em>G</em> and
878 :     returns a view in which only the nodes are visible.
879 :     Only the edges that connected two adjacent nodes on the trace, i.e.
880 :     <em>v_i \to v_{i+1}</em> for some <em>i = 1 \ldots n-1</em> are considered be within
881 :     the view. Thus if there is an edge <em>v_i \to v_j</em> in <em>G</em> where
882 :     <em>j \ne i+1</em> this edge is not considered to be within the view --- it
883 :     is considered to be an exit edge from <em>v_i</em> and an entry edge
884 :     from <em>v_j</em> however. Trace views can be used to construct a CFG region
885 :     suitable for trace scheduling \cite{trace-scheduling,bulldog}.
886 :    
887 :     Figure \ref{fig:trace-view} illustrates this concept graphically.
888 :     Here, the trace view is formed from the
889 :     nodes <tt>A, C, D, F} and \sml{G</tt>. The
890 :     solid edges linking the trace is visible within the view. All other
891 :     dotted edges are considered to be either entry of exit edges into
892 :     the trace. The edge from node <tt>G} to \sml{A</tt> is considered to
893 :     be both since it exits from <tt>G} and enters into \sml{A</tt>.
894 :    
895 :     <h3>Acyclic Subgraph</h3>
896 :     <pre>
897 :     <a href="../graphs/acyclic-graph.sml" target=code>AcyclicSubgraphView.acyclic_view</a> :
898 :     node_id list ->
899 :     ('n,'e,'g) graph -> ('n,'e,'g) graph
900 :     </pre>
901 :     \begin{wrapfigure}{r}{3in}
902 :     \begin{Boxit}
903 :     \psfig{figure=subgraph.eps,width=2.8in}
904 :     \end{Boxit}
905 :     \caption{\label{fig:acyclic-subgraph-view} An acyclic subgraph}
906 :     \end{wrapfigure}
907 :     The function <tt>acyclic_view</tt> takes an ordered
908 :     list of node ids <em>v_1,\ldots,v_n</em> and a graph <em>G</em> as arguments
909 :     and return a view <em>G'</em> such that only the nodes <em>v_1,\ldots,v_n</em>
910 :     are visible. In addition, only the edges with directions consistent
911 :     with the order list are considered to be within the view.
912 :     Thus an edge <em>v_i \to v_j</em> from <em>G</em> is in <em>G'</em> iff <em>1 \le i < j \le n</em>.
913 :     Acyclic views can be used to construct a CFG region suitable
914 :     for DAG scheduling.
915 :     Figure \ref{fig:acyclic-subgraph-view} illustrates this concept graphically.
916 :    
917 :     <h3>Start and Stop</h3>
918 :     <pre>
919 :     <a href="../graphs/start-stop.sml" target=code>StartStopView.start_stop_view</a> :
920 :     { start : 'n node,
921 :     stop : 'n node,
922 :     edges : 'e edge list
923 :     } -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph
924 :     </pre>
925 :    
926 :     The function <tt>start_stop_view</tt>
927 :    
928 :     <h3>Single-Entry/Multiple-Exits</h3>
929 :     <pre>
930 :     <a href="../graphs/SEME.sml" target=code>SingleEntryMultipleExit.SEME</a>
931 :     exit : 'n node -> ('n,'e,'g) graph -> ('n,'e,'g) graph
932 :     </pre>
933 :    
934 :     The function <tt>SEME</tt> converts a single-entry/multiple-exits
935 :     graph <em>G</em> into a single entry/single exit graph.
936 :     It takes an exit node <em>e</em> and a graph <em>G</em> and returns
937 :     a view <em>G'</em>. Suppose <em>i \edge{l} j</em> be an exit edge in <em>G</em>.
938 :     In view <em>G</em> this edge is replaced by a new normal edge <em>i \edge{l} e</em>
939 :     and a new exit edge <em>e \edge{l} j</em>. Thus <em>e</em> becomes the sole exit
940 :     node in the new view.
941 :    
942 :     <h3>Behavioral Views</h3>
943 :    
944 :     <h3>Behavioral Primitives</h3>
945 :    
946 :     Figure \ref{fig:behavioral-view-primitives} lists
947 :     the set of behavioral primitives defined
948 :     in structure <a href="../graphs/wrappers.sml" target=code>/tt GraphWrappers</a>.
949 :     These functions allow the user
950 :     to attach an action <em>a</em> to a mutator method <em>m</em> such that whenever <em>m</em>
951 :     is invoked so does <em>a</em>. Given a graph <em>G</em>, the combinator
952 :     <pre>
953 :     do_before_\(xxx\) : f -> ('n,'e,'g) graph -> ('n,'e,'g) graph
954 :     </pre>
955 :     \noindent returns a view <em>G'</em> such that whenever method <em>xxx</em> is invoked
956 :     in <em>G'</em>, the function <em>f</em> is called.
957 :     Similarly, the combinator
958 :     <pre>
959 :     do_after_\(xxx\) : f -> ('n,'e,'g) graph -> ('n,'e,'g) graph
960 :     </pre>
961 :     \noindent creates a new view <em>G''</em> such that the function <em>f</em>
962 :     is called after the method is invoked.
963 :     \begin{Figure}
964 :     \begin{boxit}
965 :     \small
966 :     <pre>
967 :     do_before_new_id : (unit -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
968 :     do_after_new_id : (node_id -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
969 :     do_before_add_node : ('n node -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
970 :     do_after_add_node : ('n node -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
971 :     do_before_add_edge : ('e edge -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
972 :     do_after_add_edge : ('e edge -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
973 :     do_before_remove_node : (node_id -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
974 :     do_after_remove_node : (node_id -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
975 :     do_before_set_in_edges : (node_id * 'e edge list -> unit) ->
976 :     ('n,'e,'g) graph -> ('n,'e,'g) graph
977 :     do_after_set_in_edges : (node_id * 'e edge list -> unit) ->
978 :     ('n,'e,'g) graph -> ('n,'e,'g) graph
979 :     do_before_set_out_edges : (node_id * 'e edge list -> unit) ->
980 :     ('n,'e,'g) graph -> ('n,'e,'g) graph
981 :     do_after_set_out_edges : (node_id * 'e edge list -> unit) ->
982 :     ('n,'e,'g) graph -> ('n,'e,'g) graph
983 :     do_before_set_entries : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
984 :     do_after_set_entries : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
985 :     do_before_set_exits : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
986 :     do_after_set_exits : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
987 :     </pre>
988 :     \end{boxit}
989 :     \caption{\label{fig:behavioral-view-primitives} Behavioral view primitives}
990 :     \end{Figure}
991 :    
992 :     Frequently it is not necessary to know precisely by which method a graph's
993 :     structure has been modified, only that it is. The following two methods
994 :     take a notification function <em>f</em> and returns a new view. <em>f</em> is
995 :     invoked before a modification is attempted in a view created
996 :     by <tt>do_before_changed</tt>. It is invoked after the modification in
997 :     a view created by <tt>do_after_changed</tt>.
998 :     <pre>
999 :     do_before_changed : (('n,'e,'g) graph -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
1000 :     do_after_changed : (('n,'e,'g) graph -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
1001 :     </pre>
1002 :    
1003 :     Behavioral views created by the above functions are all fully update
1004 :     transparent.
1005 :     <HR>
1006 :    
1007 :     </BODY>
1008 :     </HTML>

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