Package jpaul.Graphs

Graph-related classes and algorithms.


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.

Package jpaul.Graphs Description

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:

Things we would like to see implemented in the future:

Alexandru Salcianu -

Copyright 2005 Alexandru Salcianu -