chord.util.graph
Class AbstractGraph<Node>

java.lang.Object
  chord.util.graph.AbstractGraph<Node>

Type Parameters:

Node - The type of the graph's nodes.

All Implemented Interfaces:

IGraph<Node>, java.io.Serializable

Direct Known Subclasses:

CICG, CSCG, MutableGraph

public abstract class AbstractGraph<Node>
extends java.lang.Object
implements IGraph<Node>

Partial implementation of a directed graph that provides various operations on the graph that are useful for program analysis (e.g., computing SCCs, ordering nodes in RPO, etc.) but leaves the representation of the graph itself unspecified.

This class must be extended by clients who wish to use the various operations provided by it but want to provide their own representation of the graph.

This class must be used regardless of whether the desired kind of directed graph is mutable or immutable, and labeled or unlabeled. The appropriate interface must be used to convey these characteristics, namely:

• IGraph for the immutable, unlabeled case,
• ILabeledGraph for the immutable, labeled case,
• IMutableGraph for the mutable, unlabeled case, and
• IMutableLabeledGraph for the mutable, labeled case

Author:

Mayur Naik (mhn@cs.stanford.edu)

See Also:

Serialized Form

Field Summary

protected boolean

cached

Constructor Summary

AbstractGraph()

Method Summary

boolean	equals(java.lang.Object o)
protected void	evictCache()
AllPathsBuilder<Node>	getAllPathsBuilder(Node srcNode, IPathVisitor<Node> visitor, int maxPathWidth, int maxPathDepth)
java.util.Set<Pair<Node,Node>>	getBackEdges() Provides all back edges in a depth-first traversal of the graph reachable from the root nodes.
IndexMap<Node>	getNodeMap() Provides a map from each node in this graph to a unique arbitrary integer in the range [0..N] where N is the total number of nodes in the graph.
java.util.Set<Node>	getNodesInCycles() Provides all nodes of the graph reachable from the root nodes that are contained in cycles.
java.util.List<Node>	getNodesInRPO() Provides all nodes in the graph reachable from the root nodes, ordered in Reverse Post Order (RPO).
ShortestPathBuilder<Node>	getShortestPathsBuilder(Node srcNode, IPathVisitor<Node> visitor)
void	getSimpleCycles(IGraphEntityVisitor<Node> visitor) Computes all simple cycles of this graph.
java.util.List<java.util.Set<Node>>	getTopSortedSCCs() Provides the list of Strongly Connected Components (SCCs) of the graph reachable from its root nodes, sorted in topological order.
boolean	hasCycles() Determines whether the graph reachable from the root nodes contains any cycles.
int	hashCode()
boolean	isConnected() Determines whether each node in the graph is reachable from some root node.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface chord.util.graph.IGraph

getNodes, getPreds, getRoots, getSuccs, hasEdge, hasNode, hasRoot, numNodes, numPreds, numRoots, numSuccs

Field Detail

cached

protected boolean cached

Constructor Detail

AbstractGraph

public AbstractGraph()

Method Detail

evictCache

protected void evictCache()

isConnected

public boolean isConnected()

Description copied from interface: IGraph

Determines whether each node in the graph is reachable from some root node.

Specified by:

isConnected in interface IGraph<Node>

Returns:

true if each node in the graph is reachable from some root node.

getNodesInRPO

public java.util.List<Node> getNodesInRPO()

Description copied from interface: IGraph

Provides all nodes in the graph reachable from the root nodes, ordered in Reverse Post Order (RPO).

Specified by:

getNodesInRPO in interface IGraph<Node>

Returns:

All nodes in the graph reachable from the root nodes, ordered in RPO.

getTopSortedSCCs

public java.util.List<java.util.Set<Node>> getTopSortedSCCs()

Description copied from interface: IGraph

Provides the list of Strongly Connected Components (SCCs) of the graph reachable from its root nodes, sorted in topological order.

Specified by:

getTopSortedSCCs in interface IGraph<Node>

Returns:

The list of SCCs of the graph reachable from its root nodes, sorted in topological order.

getBackEdges

public java.util.Set<Pair<Node,Node>> getBackEdges()

Description copied from interface: IGraph

Provides all back edges in a depth-first traversal of the graph reachable from the root nodes.

Specified by:

getBackEdges in interface IGraph<Node>

Returns:

All back edges in a depth-first traversal of the graph reachable from its root nodes.

hasCycles

public boolean hasCycles()

Description copied from interface: IGraph

Determines whether the graph reachable from the root nodes contains any cycles.

Specified by:

hasCycles in interface IGraph<Node>

Returns:

true if the graph reachable from the root nodes contains any cycles.

getNodesInCycles

public java.util.Set<Node> getNodesInCycles()

Description copied from interface: IGraph

Provides all nodes of the graph reachable from the root nodes that are contained in cycles.

Specified by:

getNodesInCycles in interface IGraph<Node>

Returns:

All nodes of the graph reachable from the root nodes that are contained in cycles.

getSimpleCycles

public void getSimpleCycles(IGraphEntityVisitor<Node> visitor)

Description copied from interface: IGraph

Computes all simple cycles of this graph.

Specified by:

getSimpleCycles in interface IGraph<Node>

Parameters:

visitor - A visitor over the graph's simple cycles.

getShortestPathsBuilder

public ShortestPathBuilder<Node> getShortestPathsBuilder(Node srcNode,
                                                         IPathVisitor<Node> visitor)

Specified by:

getShortestPathsBuilder in interface IGraph<Node>

getAllPathsBuilder

public AllPathsBuilder<Node> getAllPathsBuilder(Node srcNode,
                                                IPathVisitor<Node> visitor,
                                                int maxPathWidth,
                                                int maxPathDepth)

Specified by:

getAllPathsBuilder in interface IGraph<Node>

getNodeMap

public IndexMap<Node> getNodeMap()

Description copied from interface: IGraph

Provides a map from each node in this graph to a unique arbitrary integer in the range [0..N] where N is the total number of nodes in the graph.

Specified by:

getNodeMap in interface IGraph<Node>

Returns:

A map from each node in the graph to a unique arbitrary integer.

equals

public boolean equals(java.lang.Object o)

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object