Class BasicBlockDiGraph<Vertex>

  extended by jpaul.Graphs.DiGraph<BasicBlock<Vertex>>
      extended by jpaul.Graphs.BasicBlockDiGraph<Vertex>

public class BasicBlockDiGraph<Vertex>
extends DiGraph<BasicBlock<Vertex>>

A BasicBlockDiGraph is a basic block representation of a directed graph. The vertices of a BasicBlockDiGraph are (maximal) BasicBlocks made up of vertices of the original digraph. The arcs are induced by the arcs of the original digraph.

$Id:,v 1.10 2006/03/14 02:29:31 salcianu Exp $
Alexandru Salcianu -
See Also:

Field Summary
Fields inherited from class jpaul.Graphs.DiGraph
Constructor Summary
BasicBlockDiGraph(DiGraph<Vertex> diGraph)
          Creates a BasicBlockDiGraph representation for diGraph.
Method Summary
 BasicBlock<Vertex> getBB(Vertex v)
 BiDiNavigator<BasicBlock<Vertex>> getBiDiNavigator()
          Returns the (bi-directional) navigator for this digraph.
 java.util.Collection<BasicBlock<Vertex>> getRoots()
          Returns the roots of this directed graph.
Methods inherited from class jpaul.Graphs.DiGraph
constructBiDiNavigator, dfs, dfs2, diGraph, diGraph, findPath, findPath, findPath, forAllVertices, getComponentDiGraph, getForwardNavigator, numArcs, numVertices, reverseDiGraph, subDiGraph, toString, transitivePred, transitivePred, transitivePredWithFrontier, transitiveSucc, transitiveSucc, transitiveSuccWithFrontier, union, vertices
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail


public BasicBlockDiGraph(DiGraph<Vertex> diGraph)
Creates a BasicBlockDiGraph representation for diGraph. Complexity: linear in the size (vertices + arcs) of diGraph

Method Detail


public BiDiNavigator<BasicBlock<Vertex>> getBiDiNavigator()
Description copied from class: DiGraph
Returns the (bi-directional) navigator for this digraph. The default implementation gets the forward navigator by calling getForwardNavigator, explores the entire digraph and constructs the predecessor relation. Clearly, this is quite costly, and does not terminate for infinite digraphs.

Note: You MUST overwrite at least one of getBiDiNavigator and getForwardNavigator.

getBiDiNavigator in class DiGraph<BasicBlock<Vertex>>
BiDiNavigator for this BasicBlockDiGraph. Complexity: O(1).


public java.util.Collection<BasicBlock<Vertex>> getRoots()
Description copied from class: DiGraph
Returns the roots of this directed graph. By "roots of a digraph" we mean any set of vertices such that one can explore the entire graph by (transitively) navigating on their outgoing arcs (using the next method of the navigator). Notice that this set is not uniquely defined; also, it is OK to return ALL the vertices from the digraph. The caller is not supposed to mutate the returned collection.

Specified by:
getRoots in class DiGraph<BasicBlock<Vertex>>


public BasicBlock<Vertex> getBB(Vertex v)
The basic block that the vertex v belongs to, or null if no such basic block exists. Complexity: O(1).

Copyright 2005 Alexandru Salcianu -