All graphs in MLRISC are modeled as edge- and node-labeled directed multi-graphs. Briefly, this means that nodes and edges can carry user supplied data, and multiple directed edges can be attached between any two nodes. Self-loops are also allowed.
A node is uniquely identified by its >node_id, which is simply an integer. Node ids can be assigned externally by the user, or else generated automatically by a graph. All graphs keep track of all node ids that are currently used, and the method new_id : unit -> node_id generates a new unused id.
A node is modeled as a node id and node label pair, (i,l). An edge is modeled as a triple i -> j, which contains the source and target node ids i and j, and the edge label l. These types are defined as follows:
type 'n node = node_id * 'n type 'e edge = node_id * node_id * 'e
signature GRAPH = sig type node_id = int type 'n node = node_id * 'n type 'e edge = node_id * node_id * 'e exception Graph of string exception Subgraph exception NotFound exception Unimplemented exception Readonly datatype ('n,'e,'g) graph = GRAPH of ('n,'e,'g) graph_methods withtype ('n,'e,'g) graph_methods = { name : string, graph_info : 'g, (* selectors *) (* mutators *) (* iterators *) } endA few exceptions are predefined in this signature, which have the following informal interpretation. Exception Graph is raised when a bug is encountered. The exception Subgraph is raised if certain semantics constraints imposed on a graph are violated. The exception NotFound is raised if lookup of a node id fails. The exception Unimplemented is raised if a certain feature is accessed but is undefined on the graph. The exception Readonly is raised if the graph is readonly and an update operation is attempted.
nodes : unit -> \alpha node list & Return a list of all nodes in a graph \\ edges : unit -> \beta edge list & Return a list of all edges in a graph \\ order : unit -> int & Return the number of nodes in a graph. The graph is empty if its order is zero \\ size : unit -> int & Return the number of edges in a graph \\ capacity : unit -> int & Return the maximum node id in the graph, plus 1. This can be used as a new id \\ succ : node_id -> node_id list & Given a node id i, return the node ids of all its successors, i.e. { j | i \edge{l} j \in E}. \\ pred : node_id -> node_id list & Given a node id j, return the node ids of all its predecessors, i.e. { i | i \edge{l} j \in E}. \\ out_edges : node_id -> \beta edge list & Given a node id i, return all the out-going edges from node i, i.e. all edges whose source is i. \\ in_edges : node_id -> \beta edge list & Given a node id j, return all the in-coming edges from node j, i.e. all edges whose target is j. \\ has_edge : node_id * node_id -> bool & Given two node ids i and j, find out if an edge with source i and target j exists. \\ has_node : node_id -> bool & Given a node id i, find out if a node of id i exists. \\ node_info : node_id -> \alpha & Given a node id, return its node label. If the node does not exist, raise exception NotFound. \\
val GRAPH g = G val edges = #edges g () val nodes = #nodes g ()We can view #edges g} as sending the message to \sml{G. While all this seems like mere syntactic deviation from the usual signature/structure approach, there are two crucial differences which we will exploit: {\em (i)} records are first class objects while structures are not (consequently late binding of ``methods'' and cannot be easily simulated on the structure level); {\em (ii)} recursion is possible on the type level, while recursive structures are not available. The extra flexibility of this choice becomes apparent with the introduction of views later.
signature GRAPH_IMPLEMENTATION = sig val graph : string * 'g * int -> ('n,'e,'g) graph endThe function graph takes a string (the name of the graph), graph info, and a default size as arguments and create an empty graph. The functor DirectedGraphFn:
functor DirectedGraphFn(A : ARRAY_SIG) : GRAPH_IMPLEMENTATIONimplements a graph using adjacency lists as internal representation. It takes an array type as a parameter. For graphs with node ids that are dense enumerations, the DynamicArray structure should be used as the parameter to this functor. The structure DirectedGraph is predefined as follows:
structure DirectedGraph = DirectedGraphFn(DynamicArray)For node ids that are sparse enumerations, the structure HashArray, which implements integer-keyed hash tables with the signature of arrays, can be used as argument to DirectedGraphFn. For graphs with fixed sizes determined at creation time, the structure Array can be used (see also functor /tt UndoableArrayFn, which creates arrays with undoable updates, and transaction-like semantics.)
val dfs : ('n,'e,'g) graph -> (node_id -> unit) -> ('e edge -> unit) -> node_id list -> unitThe function dfs takes as arguments a graph, a function f : node_id -> unit, a function g : 'e edge -> unit, and a set of source vertices. It performs depth first search on the graph. The function f is invoked whenever a new node is being visited, while the function g is invoked whenever a new edge is being traversed. This algorithm has running time O(|V|+|E|).
val dfsfold : ('n,'e,'g) graph -> (node_id * 'a -> 'a) -> ('e edge * 'b -> 'a) -> node_id list -> 'a * 'b -> 'a * 'b val dfsnum : ('n,'e,'g) graph -> (node_id * 'a -> 'a) -> { dfsnum : int array, compnum : int array }The function bfs} is similar to \sml{dfs except that breath first search is performed.
val bfs : ('n,'e,'g) graph -> (node_id -> unit) -> ('e edge -> unit) -> node_id list -> unit val bfsdist : ('n,'e,'g) graph -> node_id list -> int array
val preorder_numbering : ('n,'e,'g) graph -> int -> int array val postorder_numbering : ('n,'e,'g) graph -> int -> int arrayBoth these functions take a tree T and a root v, and return the preorder numbering and the postorder numbering of the tree respectively.
val topsort : ('n,'e,'g) graph -> node_id list -> node_id listThe function topsort takes a graph G and a set of source vertices S as arguments. It returns a topological sort of all the nodes reachable from the set S. This algorithm has running time O(|S|+|V|+|E|).
val strong_components : ('n,'e,'g) graph -> (node_id list * 'a -> 'a) -> 'a -> 'aThe function strong_components takes a graph G and an aggregate function f with type
node_id list * 'a -> 'a\noindent and an identity element x : 'a as arguments. Function f is invoked with a strongly connected component (represented as a list of node ids) as each is discovered. That is, the function strong_components computes \[ f(SCC_n,f(SCC_{n-1},\ldots f(SCC_1,x))) \] where SCC_1,\ldots,SCC_n are the strongly connected components in topological order. This algorithm has running time O(|V|+|E|).
val biconnected_components : ('n,'e,'g) graph -> ('e edge list * 'a -> 'a) -> 'a -> 'aThe function biconnected_components takes a graph G and an aggregate function f with type
'e edge list * 'a -> 'a\noindent and an identity element x : 'a as arguments. Function f is invoked with a biconnected component (represented as a list of edges) as each is discovered. That is, the function biconnected_components computes \[ f(BCC_n,f(BCC_{n-1},\ldots f(BCC_1,x))) \] where BCC_1,\ldots,BCC_n are the biconnected components. This algorithm has running time O(|V|+|E|).
val is_cyclic : ('n,'e,'g) graph -> boolFunction is_cyclic tests if a graph is cyclic. This algorithm has running time O(|V|+|E|).
val cycles : ('n,'e,'g) graph -> ('e edge list * 'a -> 'a) -> 'a ->'aA simple cycle is a circuit that visits each vertex only once. The function cycles enumerates all simple cycles in a graph G. It takes as argument an aggregate function f of type
'e edge list * 'a -> 'aand an identity element e, and computes as result the expression \[ f(c_n,f(c_{n-1},f(c_{n-2},\ldots f(c_1,e)))) \] where c_1,\ldots,c_n are all the simple cycles in the graph. All cycles c_1,\ldots,c_n are guaranteed to be distinct. A cycle is represented as a sequence of adjacent edges, i.e. in the order of \[ v_1 \to v_2, v_2 \to v_3, v_3 \to v_4, \ldots, v_{n-1} \to v_n, v_n \to v_1 \] Our implementation works by first decomposing the graph into its strongly connected components, then uses backtracking to enumerate simple cycles in each component.
signature MIN_COST_SPANNING_TREE = sig exception Unconnected val spanning_tree : { weight : 'e edge -> 'a, < : 'a * 'a -> bool } -> ('n, 'e, 'g) graph -> ('e edge * 'a -> 'a) -> 'a -> 'a end structure Kruskal : MIN_COST_SPANNING_TREEStructure Kruskal implements Kruskal's algorithm for computing a minimal cost spanning tree of a graph. The function spanning_tree takes as arguments:
signature ABELIAN_GROUP = sig type elem val + : elem * elem -> elem val - : elem * elem -> elem val : elem -> elem val zero : elem val < : elem * elem -> bool val == : elem * elem -> bool end signature ABELIAN_GROUP_WITH_INF = sig include ABELIAN_GROUP val inf : elem endSignature ABELIAN_GROUP specifies an ordered commutative group, while signature ABELIAN_GROUP_WITH_INF specifies an ordered commutative group with an infinity element inf which satisfies {\em(i)} -\mbox{inf}} \le x \le \mbox{inf} for all x, and {\em (ii) x + \mbox{inf}} = \mbox{inf for all x.
signature SINGLE_SOURCE_SHORTEST_PATHS = sig structure Num : ABELIAN_GROUP_WITH_INF val single_source_shortest_paths : { graph : ('n,'e,'g) graph, weight : 'e edge -> Num.elem, s : node_id } -> { dist : Num.elem array, pred : node_id array } end functor DijkstraFn(Num : ABELIAN_GROUP_WITH_INF) : SINGLE_SOURCE_SHORTEST_PATHSThe functor DijkstraFn implements Dijkstra's algorithm for single source shortest paths. The function \linebreak single_source_shortest_paths takes as arguments:
functor BellmanFordFn(Num : ABELIAN_GROUP_WITH_INF) : sig include SINGLE_SOURCE_SHORTEST_PATHS exception NegativeCycle end
signature ALL_PAIRS_SHORTEST_PATHS = sig structure Num : ABELIAN_GROUP_WITH_INF val all_pairs_shortest_paths : { graph : ('n,'e,'g) graph, weight : 'e edge -> Num.elem } -> { dist : Num.elem Array2.array, pred : node_id Array2.array } end functor FloydWarshallFn(Num : ABELIAN_GROUP_WITH_INF) : ALL_PAIRS_SHORTEST_PATHSThe functor FloydWarshallFn implements Floyd-Warshall's algorithm for all pairs shortest paths. The function all_pairs_shortest_paths takes as arguments:
functor JohnsonFn(Num : ABELIAN_GROUP_WITH_INF) : sig include ALL_PAIRS_SHORTEST_PATHS exception Negative Cycle end
signature TRANSITIVE_CLOSURE = sig val acyclic_transitive_closure : { + : ('e * 'e -> 'e), simple : bool } -> ('n,'e,'g) graph -> unit val acyclic_transitive_closure2 : { + : 'e * 'e -> 'e, max : 'e * 'e -> 'e } -> ('n,'e,'g) graph -> unit val transitive_closure : ('e * 'e -> 'e) -> ('n,'e,'g) graph -> unit structure TransitiveClosure : TRANSITIVE_CLOSUREStructure TransitiveClosure implements in-place transitive closures on graphs. Three functions are implemented. Functions acyclic_transitive_closure and acyclic_transitive_closure2 can be used to compute the transitive closure of an acyclic graph, whereas the function transitive_closure computes the transitive closure of a cyclic graph. All take a binary function
+ : 'e * 'e -> 'edefined on edge labels. Transitive edges are inserted in the following manner:
signature MAX_FLOW = sig structure Num : ABELIAN_GROUP val max_flow : { graph : ('n,'e,'g) graph, s : node_id, t : node_id, capacity : 'e edge -> Num.elem, flows : 'e edge * Num.elem -> unit } -> Num.elem end functor MaxFlowFn(Num : ABELIAN_GROUP) : MAX_FLOWThe function max_flow returns its result in the follow manner: The function returns the total flow as its result value. Furthermore, the function flows is called once for each edge e in the graph with its associated flow f_e. This algorithm uses Goldberg's preflow-push approach, and runs in O(|V|^2|E|) time.
signature MIN_CUT = sig structure Num : ABELIAN_GROUP val min_cut : { graph : ('n,'e,'g) graph, weight : 'e edge -> Num.elem } -> node_id list * Num.elem end functor MinCutFn(Num : ABELIAN_GROUP) : MIN_CUTThe function min_cut returns a list of node ids denoting one side of the cut C (the other side of the cut is V - C) and the weight cut.
val matching : ('n,'e,'g) graph -> ('e edge * 'a -> 'a) -> 'a -> 'a * intThe function BipartiteMatching.matching computes the maximal cardinality matching of a bipartite graph. As result, the function iterates over all the matched edges and returns the number of matched edges. The algorithm runs in time O(|V||E|).
signature NODE_PARTITION = sig type 'n node_partition val node_partition : ('n,'e,'g) graph -> 'n node_partition val !! : 'n node_partition -> node_id -> 'n node val == : 'n node_partition -> node_id * node_id -> bool val union : 'n node_partition -> ('n node * 'n node -> 'n node) -> node_id * node_id -> bool val union': 'n node_partition -> node_id * node_id -> bool end
signature NODE_PRIORITY_QUEUE = sig type node_priority_queue exception EmptyPriorityQueue val create : (node_id * node_id -> bool) -> node_priority_queue val fromGraph : (node_id * node_id -> bool) -> ('n,'e,'g) graph -> node_priority_queue val isEmpty : node_priority_queue -> bool val clear : node_priority_queue -> unit val min : node_priority_queue -> node_id val deleteMin : node_priority_queue -> node_id val decreaseWeight : node_priority_queue * node_id -> unit val insert : node_priority_queue * node_id -> unit val toList : node_priority_queue -> node_id list end
set_entries : node_id list -> unit set_exits : node_id list -> unit entries : unit -> node_id list exits : unit -> node_id listFor example, a CFG usually has a single entry and a single exit. These methods allow the client to destinate one node as the entry and another as the exit. In the case of subgraph view, these methods are overridden so that the proper conventions are preserved: a node in a subgraph is an entry (exit) iff there is an in-edge (out-edge) from (to) outside the (sub-)graph. Similarly, the methods entry_edges} and \sml{exit_edges can be used return the entry and exit edges associated with a node in a subgraph.
entry_edges : node_id -> 'e edge list exit_edges : node_id -> 'e edge listThese methods are initially defined to return [] in a graph and subsequently overridden in a subgraph.
ReversedGraphView.rev_view : ('n,'e,'g) graph -> ('n,'e,'g) graphThis combinator takes a graph G and produces a view G^R which reverses the direction of all its edges, including entry and exit edges. Thus the edge i \edge{l} j in G becomes the edge j \edge{l} i in G^R. This view is fully update transparent.
ReadOnlyGraphView.readonly_view : ('n,'e,'g) graph -> ('n,'e,'g) graphThis function takes a graph G and produces a view G' in which no mutator methods can be used. Invoking a mutator method raises the exception Readonly. This view is globally update transparent.
functor GraphSnapShotFn(GI : GRAPH_IMPLEMENTATION) : GRAPH_SNAPSHOT signature GRAPH_SNAPSHOT = sig val snapshot : ('n,'e,'g) graph -> { picture : ('n,'e,'g) graph, button : unit -> unit } endThe function snapshot can be used to keep a cached copy of a view a.k.a the picture. This cached copy can be updated locally but the modification will not be reflected back to the base graph. The function button can be used to keep the view and the base graph up-to-date.
IsomorphicGraphView.map : ('n node -> \(\alpha'\)) -> ('e edge -> \(\beta'\)) -> ('g -> \(\gamma'\)) -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graphThe function map} is a generalization of the \sml{map function on lists. It takes three functions \(f\) : 'n node -> \(\alpha'\)}, \sml{\(g\) : 'e edge -> \(\beta'\), \(h\) : 'g -> \(\gamma\)' and a graph G=(V,L,E,I) as arguments. It computes the view G'=(V,L',E',I') where \begin{eqnarray*} L'(v) & = & f(v,L(v)) \mbox{\ for all v \in V} \\ E' & = & { i \edge{g(i,j,l)} j | i \edge{l} j \in E } \\ I' & = & h(I) \end{eqnarray*}
SingletonGraphView.singleton_view : ('n,'e,'g) graph -> node_id -> ('n,'e,'g) graphFunction singleton_view takes a graph G and a node id v (which must exists in G) and return an edge-free graph with only one node (v). This view is opaque.
RenamedGraphView.rename_view : int -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graphThe function rename_view takes an integer n and a graph G and create a fully update transparent view where all node ids are incremented by n. Formally, given graph G=(V,E,L,I) it computes the view G'=(V',E',L',I) where \begin{eqnarray*} V' & = & { v + n | v \in V } \\ E' & = & { i+n \edge{l} j+n | i \edge{l} j \in E } \\ L' & = & \lambda v. L(v-n) \end{eqnarray*}
UnionGraphView.union_view : ('g * \(\gamma'\)) -> \(\gamma''\)) -> ('n,'e,'g) graph * (\(\alpha,\beta,\gamma'\)) graph -> (\(\alpha',\beta',\gamma''\)) graph GraphCombinations.unions : ('n,'e,'g) graph list -> (\(\alpha',\beta',\gamma\)) graph GraphCombinations.sum : ('n,'e,'g) graph * ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma\)) graph GraphCombinations.sums : ('n,'e,'g) graph list -> (\(\alpha',\beta',\gamma\)) graphFunction union_view takes as arguments a function f, and two graphs G=(V,L,E,I) and G'=(V',L',E',I'), it computes the union G+G' of these graphs. Formally, G \union G'=(V'',L'',E'',I'') where \begin{eqnarray*} V'' & = & V \union V' \\ L'' & = & L \overrides L' \\ E'' & = & E \union E' \\ I'' & = & f(I,I') \end{eqnarray*} The function sum} constructs a \define{disjoint sum of two graphs.
SimpleGraph.simple_graph : (node_id * node_id * 'e list -> 'e) -> ('n,'e,'g) graph -> ('n,'e,'g) graphFunction simple_graph takes a merge function f and a multi-graph G as arguments and return a view in which all parallel multi-edges (edges with the same source and target) are combined into a single edge: i.e. any collection of multi-edges between the same source s and target t and with labels l_1,\ldots,l_n, are replaced by the edge s \edge{l_{st}} t in the view, where l_{st} = f(s,t,[l_1,\ldots,l_n]). The function f is assumed to satisfy the equality l = f(s,t,[l]) for all l, s and t.
NoEntryView.no_entry_view : ('n,'e,'g) graph -> ('n,'e,'g) graph NoEntryView.no_exit_view : ('n,'e,'g) graph -> ('n,'e,'g) graphThe function no_entry_view creates a view in which all entry edges (and thus entry nodes) are removed. The function no_exit_view is the dual of this and creates a view in which all exit edges are removed. This view is fully update transparent. It is possible to remove all entry and exit edges by composing these two functions.
SubgraphView.subgraph_view : node_id list -> ('e edge -> bool) -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graphThe function subgraph_view takes as arguments a set of node ids S, an edge predicate p and a graph G=(V,L,E,I). It returns a view in which only the visible nodes are S and the only visible edges e are those that satisfy p(e) and with sources and targets in S. S must be a subset of V.
Subgraph_P_View.subgraph_p_view : node_id list -> (node_id -> bool) -> (node_id * node_id -> bool) -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graphThe function subgraph_view takes as arguments a set of node ids S, a node predicate p, an edge predicate q and a graph G=(V,L,E,I). It returns a view in which only the visible nodes v are those in S satisfying p(v), and the only visible edges e are those that satisfy q(e) and with sources and targets in S. S must be a subset of V.
TraceView.trace_view : node_id list -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph\begin{wrapfigure}{r}{3in} \begin{Boxit} \psfig{figure=trace.eps,width=2.8in} \end{Boxit} \caption{\label{fig:trace-view} A trace view} \end{wrapfigure} A trace is an acyclic path in a graph. The function trace_view takes a trace of node ids v_1,\ldots,v_n and a graph G and returns a view in which only the nodes are visible. Only the edges that connected two adjacent nodes on the trace, i.e. v_i \to v_{i+1} for some i = 1 \ldots n-1 are considered be within the view. Thus if there is an edge v_i \to v_j in G where j \ne i+1 this edge is not considered to be within the view --- it is considered to be an exit edge from v_i and an entry edge from v_j however. Trace views can be used to construct a CFG region suitable for trace scheduling \cite{trace-scheduling,bulldog}. Figure \ref{fig:trace-view} illustrates this concept graphically. Here, the trace view is formed from the nodes A, C, D, F} and \sml{G. The solid edges linking the trace is visible within the view. All other dotted edges are considered to be either entry of exit edges into the trace. The edge from node G} to \sml{A is considered to be both since it exits from G} and enters into \sml{A.
AcyclicSubgraphView.acyclic_view : node_id list -> ('n,'e,'g) graph -> ('n,'e,'g) graph\begin{wrapfigure}{r}{3in} \begin{Boxit} \psfig{figure=subgraph.eps,width=2.8in} \end{Boxit} \caption{\label{fig:acyclic-subgraph-view} An acyclic subgraph} \end{wrapfigure} The function acyclic_view takes an ordered list of node ids v_1,\ldots,v_n and a graph G as arguments and return a view G' such that only the nodes v_1,\ldots,v_n are visible. In addition, only the edges with directions consistent with the order list are considered to be within the view. Thus an edge v_i \to v_j from G is in G' iff 1 \le i < j \le n. Acyclic views can be used to construct a CFG region suitable for DAG scheduling. Figure \ref{fig:acyclic-subgraph-view} illustrates this concept graphically.
StartStopView.start_stop_view : { start : 'n node, stop : 'n node, edges : 'e edge list } -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graphThe function start_stop_view
SingleEntryMultipleExit.SEME exit : 'n node -> ('n,'e,'g) graph -> ('n,'e,'g) graphThe function SEME converts a single-entry/multiple-exits graph G into a single entry/single exit graph. It takes an exit node e and a graph G and returns a view G'. Suppose i \edge{l} j be an exit edge in G. In view G this edge is replaced by a new normal edge i \edge{l} e and a new exit edge e \edge{l} j. Thus e becomes the sole exit node in the new view.
do_before_\(xxx\) : f -> ('n,'e,'g) graph -> ('n,'e,'g) graph\noindent returns a view G' such that whenever method xxx is invoked in G', the function f is called. Similarly, the combinator
do_after_\(xxx\) : f -> ('n,'e,'g) graph -> ('n,'e,'g) graph\noindent creates a new view G'' such that the function f is called after the method is invoked. \begin{Figure} \begin{boxit} \small
do_before_new_id : (unit -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_after_new_id : (node_id -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_before_add_node : ('n node -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_after_add_node : ('n node -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_before_add_edge : ('e edge -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_after_add_edge : ('e edge -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_before_remove_node : (node_id -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_after_remove_node : (node_id -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_before_set_in_edges : (node_id * 'e edge list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_after_set_in_edges : (node_id * 'e edge list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_before_set_out_edges : (node_id * 'e edge list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_after_set_out_edges : (node_id * 'e edge list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_before_set_entries : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_after_set_entries : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_before_set_exits : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_after_set_exits : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph\end{boxit} \caption{\label{fig:behavioral-view-primitives} Behavioral view primitives} \end{Figure} Frequently it is not necessary to know precisely by which method a graph's structure has been modified, only that it is. The following two methods take a notification function f and returns a new view. f is invoked before a modification is attempted in a view created by do_before_changed. It is invoked after the modification in a view created by do_after_changed.
do_before_changed : (('n,'e,'g) graph -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph do_after_changed : (('n,'e,'g) graph -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graphBehavioral views created by the above functions are all fully update transparent.