chord.util.graph
Class MutableGraph<Node>

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

Type Parameters:

Node - The type of the graph's nodes.

All Implemented Interfaces:

IGraph<Node>, IMutableGraph<Node>, java.io.Serializable

Direct Known Subclasses:

MutableLabeledGraph

public class MutableGraph<Node>
extends AbstractGraph<Node>
implements IMutableGraph<Node>

Complete implementation of a mutable, unlabeled, directed graph with useful operations on it.

This class must be used by clients who wish to use both, the operations inherited by it (e.g., computing SCCs, ordering nodes in RPO, etc.) and the representation of the graph provided by it.

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

• IGraph for the immutable case, and
• IMutableGraph for the mutable case.

Author:

Mayur Naik (mhn@cs.stanford.edu)

See Also:

Serialized Form

Field Summary

protected java.util.Map<Node,java.util.Set<Node>>	nodeToPreds Map from each node in the graph to the set of all its immediate predecessors.
protected java.util.Map<Node,java.util.Set<Node>>	nodeToSuccs Map from each node in the graph to the set of all its immediate successors.
protected java.util.Set<Node>	roots Set of root nodes of the graph.

Fields inherited from class chord.util.graph.AbstractGraph

cached

Constructor Summary

MutableGraph()
Constructs an empty mutable, unlabeled, directed graph.

MutableGraph(IGraph<Node> graph)
Constructs a mutable, unlabeled directed graph as a copy of the specified graph.

MutableGraph(java.util.Set<Node> roots, java.util.Map<Node,java.util.Set<Node>> nodeToPreds, java.util.Map<Node,java.util.Set<Node>> nodeToSuccs)
Constructs a mutable, unlabeled, directed graph with the provided roots, nodes, and edges.

Method Summary

boolean	bypassNode(Node v) Removes a given node from the graph while preserving edges incident upon it.
void	computeTransitiveClosure() Computes the transitive closure of the graph.
java.util.Set<Node>	getNodes() Provides all nodes in this graph.
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.
java.util.Set<Node>	getSuccs(Node node) Provides all immediate successors of a given node in this graph.
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	insertEdge(Node u, Node v) Inserts a given directed edge into the graph, also inserting the nodes of the edge if they do not exist in the graph.
boolean	insertEdgeStrict(Node u, Node v) Inserts a given directed edge into the graph, presuming that the nodes of the edge exist in the graph.
boolean	insertNode(Node v) Inserts a given node as a non-root node into the graph.
boolean	insertRoot(Node v) Inserts a given node as a root node into the graph.
boolean	insertRootStrict(Node v) Designates a given node in the graph as a 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.
boolean	removeEdge(Node u, Node v) Removes a given directed edge from the graph.
boolean	removeNode(Node v) Removes a given node from the graph along with edges incident upon it.
boolean	removeRootStrict(Node v) Designates a given node in the graph as a non-root node.
boolean	replaceNode(Node oldNode, Node newNode) Replaces a given node in the graph by another given node.
void	union(IGraph<Node> that) Computes the union of this graph with a given directed graph, and updates this graph with the result.
void	validate()

Methods inherited from class chord.util.graph.AbstractGraph

equals, evictCache, getAllPathsBuilder, getBackEdges, getNodeMap, getNodesInCycles, getNodesInRPO, getShortestPathsBuilder, getSimpleCycles, getTopSortedSCCs, hasCycles, hashCode, isConnected, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface chord.util.graph.IGraph

getAllPathsBuilder, getBackEdges, getNodeMap, getNodesInCycles, getNodesInRPO, getShortestPathsBuilder, getSimpleCycles, getTopSortedSCCs, hasCycles, isConnected

Field Detail

roots

protected java.util.Set<Node> roots

Set of root nodes of the graph.

nodeToPreds

protected java.util.Map<Node,java.util.Set<Node>> nodeToPreds

Map from each node in the graph to the set of all its immediate predecessors.

nodeToSuccs

protected java.util.Map<Node,java.util.Set<Node>> nodeToSuccs

Map from each node in the graph to the set of all its immediate successors.

Constructor Detail

MutableGraph

public MutableGraph()

Constructs an empty mutable, unlabeled, directed graph.

MutableGraph

public MutableGraph(IGraph<Node> graph)

Constructs a mutable, unlabeled directed graph as a copy of the specified graph. Any mutable operations performed henceforth on the specified graph do not affect this graph.

MutableGraph

public MutableGraph(java.util.Set<Node> roots,
                    java.util.Map<Node,java.util.Set<Node>> nodeToPreds,
                    java.util.Map<Node,java.util.Set<Node>> nodeToSuccs)

Constructs a mutable, unlabeled, directed graph with the provided roots, nodes, and edges.

If both maps nodeToPreds and nodeToSuccs are null, then an empty graph is constructed.

If both maps nodeToPreds and nodeToSuccs are non-null, then they are checked for consistency, namely, node1 must be specified as an immediate predecessor of node2 in map nodeToPreds iff node2 is specified as an immediate successor of node1 in map nodeToSuccs.

If map nodeToPreds is non-null, then the following three conditions must hold:

• nodeToPreds.keySet() must not contain null (that is, the graph cannot have a null node),
• nodeToPreds.values() must not contain null (that is, the map must specify the set of immediate predecessor nodes of each node in the graph, even if that set is empty, and
• for each node node1 in nodeToPreds.keySet(), each node node2 in nodeToPreds.get(node1) must be contained in nodeToPreds.keySet().

If map nodeToSuccs is non-null, then the following three conditions must hold:

• nodeToSuccs.keySet() must not contain null (that is, the graph cannot have a null node),
• nodeToPreds.values() must not contain null (that is, the map must specify the set of immediate successor nodes of each node in the graph, even if that set is empty, and
• for each node node1 in nodeToSuccs.keySet(), each node node2 in nodeToSuccs.get(node1) must be contained in nodeToSuccs.keySet().

Parameters:

roots - A set of nodes designated as roots of the graph. It may be null, in which case every node in the graph is treated as a root node.

nodeToPreds - A map from each node in the graph to the set of all its immediate predecessor nodes. It may be null.

nodeToSuccs - A map from each node in the graph to the set of all its immediate successor nodes. It may be null.

Method Detail

numRoots

public int numRoots()

Description copied from interface: IGraph

Provides the total number of roots of this graph.

Specified by:

numRoots in interface IGraph<Node>

Returns:

The total number of roots of this graph.

numNodes

public int numNodes()

Description copied from interface: IGraph

Provides the total number of nodes in this graph.

Specified by:

numNodes in interface IGraph<Node>

Returns:

The total number of nodes in this graph.

numPreds

public int numPreds(Node node)

Description copied from interface: IGraph

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

Specified by:

numPreds in interface IGraph<Node>

Parameters:

node - A node.

Returns:

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

numSuccs

public int numSuccs(Node node)

Description copied from interface: IGraph

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

Specified by:

numSuccs in interface IGraph<Node>

Parameters:

node - A node.

Returns:

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

hasRoot

public boolean hasRoot(Node node)

Description copied from interface: IGraph

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

Specified by:

hasRoot in interface IGraph<Node>

Parameters:

node - A node.

Returns:

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

hasNode

public boolean hasNode(Node node)

Description copied from interface: IGraph

Determines whether this graph contains a given node.

Specified by:

hasNode in interface IGraph<Node>

Parameters:

node - A node.

Returns:

true if this graph contains the given node.

hasEdge

public boolean hasEdge(Node node1,
                       Node node2)

Description copied from interface: IGraph

Determines whether this graph contains a given directed edge.

Specified by:

hasEdge in interface IGraph<Node>

Parameters:

node1 - A node.

node2 - A node.

Returns:

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

getRoots

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

Description copied from interface: IGraph

Provides all root nodes of this graph.

Specified by:

getRoots in interface IGraph<Node>

Returns:

All root nodes of this graph.

getNodes

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

Description copied from interface: IGraph

Provides all nodes in this graph.

Specified by:

getNodes in interface IGraph<Node>

Returns:

All nodes in this graph.

getPreds

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

Description copied from interface: IGraph

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

Specified by:

getPreds in interface IGraph<Node>

Parameters:

node - A node.

Returns:

All immediate predecessors of the given node.

getSuccs

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

Description copied from interface: IGraph

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

Specified by:

getSuccs in interface IGraph<Node>

Parameters:

node - A node.

Returns:

All immediate successors of the given node.

insertNode

public boolean insertNode(Node v)

Description copied from interface: IMutableGraph

Inserts a given node as a non-root node into the graph.

Specified by:

insertNode in interface IMutableGraph<Node>

Parameters:

v - The node to be inserted.

Returns:

true if the graph is modified, i.e., if node does not exist in the graph.

insertRoot

public boolean insertRoot(Node v)

Description copied from interface: IMutableGraph

Inserts a given node as a root node into the graph.

Specified by:

insertRoot in interface IMutableGraph<Node>

Parameters:

v - The node to be inserted.

Returns:

true if the graph is modified, i.e., if node does not exist in the graph or is a non-root node in the graph.

insertRootStrict

public boolean insertRootStrict(Node v)

Description copied from interface: IMutableGraph

Designates a given node in the graph as a root node.

Specified by:

insertRootStrict in interface IMutableGraph<Node>

Parameters:

v - A node in the graph.

Returns:

true if the graph is modified, i.e., if node is a non-root node in the graph.

bypassNode

public boolean bypassNode(Node v)

Description copied from interface: IMutableGraph

Removes a given node from the graph while preserving edges incident upon it. This operation removes the following edges from the graph:

 1. for each immed. pred. node1 of node: edge (node1,node)
 2. for each immed. succ. node2 of node: edge (node,node2)
 

This operation inserts the following edges into the graph:

 for each immed. pred. node1 of node such that node1 != node:
         for each immed. succ. node2 of node such that node2 != node:
                 edge (node1,node2)
 

Moreover, if node is a root node, then each of its immediate successors is designated a root node.

Specified by:

bypassNode in interface IMutableGraph<Node>

Parameters:

v - The node to be removed.

Returns:

true if the graph is modified, i.e., if node exists in the graph.

See Also:

IMutableGraph.removeNode(Node)

removeRootStrict

public boolean removeRootStrict(Node v)

Description copied from interface: IMutableGraph

Designates a given node in the graph as a non-root node.

Specified by:

removeRootStrict in interface IMutableGraph<Node>

Parameters:

v - A node in the graph.

Returns:

true if the graph is modified, i.e., if node is a root node in the graph.

removeNode

public boolean removeNode(Node v)

Description copied from interface: IMutableGraph

Removes a given node from the graph along with edges incident upon it.

Specified by:

removeNode in interface IMutableGraph<Node>

Parameters:

v - A node.

Returns:

true if the graph is modified, i.e., if node exists in the graph.

See Also:

IMutableGraph.bypassNode(Node)

replaceNode

public boolean replaceNode(Node oldNode,
                           Node newNode)

Description copied from interface: IMutableGraph

Replaces a given node in the graph by another given node.

Specified by:

replaceNode in interface IMutableGraph<Node>

Parameters:

oldNode - The old node.

newNode - The new node.

Returns:

true if the graph is modified, i.e., if oldNode exists in the graph and newNode is different from it.

insertEdge

public boolean insertEdge(Node u,
                          Node v)

Description copied from interface: IMutableGraph

Inserts a given directed edge into the graph, also inserting the nodes of the edge if they do not exist in the graph.

Specified by:

insertEdge in interface IMutableGraph<Node>

Parameters:

u - The source node of the edge to be inserted.

v - The target node of the edge to be inserted.

Returns:

true if the graph is modified, i.e., if an edge from srcNode to dstNode does not exist in the graph.

insertEdgeStrict

public boolean insertEdgeStrict(Node u,
                                Node v)

Description copied from interface: IMutableGraph

Inserts a given directed edge into the graph, presuming that the nodes of the edge exist in the graph.

Specified by:

insertEdgeStrict in interface IMutableGraph<Node>

Parameters:

u - The source node of the edge to be inserted.

v - The target node of the edge to be inserted.

Returns:

true if the graph is modified, i.e., if an edge from srcNode to dstNode does not exist in the graph.

removeEdge

public boolean removeEdge(Node u,
                          Node v)

Description copied from interface: IMutableGraph

Removes a given directed edge from the graph.

Specified by:

removeEdge in interface IMutableGraph<Node>

Parameters:

u - The source node of the edge to be removed.

v - The target node of the edge to be removed.

Returns:

true if the graph is modified, i.e., if an edge from srcNode to dstNode exists in the graph.

computeTransitiveClosure

public void computeTransitiveClosure()

Computes the transitive closure of the graph. Considers each pair of edges (u,v) and (v,w) in the graph such that u != v != w, and adds edge (u,w) if it is not in the graph. The process terminates after no more edges can be added.

Specified by:

computeTransitiveClosure in interface IMutableGraph<Node>

union

public void union(IGraph<Node> that)

Description copied from interface: IMutableGraph

Computes the union of this graph with a given directed graph, and updates this graph with the result.

Specified by:

union in interface IMutableGraph<Node>

Parameters:

that - A directed graph. It must be non-null.

validate

public void validate()