chord.util.graph
Interface IGraph<Node>

Type Parameters:

Node - The type of the graph's nodes.

All Superinterfaces:

java.io.Serializable

All Known Subinterfaces:

ICICG, ICSCG, ILabeledGraph<Node,Label>, IMutableGraph<Node>, IMutableLabeledGraph<Node,Label>

All Known Implementing Classes:

AbstractGraph, CICG, CSCG, MutableGraph, MutableLabeledGraph

public interface IGraph<Node>
extends java.io.Serializable

Specification of an immutable, unlabeled, directed graph with useful operations on it.

This interface must be used when it is desirable to provide an immutable view of an unlabeled, directed graph to clients even though the underlying implementation may be that of a mutable graph.

Classes implementing this interface are:

• MutableGraph, a complete implementation that provides both, the useful operations and a representation of the graph.
• AbstractGraph, a partial implementation that provides the useful operations but leaves the representation of the graph unspecified.

Author:

Mayur Naik (mhn@cs.stanford.edu)

Method Summary

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>	getNodes() Provides all nodes in this 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).
java.util.Set<Node>	getPreds(Node node) Provides all immediate predecessors of a given node in this graph.
java.util.Set<Node>	getRoots() Provides all root nodes of this graph.
ShortestPathBuilder<Node>	getShortestPathsBuilder(Node srcNode, IPathVisitor<Node> visitor)
void	getSimpleCycles(IGraphEntityVisitor<Node> visitor) Computes all simple cycles of this graph.
java.util.Set<Node>	getSuccs(Node node) Provides all immediate successors of a given node in 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.
boolean	hasEdge(Node node1, Node node2) Determines whether this graph contains a given directed edge.
boolean	hasNode(Node node) Determines whether this graph contains a given node.
boolean	hasRoot(Node node) Determines whether this graph contains a given node as a root node.
boolean	isConnected() Determines whether each node in the graph is reachable from some root node.
int	numNodes() Provides the total number of nodes in this graph.
int	numPreds(Node node) Provides the number of immediate predecessors of a given node in this graph.
int	numRoots() Provides the total number of roots of this graph.
int	numSuccs(Node node) Provides the number of immediate successors of a given node in this graph.

Method Detail

hasRoot

boolean hasRoot(Node node)

Determines whether this graph contains a given node as a root node.

Parameters:

node - A node.

Returns:

true if this graph contains the given node as a root node.

hasNode

boolean hasNode(Node node)

Determines whether this graph contains a given node.

Parameters:

node - A node.

Returns:

true if this graph contains the given node.

hasEdge

boolean hasEdge(Node node1,
                Node node2)

Determines whether this graph contains a given directed edge.

Parameters:

node1 - A node.

node2 - A node.

Returns:

true if this graph contains a directed edge from node1 to node2.

numRoots

int numRoots()

Provides the total number of roots of this graph.

Returns:

The total number of roots of this graph.

numNodes

int numNodes()

Provides the total number of nodes in this graph.

Returns:

The total number of nodes in this graph.

numPreds

int numPreds(Node node)

Provides the number of immediate predecessors of a given node in this graph.

Parameters:

node - A node.

Returns:

The number of immediate predecessors of the given node, if it exists in this graph, and 0 otherwise.

numSuccs

int numSuccs(Node node)

Provides the number of immediate successors of a given node in this graph.

Parameters:

node - A node.

Returns:

The number of immediate successors of the given node, if it exists in this graph, and 0 otherwise.

getRoots

java.util.Set<Node> getRoots()

Provides all root nodes of this graph.

Returns:

All root nodes of this graph.

getNodes

java.util.Set<Node> getNodes()

Provides all nodes in this graph.

Returns:

All nodes in this graph.

getPreds

java.util.Set<Node> getPreds(Node node)

Provides all immediate predecessors of a given node in this graph.

Parameters:

node - A node.

Returns:

All immediate predecessors of the given node.

getSuccs

java.util.Set<Node> getSuccs(Node node)

Provides all immediate successors of a given node in this graph.

Parameters:

node - A node.

Returns:

All immediate successors of the given node.

isConnected

boolean isConnected()

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

Returns:

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

getNodesInRPO

java.util.List<Node> getNodesInRPO()

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

Returns:

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

getTopSortedSCCs

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.

Returns:

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

getBackEdges

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

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

Returns:

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

hasCycles

boolean hasCycles()

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

Returns:

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

getNodesInCycles

java.util.Set<Node> getNodesInCycles()

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

Returns:

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

getSimpleCycles

void getSimpleCycles(IGraphEntityVisitor<Node> visitor)

Computes all simple cycles of this graph.

Parameters:

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

getNodeMap

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.

Returns:

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

getShortestPathsBuilder

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

getAllPathsBuilder

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