chord.util.graph
Interface IMutableGraph<Node>

Type Parameters:

Node - The type of the graph's nodes.

All Superinterfaces:

IGraph<Node>, java.io.Serializable

All Known Subinterfaces:

IMutableLabeledGraph<Node,Label>

All Known Implementing Classes:

MutableGraph, MutableLabeledGraph

public interface IMutableGraph<Node>
extends IGraph<Node>

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

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

boolean	bypassNode(Node node) Removes a given node from the graph while preserving edges incident upon it.
void	computeTransitiveClosure() Computes the transitive closure of the graph and updates it with the result.
boolean	insertEdge(Node srcNode, Node dstNode) 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 srcNode, Node dstNode) Inserts a given directed edge into the graph, presuming that the nodes of the edge exist in the graph.
boolean	insertNode(Node node) Inserts a given node as a non-root node into the graph.
boolean	insertRoot(Node node) Inserts a given node as a root node into the graph.
boolean	insertRootStrict(Node node) Designates a given node in the graph as a root node.
boolean	removeEdge(Node srcNode, Node dstNode) Removes a given directed edge from the graph.
boolean	removeNode(Node node) Removes a given node from the graph along with edges incident upon it.
boolean	removeRootStrict(Node node) 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> graph) Computes the union of this graph with a given directed graph, and updates this graph with the result.

Methods inherited from interface chord.util.graph.IGraph

getAllPathsBuilder, getBackEdges, getNodeMap, getNodes, getNodesInCycles, getNodesInRPO, getPreds, getRoots, getShortestPathsBuilder, getSimpleCycles, getSuccs, getTopSortedSCCs, hasCycles, hasEdge, hasNode, hasRoot, isConnected, numNodes, numPreds, numRoots, numSuccs

Method Detail

insertNode

boolean insertNode(Node node)

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

Parameters:

node - The node to be inserted.

Returns:

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

insertRoot

boolean insertRoot(Node node)

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

Parameters:

node - 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

boolean insertRootStrict(Node node)

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

Parameters:

node - A node in the graph.

Returns:

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

Throws:

java.lang.RuntimeException - if node does not exist in the graph.

bypassNode

boolean bypassNode(Node node)

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.

Parameters:

node - The node to be removed.

Returns:

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

See Also:

removeNode(Node)

removeRootStrict

boolean removeRootStrict(Node node)

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

Parameters:

node - A node in the graph.

Returns:

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

Throws:

java.lang.RuntimeException - if node does not exist in the graph.

removeNode

boolean removeNode(Node node)

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

Parameters:

node - A node.

Returns:

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

See Also:

bypassNode(Node)

replaceNode

boolean replaceNode(Node oldNode,
                    Node newNode)

Replaces a given node in the graph by another given 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

boolean insertEdge(Node srcNode,
                   Node dstNode)

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

Parameters:

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

dstNode - 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

boolean insertEdgeStrict(Node srcNode,
                         Node dstNode)

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

Parameters:

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

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

Throws:

java.lang.RuntimeException - if srcNode or dstNode does not exist in the graph.

removeEdge

boolean removeEdge(Node srcNode,
                   Node dstNode)

Removes a given directed edge from the graph.

Parameters:

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

dstNode - 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

void computeTransitiveClosure()

Computes the transitive closure of the graph and updates it with the result.

union

void union(IGraph<Node> graph)

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

Parameters:

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