The Graph Library

Overview

Graphs are the most fundamental data structure in the MLRISC system. MLRISC now contains an extensive library for working with graphs.

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

The graph signature

All graphs are accessed through an abstract interface of the polymorphic type ('n,'e,'g) graph. Here, 'n is the type of the node labels, 'e is the type of the edge labels, and 'g is the type of any extra information embedded in a graph. We call the latter graph info. Formally, a graph G is a quadruple (V,L,E,I) where V is a set of node ids, L : V \to \alpha is a node labeling function from vertices to node labels, E is a multi-set of labeled-edges of type V \times V \times \beta, and I: \gamma is the graph info. The interface of a graph is packaged into a record of methods that manipulate the base representation:
 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 *)
       }
 end
A 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.

Selectors

Methods that access the structure of a graph are listed below:
   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. \\

Graph hierarchy

A graph G may in fact be a subgraph of a base graph G', or obtained from G' via some transformation T. In such cases the following methods may be used to determine of the relationship between G and G'. An entry edge is an edge in G' that terminates at a node in G, but is not an edge in G. Similarly, an exit edge is an edge in G' that originates from a node in G, but is not an edge in G. An entry node is a node in G that has an incoming entry edge. An \define{exit node} is a node in G that has an out-going exit edge. If G is not a subgraph, all these methods will return nil. \begin{methods} entries : unit -> node_id list & Return the node ids of all the entry nodes. \\ exits : unit -> node_id list & Return the node ids of all the exit nodes. \\ entry_edges : node_id -> \beta edge list & Given a node id i, return all the entry edges whose sources are i. \\ exit_edges : node_id -> \beta edge list & Given a node id i, return all the exit edges whose targets are i. \end{methods} \pagebreak

Mutators

Methods to update a graph are listed below: \begin{methods} new_id : unit -> node_id & Return a unique node id guaranteed to be absent in the current graph. \\ add_node : \alpha node -> unit & Insert node into the graph. If a node of the same node id already exists, replace the old node with the new. \\ add_edge : \beta edge -> unit & Insert an edge into the graph. \\ remove_node : node_id -> unit & Given a node id n, remove the node with the node id from the graph. This also automatically removes all edges with source or target n. \\ set_out_edges : node_id * \beta edge list -> unit & Given a node id n, and a list of edges e_1,\ldots,e_n with sources n, replace all out-edges of n by e_1,\ldots,e_n. \\ set_in_edges : node_id * \beta edge list -> unit & Given a node id n, and a list of edges e_1,\ldots,e_n with targets n, replace all in-edges of n by e_1,\ldots,e_n. \\ set_entries : node_id list -> unit & Set the entry nodes of a graph. \\ set_exits : node_id list -> unit & Set the exit nodes of a graph. \\ garbage_collect : unit -> unit & Reclaim all node ids of nodes that have been removed by remove_node}. Subsequent \sml{new_id will reuse these node ids. \\ \end{methods}

Iterators

Two primitive iterators are supported in the graph interface. Method forall_nodes iterates over all the nodes in a graph, while method forall_edges iterates over all the edges. Other more complex iterators can be found in other modules. \begin{methods} forall_nodes : (\alpha node -> unit) -> unit & Given a function f on nodes, apply f on all the nodes in the graph. \\ forall_edges : (\beta edge -> unit) -> unit & Given a function f on edges, apply f on all the edges in the graph. \end{methods}

Manipulating a graph

Since operations on the graph type are packaged into a record, an ``object oriented'' style of graph manipulation should be used. For example, if G is a graph object, then we can obtain all the nodes and edges of G as follows.
 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.

Creating a Graph

A graph implementation has the following signature
 signature GRAPH_IMPLEMENTATION = sig
   val graph : string * 'g * int -> ('n,'e,'g) graph
 end
The 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_IMPLEMENTATION
implements 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.)

Basic Graph Algorithms

Depth-/Breath-First Search

   val dfs : ('n,'e,'g) graph  ->
             (node_id -> unit) ->
             ('e edge -> unit) ->
             node_id list -> unit
The 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

Preorder/Postorder numbering

   val preorder_numbering  : ('n,'e,'g) graph -> int -> int array
   val postorder_numbering : ('n,'e,'g) graph -> int -> int array
Both these functions take a tree T and a root v, and return the preorder numbering and the postorder numbering of the tree respectively.

Topological Sort

val topsort : ('n,'e,'g) graph -> node_id list -> node_id list
The 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|).

Strongly Connected Components

 val strong_components : ('n,'e,'g) graph -> 
   (node_id list * 'a -> 'a) -> 'a -> 'a
The 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|).

Biconnected Components

 val biconnected_components : ('n,'e,'g) graph -> 
        ('e edge list * 'a -> 'a) -> 'a -> 'a
The 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|).

Cyclic Test

 val is_cyclic : ('n,'e,'g) graph -> bool
Function is_cyclic tests if a graph is cyclic. This algorithm has running time O(|V|+|E|).

Enumerate Simple Cycles

 val cycles : ('n,'e,'g) graph -> ('e edge list * 'a -> 'a) -> 'a ->'a
A 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 -> 'a
  
and 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.

Minimal Cost Spanning Tree

 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_TREE
Structure Kruskal implements Kruskal's algorithm for computing a minimal cost spanning tree of a graph. The function spanning_tree takes as arguments: The function spanning_tree computes \[ f(e_{n},f(e_{n-1},\ldots f(e_1,x))) \] where e_1,\ldots,e_n are the edges in a minimal cost spanning tree of the graph. The exception Unconnected is raised if the graph is unconnected.

Abelian Groups

Graph algorithms that deal with numeric weights or distances are parameterized with respect to the signatures ABELIAN_GROUP} or \sml{ABELIAN_GROUP_WITH_INF. These are defined as follows:
 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
 end
Signature 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.

Single Source Shortest Paths

 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_PATHS
The functor DijkstraFn implements Dijkstra's algorithm for single source shortest paths. The function \linebreak single_source_shortest_paths takes as arguments: It returns two arrays dist and pred indexed by vertices. These arrays have the following interpretation. Given a vertex v, Dijkstra's algorithm fails to work on graphs that have negative edge weights. To handle negative weights, Bellman-Ford's algorithm can be used. The exception NegativeCycle is raised if a cycle of negative total weight is detected.
 functor BellmanFordFn(Num : ABELIAN_GROUP_WITH_INF) : sig
    include SINGLE_SOURCE_SHORTEST_PATHS
    exception NegativeCycle
 end

All Pairs Shortest Paths

 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_PATHS
The functor FloydWarshallFn implements Floyd-Warshall's algorithm for all pairs shortest paths. The function all_pairs_shortest_paths takes as arguments: It returns two 2-dimensional arrays dist} and \sml{pred indexed by vertices (u,v). These arrays have the following interpretation. Given a pair (u,v), This algorithm runs in time O(|V|^3+|E|). An alternative implementation is available that uses Johnson's algorithm, which works better for sparse graphs:
 functor JohnsonFn(Num : ABELIAN_GROUP_WITH_INF) 
    : sig include ALL_PAIRS_SHORTEST_PATHS
          exception Negative Cycle
      end

Transitive Closure

 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_CLOSURE
Structure 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 -> 'e
defined on edge labels. Transitive edges are inserted in the following manner:

Max Flow

The function max_flow computes the maximum flow between the source vertex s and the sink vertex t} in the graph when given a \sml{capacity function.
 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_FLOW
The 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.

Min Cut

The function min_cut computes the minimum (undirected) cut in a graph} when given a \sml{weight function on its edges.
 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_CUT
The 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.

Max Cardinality Matching

   val matching : ('n,'e,'g) graph -> ('e edge * 'a -> 'a) -> 'a -> 'a * int
The 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|).

Node Partition

 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

Node Priority Queue

 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

Views}\label{sec:views

Simply put, a view is an alternative presentation of a data structure to a client. A graph, such as the control flow graph, frequently has to be presented in different ways in a compiler. For example, when global scheduling is applied on a region (a subgraph of the CFG), we want to be able to concentrate on just the region and ignore all nodes and edges that are not part of the current focus. All transformations that are applied on the current region view should be automatically reflected back to the entire CFG as a whole. Furthermore, we want to be able to freely intermix graphs and subgraphs of the same type in our program, without having to introducing sums in our type representations. The subgraph_view} view combinator accomplishes this. \sml{Subgraph takes a list of nodes and produces a graph object which is a view of the node induced subgraph of the original graph. All modification to the subgraph are automatically reflected back to the original graph. From the client point of view, a graph and a subgraph are entirely indistinguishable, and furthermore, graphs and subgraphs can be freely mixed together (they are the same type from ML's point of view.) This transparency is obtained by selective method overriding, composition, and delegation. For example, a generic graph object provides the following methods for setting and looking up the entries and exits from a graph.
   set_entries  : node_id list -> unit
   set_exits    : node_id list -> unit
   entries      : unit -> node_id list
   exits        : unit -> node_id list
For 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 list
These methods are initially defined to return [] in a graph and subsequently overridden in a subgraph.

Update Transparency

Suppose a view G' is created from some base graphs or views. Update transparency refers to the fact that G' behaves consistently according to its conventions and semantics when updates are performed. There are 4 different type of update transparencies:

Structural Views}\label{sec:structural-views

Reversal

   ReversedGraphView.rev_view : ('n,'e,'g) graph -> ('n,'e,'g) graph
This 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.

Readonly

   ReadOnlyGraphView.readonly_view : ('n,'e,'g) graph -> ('n,'e,'g) graph
This 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.

Snapshot

   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 }
   end
The 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.

Map

   IsomorphicGraphView.map :
     ('n node -> \(\alpha'\)) -> ('e edge -> \(\beta'\)) -> ('g -> \(\gamma'\)) -> 
     ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph
The 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*}

Singleton

   SingletonGraphView.singleton_view : ('n,'e,'g) graph -> node_id -> ('n,'e,'g) graph
Function 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.

Node id renaming

   RenamedGraphView.rename_view : int -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph
The 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*}

Union and Sum

   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\)) graph
Function 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.

Simple Graph View

  SimpleGraph.simple_graph : (node_id * node_id * 'e list -> 'e) ->
   ('n,'e,'g) graph -> ('n,'e,'g) graph
Function 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.

No Entry or No Exit

  NoEntryView.no_entry_view : ('n,'e,'g) graph -> ('n,'e,'g) graph
  NoEntryView.no_exit_view : ('n,'e,'g) graph -> ('n,'e,'g) graph
The 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.

Subgraphs

   SubgraphView.subgraph_view : node_id list -> ('e edge -> bool) -> 
     ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph
The 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'\)) graph
The 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.

Trace

   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.

Acyclic Subgraph

   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.

Start and Stop

   StartStopView.start_stop_view :
     { start : 'n node,
        stop  : 'n node,
        edges : 'e edge list
     } -> ('n,'e,'g) graph -> (\(\alpha',\beta',\gamma'\)) graph
The function start_stop_view

Single-Entry/Multiple-Exits

   SingleEntryMultipleExit.SEME
     exit : 'n node -> ('n,'e,'g) graph -> ('n,'e,'g) graph
The 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.

Behavioral Views

Behavioral Primitives

Figure \ref{fig:behavioral-view-primitives} lists the set of behavioral primitives defined in structure /tt GraphWrappers. These functions allow the user to attach an action a to a mutator method m such that whenever m is invoked so does a. Given a graph G, the combinator
   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) graph
Behavioral views created by the above functions are all fully update transparent.
Allen Leung

Click to toggle
does not end with </html> tag
does not end with </body> tag
The output has ended thus: E="-2"> <ADDRESS> <A HREF="mailto:leunga@cs.nyu.edu">Allen Leung</A></ADDRESS> <BR> </BODY> </HTML>