jpaul.Graphs
Class BasicBlockDiGraph<Vertex>

java.lang.Object
  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.

Version:
$Id: BasicBlockDiGraph.java,v 1.10 2006/03/14 02:29:31 salcianu Exp $
Author:
Alexandru Salcianu - salcianu@alum.mit.edu
See Also:
BasicBlock

Field Summary
 
Fields inherited from class jpaul.Graphs.DiGraph
CACHING
 
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

BasicBlockDiGraph

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

Method Detail

getBiDiNavigator

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.

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

getRoots

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>>

getBB

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


Copyright 2005 Alexandru Salcianu - salcianu@alum.mit.edu