

PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 
See:
Description
Interface Summary  

BasicBlock<Vertex>  BasicBlock is a straightline 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 forwardonly 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 stronglyconnected
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 topologicallysorted
component digraph. 
Graphrelated 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 bidirectional 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 callercallee 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 bidirectional
and forwardonly
navigators. The explanation is that we can produce one kind of
navigators based on the other one: any bidirectional 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 bidirectional navigator.
If possible, the user can give a bidirectional navigator and spare
the cost of constructing one based on a forwardonly 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 graphlike 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 straightline
sequences of digraph vertices.
Things we would like to see implemented in the future:


PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 