jpaul.Graphs
Class BasicBlockDiGraph<Vertex>

java.lang.Object
  jpaul.Graphs.DiGraph<BasicBlock<Vertex>>
      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.7 2005/10/31 22:30:12 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)
Navigator<BasicBlock<Vertex>>	getNavigator() 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

constructNavigator, dfs, diGraph, diGraph, findPath, findPath, forAllVertices, getComponentDiGraph, getForwardNavigator, numArcs, numVertices, reverseDiGraph, subDiGraph, transitivePred, transitivePred, transitiveSucc, transitiveSucc, union, vertices

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, 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

getNavigator

public Navigator<BasicBlock<Vertex>> getNavigator()

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 getNavigator and getForwardNavigator.

Overrides:

getNavigator in class DiGraph<BasicBlock<Vertex>>

Returns:

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

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