|
|||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||
See:
Description
| Interface Summary | |
|---|---|
| BasicBlock<Vertex> | BasicBlock is a straight-line sequence of
vertices. |
| BiDiNavigator<Vertex> | The BiDiNavigator interface allows graph algorithms to
detect (and use) the arcs from and to a certain vertex. |
| ForwardNavigator<Vertex> | ForwardNavigator is a forward-only graph navigator:
given a vertex, it returns its successors in the graph. |
| Class Summary | |
|---|---|
| ArcBasedDiGraph<Vertex> | Digraph based on a list of arcs. |
| BasicBlockDiGraph<Vertex> | A BasicBlockDiGraph is a basic block representation of
a directed graph. |
| BinTreeNavigator<T> | BinTreeNavigator models the arcs of a binary tree. |
| BinTreeUtil | BinTreeUtil is a wrapper for binary tree utilities. |
| DiGraph<Vertex> | DiGraph models a directed graph. |
| GraphUtil | GraphUtil is a wrapper for various graph utilities. |
| LabeledDiGraph<Vertex,Label> | LabeledDiGraph models a labeled directed graph. |
| LabeledDiGraph.LabeledBiDiNavigator<Vertex,Label> | Bidirectional iterator into a labeled graph. |
| LabeledDiGraph.LabeledForwardNavigator<Vertex,Label> | Forward 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 (in the case of a bi-directional navigator),
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.
[ The graph algorithms work with both bi-directional and forward-only
navigators. The explanation is that we can produce one kind of
navigators based on the other one: any bi-directional navigator is
trivially a forward one; conversely, given a forward navigator and a
set of roots, we can traverse the whole graph, &discover& the
predecessors of each vertex, and construct a bi-directional navigator.
If possible, the user can give a bi-directional navigator and spare
the cost of constructing one based on a forward-only navigator. ]
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
LabeledDiGraph (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 | ||||||||