The Graph Library
OverviewGraphs are the most fundamental data structure in the MLRISC system, and in fact in many optimizing compilers. 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, .
An edge is modeled as a triple , which contains
the source and target node ids and ,
and the edge label . These types are defined as follows:
The graph signatureAll 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 is a quadruple where is a set of node ids, is a node labeling function from vertices to node labels, is a multi-set of labeled-edges of type , and is the graph info.
The interface of a graph is packaged into a
record of methods that manipulate the base representation:
SelectorsMethods that access the structure of a graph are listed below:
Graph hierarchyA graph may in fact be a subgraph of a base graph , or obtained from via some transformation . In such cases the following methods may be used to determine of the relationship between and . An entry edge is an edge in that terminates at a node in , but is not an edge in . Similarly, an exit edge is an edge in that originates from a node in , but is not an edge in . An entry node is a node in that has an incoming entry edge. An exit node is a node in that has an out-going exit edge. If is not a subgraph, all these methods will return nil.
MutatorsMethods to update a graph are listed below:
IteratorsTwo 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.
Manipulating a graphSince 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 G. While all this seems like mere syntactic deviation from the usual signature/structure approach, there are two crucial differences which we will exploit: (i) records are first class objects while structures are not (consequently late binding of ``methods'' and cannot be easily simulated on the structure level); (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 GraphA graph implementation has the following signaturesignature 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 DirectedGraph:
Basic Graph AlgorithmsDepth-/Breath-First Searchval 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 .
Preorder/Postorder numberingval preorder_numbering : ('n,'e,'g) graph -> int -> int array val postorder_numbering : ('n,'e,'g) graph -> int -> int arrayBoth these functions take a tree and a root , and return the preorder numbering and the postorder numbering of the tree respectively. Topological Sortval topsort : ('n,'e,'g) graph -> node_id list -> node_id listThe function topsort takes a graph and a set of source vertices as arguments. It returns a topological sort of all the nodes reachable from the set . This algorithm has running time . Strongly Connected Componentsval strong_components : ('n,'e,'g) graph -> (node_id list * 'a -> 'a) -> 'a -> 'aThe function strong_components takes a graph and an aggregate function with type node_id list * 'a -> 'aand an identity element x : 'a as arguments. Function 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
Biconnected Componentsval biconnected_components : ('n,'e,'g) graph -> ('e edge list * 'a -> 'a) -> 'a -> 'aThe function biconnected_components takes a graph and an aggregate function with type 'e edge list * 'a -> 'aand an identity element x : 'a as arguments. Function is invoked with a biconnected component (represented as a list of edges) as each is discovered. That is, the function biconnected_components computes
Cyclic Testval is_cyclic : ('n,'e,'g) graph -> boolFunction is_cyclic tests if a graph is cyclic. This algorithm has running time . Enumerate Simple Cyclesval 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 . It takes as argument an aggregate function of type 'e edge list * 'a -> 'aand an identity element , and computes as result the expression Minimal Cost Spanning Treesignature 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:
Abelian GroupsGraph algorithms that deal with numeric weights or distances are parameterized with respect to the signatures ABELIAN_GROUP or 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 endSignature ABELIAN_GROUP specifies an ordered commutative group, while signature ABELIAN_GROUP_WITH_INF specifies an ordered commutative group with an infinity element inf. Single Source Shortest Pathssignature 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 Dijkstra(Num : ABELIAN_GROUP_WITH_INF) : SINGLE_SOURCE_SHORTEST_PATHSThe functor Dijkstra implements Dijkstra's algorithm for single source shortest paths. The function single_source_shortest_paths takes as arguments:
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.
All Pairs Shortest Pathssignature 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 FloydWarshall(Num : ABELIAN_GROUP_WITH_INF) : ALL_PAIRS_SHORTEST_PATHSThe functor FloydWarshall implements Floyd-Warshall's algorithm for all pairs shortest paths. The function all_pairs_shortest_paths takes as arguments:
An alternative implementation is available that uses Johnson's algorithm,
which works better for sparse graphs:
Transitive Closuresignature 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:
Max FlowThe function max_flow computes the maximum flow between the source vertex s and the sink vertex t in the graph when given a 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 MaxFlow(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 in the graph with its associated flow . This algorithm uses Goldberg's preflow-push approach, and runs in time. Min CutThe function min_cut computes the minimum (undirected) cut in a graph when given a 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 MinCut(Num : ABELIAN_GROUP) : MIN_CUTThe function min_cut returns a list of node ids denoting one side of the cut (the other side of the cut is and the weight cut. Max Cardinality Matchingval 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 . Node Partitionsignature 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 Queuesignature 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 ViewsSimply 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. 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.
Update TransparencySuppose a view is created from some base graphs or views. Update transparency refers to the fact that behaves consistently according to its conventions and semantics when updates are performed. There are 4 different type of update transparencies:
Structural ViewsReversalval ReversedGraphView.rev_view : ('n,'e,'g) graph -> ('n,'e,'g) graphThis combinator takes a graph and produces a view which reverses the direction of all its edges, including entry and exit edges. Thus the edge in becomes the edge in . This view is fully update transparent. Readonlyval ReadOnlyGraphView.readonly_view : ('n,'e,'g) graph -> ('n,'e,'g) graphThis function takes a graph and produces a view in which no mutator methods can be used. Invoking a mutator method raises the exception Readonly. This view is globally update transparent. Snapshotfunctor GraphSnapShot(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. Mapval IsomorphicGraphView.map : ('n node -> 'n') -> ('e edge -> 'e') -> ('g -> 'g') -> ('n,'e,'g) graph -> ('n','e','g') graphThe function map is a generalization of the map function on lists. It takes three functions f : 'n node -> 'n g : 'e edge -> 'e h : 'g -> g'and a graph as arguments. It computes the view where Singletonval SingletonGraphView.singleton_view : ('n,'e,'g) graph -> node_id -> ('n,'e,'g) graphFunction singleton_view takes a graph and a node id (which must exists in ) and return an edge-free graph with only one node (). This view is opaque. Node id renamingval RenamedGraphView.rename_view : int -> ('n,'e,'g) graph -> ('n','e','g') graphThe function rename_view takes an integer and a graph and create a fully update transparent view where all node ids are incremented by . Formally, given graph it computes the view where Union and Sumval UnionGraphView.union_view : ('g * 'g') -> 'g'') -> ('n,'e,'g) graph * ('n,'e,'g') graph -> ('n','e','g'') graph GraphCombinations.unions : ('n,'e,'g) graph list -> ('n,'e,'g) graph GraphCombinations.sum : ('n,'e,'g) graph * ('n,'e,'g) graph -> ('n,'e,'g) graph GraphCombinations.sums : ('n,'e,'g) graph list -> ('n,'e,'g) graphFunction union_view takes as arguments a function , and two graphs and , it computes the union of these graphs. Formally, where Simple Graph Viewval SimpleGraph.simple_graph : (node_id * node_id * 'e list -> 'e) -> ('n,'e,'g) graph -> ('n,'e,'g) graphFunction simple_graph takes a merge function and a multi-graph 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 and target and with labels , are replaced by the edge in the view, where . The function is assumed to satisfy the equality for all , and . No Entry or No Exitval 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. Subgraphsval SubgraphView.subgraph_view : node_id list -> ('e edge -> bool) -> ('n,'e,'g) graph -> (n','e','g') graphThe function subgraph_view takes as arguments a set of node ids , an edge predicate and a graph . It returns a view in which only the visible nodes are and the only visible edges are those that satisfy and with sources and targets in . must be a subset of .
Traceval TraceView.trace_view : node_id list -> ('n,'e,'g) graph -> ('n','e','g') graph
Figure Trace illustrates this concept graphically. Here, the trace view is formed from the nodes A, C, D, F and 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 A is considered to be both since it exits from G and enters into A. Acyclic Subgraphval AcyclicSubgraphView.acyclic_view : node_id list -> ('n,'e,'g) graph -> ('n,'e,'g) graph
Start and Stopval StartStopView.start_stop_view : { start : 'n node, stop : 'n node, edges : 'e edge list } -> ('n,'e,'g) graph -> ('n','e','g') graphThe function start_stop_view Single-Entry/Multiple-ExitsSingleEntryMultipleExit.SEME exit : 'n node -> ('n,'e,'g) graph -> ('n,'e,'g) graphThe function SEME converts a single-entry/multiple-exits graph into a single entry/single exit graph. It takes an exit node and a graph and returns a view . Suppose is an exit edge in . In view this edge is replaced by a new normal edge and a new exit edge . Thus becomes the sole exit node in the new view. Behavioral ViewsBehavioral PrimitivesFigure Behavioral Primitives lists the set of behavioral primitives defined in structure GraphWrappers. These functions allow the user to attach an action to a mutator method such that whenever is invoked so does . Given a graph , the combinatordo_before_ : f -> ('n,'e,'g) graph -> ('n,'e,'g) graphreturns a view such that whenever method is invoked in , the function is called. Similarly, the combinator do_after_ : f -> ('n,'e,'g) graph -> ('n,'e,'g) graphcreates a new view such that the function is called after the method is invoked.
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.
|