org.jikesrvm.compilers.opt.util

Class DFSenumerateByFinish

java.lang.Object

org.jikesrvm.compilers.opt.util.Stack<GraphNode>

org.jikesrvm.compilers.opt.util.DFSenumerateByFinish

All Implemented Interfaces:

Iterable<GraphNode>, Enumeration<GraphNode>

Direct Known Subclasses:

FilteredDFSenumerateByFinish, ReverseDFSenumerateByFinish

public class DFSenumerateByFinish
extends Stack<GraphNode>
implements Enumeration<GraphNode>

This class implements depth-first search over a Graph, return an enumeration of the nodes of the graph in order of increasing finishing time. This class follows the outNodes of the graph nodes to define the graph, but this behavior can be changed by overriding the getConnected method.

Field Summary

Fields

Modifier and Type	Field and Description
GraphNode	currentRoot While a depth-first enumeration is in progress, this field holds the current root node, i.e. the current bottom of the search stack (assuming stacks grow upward).
private Enumeration<GraphNode>	e an enumeration of all nodes to search from
private List<Enumeration<GraphNode>>	info an enumeration of child nodes for each node being searched
private GraphNode	theNextElement the current next element in finishing time order

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	DFSenumerateByFinish(Graph net) Construct a depth-first enumerator across all the nodes of a graph.
	DFSenumerateByFinish(Graph net, Enumeration<GraphNode> nodes) Construct a depth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.

Method Summary

Modifier and Type	Method and Description
protected Enumeration<GraphNode>	getConnected(GraphNode n) get the out edges of a given node
boolean	hasMoreElements() Return whether there are any more nodes left to enumerate.
GraphNode	nextElement() Find the next graph node in finishing time order.

Methods inherited from class org.jikesrvm.compilers.opt.util.Stack

compare, copy, empty, getTOS, isEmpty, iterator, peek, pop, push, shallowCopy, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

currentRoot

public GraphNode currentRoot

While a depth-first enumeration is in progress, this field holds the current root node, i.e. the current bottom of the search stack (assuming stacks grow upward). This is used primarily when constructing strongly connected components.

theNextElement

private GraphNode theNextElement

the current next element in finishing time order

e

private final Enumeration<GraphNode> e

an enumeration of all nodes to search from

info

private final List<Enumeration<GraphNode>> info

an enumeration of child nodes for each node being searched

Constructor Detail

DFSenumerateByFinish

protected DFSenumerateByFinish(Graph net)

Construct a depth-first enumerator across all the nodes of a graph.

Parameters:

net - the graph whose nodes to enumerate

DFSenumerateByFinish

public DFSenumerateByFinish(Graph net,
                            Enumeration<GraphNode> nodes)

Construct a depth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.

Parameters:

net - the graph whose nodes to enumerate

nodes - the set of nodes from which to start searching

Method Detail

hasMoreElements

public boolean hasMoreElements()

Return whether there are any more nodes left to enumerate.

Specified by:

hasMoreElements in interface Enumeration<GraphNode>

Returns:

true if there nodes left to enumerate.

nextElement

public GraphNode nextElement()

Find the next graph node in finishing time order.

Specified by:

nextElement in interface Enumeration<GraphNode>

Returns:

the next graph node in finishing time order.

See Also:

nextElement()

getConnected

protected Enumeration<GraphNode> getConnected(GraphNode n)

get the out edges of a given node

Parameters:

n - the node of which to get the out edges

Returns:

the out edges