|
|||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||
See:
Description
| Interface Summary | |
|---|---|
| BasicBlock<Vertex> | BasicBlock is a straight-line sequence of
vertices. |
| ForwardNavigator<Vertex> | ForwardNavigator is a forward-only graph navigator:
given a vertex, it returns its successors in the graph. |
| Navigator<Vertex> | The Navigator interface allows graph algorithms to
detect (and use) the arcs from and to a certain vertex. |
| Class Summary | |
|---|---|
| ArcBasedDiGraph<Vertex> | Digraph based on a list of arcs. |
| BasicBlockDiGraph<Vertex> | A BasicBlockDiGraph is a basic block representation of
a directed graph. |
| BinTreeNav<T> | BinTreeNav models the arcs of a binary tree. |
| BinTreeUtil | BinTreeUtil contains utilities for binary trees. |
| DiGraph<Vertex> | DiGraph models a directed graph. |
| GraphUtil | GraphUtil contains various graph utilities. |
| LDiGraph<Vertex,Label> | LDiGraph models a labeled directed graph. |
| LDiGraph.LForwardNavigator<Vertex,Label> | Forward iterator into a labeled graph. |
| LDiGraph.LNavigator<Vertex,Label> | Bidirectional iterator into a labeled graph. |
| SCComponent<Vertex> | SCComponent models a strongly-connected
component of a directed graph: a set of vertices such that
there is a path between any two of them. |
| TopSortedCompDiGraph<Vertex> | TopSortedCompDiGraph is a topologically-sorted
component digraph. |
Graph-related classes and algorithms. It is surprising how many compiler algorithms can be described in terms of pure graph algorithms, without any additional knowledge about the instructions of the analyzed program besides their graph structure. This package attempts to provide a very general library that will eliminate the need to reimplement these algorithms for every new compiler.
Graph model: We model a directed graph (DiGraph) as a set of root vertices and a
Navigator that describes the arcs of
the graph. The navigator is an iterator over the directed graph:
given a vertex v, it gives v's direct
successors (i.e., vertices pointed to by arcs that start in
v), and (optionally), v's direct
predecessors. The digraph consists of all the vertices that can be
reached from the roots, by following forward arcs given by the
navigator. This design allows the use of our library even for graphs
whose arcs are not explicitly stored in the vertices. As an example,
consider a call graph: the caller-callee relation is not usually
stored at the level of each procedure; still, the call graph is a real
directed graph, and we want to be able to apply all graph algorithms
to it.
A note on dynamic graphs: Notice that the simple graph model described above has no mechanism for informing a graph when a mutation is performed (e.g., when an arc is added). For example, if one computes the component graph of a digraph and next the underlying digraph changes, these changes are not propagated to the component graph. The reasons we don't have such a mechanism are: (1) complexity (hard to program it and hard to get it right); (2) cost; and (3) we want our library to work with many graph-like structures that already exist. It is the user's responsibility to make sure that a graph does not change in the middle of an operation on it. E.g., a graph should not change while we compute its component graph; if the original graph changes and we need to update the component graph, we have to recompute it. This strategy is easy to implement and test, and also seems to work well if the digraph changes come in stages (as it usually happens in a compiler: we alternate stages of analysis and optimization).
Things implemented so far:
DiGraph (unlabeled digraphs) and
LDiGraph (labeled digraphs).
DiGraph.union), dfs traversals (DiGraph.dfs), reachability (DiGraph.transitiveSucc), shortest
paths (in terms of number of edges, no weighted edges yet) (DiGraph.findPath), etc.
SCComponent): given a digraph, we can construct its topologically
sorted component digraph, a digraph whose vertices are the SCCs of the
original grap; see TopSortedCompDiGraph for more details.
BasicBlockDiGraph. A basic block
(BasicBlock) is a straight-line
sequences of digraph vertices.
Things we would like to see implemented in the future:
|
|||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||