chord.util.graph
Class MutableLabeledGraph<Node,Label>

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

Type Parameters:

Node - The type of the graph's nodes.

Label - The type of the labels on the graph's edges.

All Implemented Interfaces:

IGraph<Node>, ILabeledGraph<Node,Label>, IMutableGraph<Node>, IMutableLabeledGraph<Node,Label>, java.io.Serializable

public class MutableLabeledGraph<Node,Label>
extends MutableGraph<Node>
implements IMutableLabeledGraph<Node,Label>

Complete implementation of a mutable, labeled, 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 labeled, directed graph is immutable or mutable. The appropriate interface must be used to convey these characteristics, namely:

• ILabeledGraph for the immutable case, and
• IMutableLabeledGraph for the mutable case.

Author:

Mayur Naik (mhn@cs.stanford.edu)

See Also:

Serialized Form

Field Summary

protected java.util.Map<Pair<Node,Node>,java.util.Set<Label>>

nodesToLabels Map from each pair of nodes (u,v) to the set containing each label l such that u->v is an edge labeled l in the graph.

Fields inherited from class chord.util.graph.MutableGraph

nodeToPreds, nodeToSuccs, roots

Fields inherited from class chord.util.graph.AbstractGraph

cached

Constructor Summary

MutableLabeledGraph()
Constructs an empty mutable, labeled, directed graph.

MutableLabeledGraph(java.util.Set<Node> roots, java.util.Map<Node,java.util.Set<Node>> nodeToPreds, java.util.Map<Node,java.util.Set<Node>> nodeToSuccs, java.util.Map<Pair<Node,Node>,java.util.Set<Label>> nodesToLabels)
Constructs a mutable, labeled, directed graph with the specified roots, nodes, edges, and labels on edges.

Method Summary

boolean	bypassNode(Node node) Removes a given node from the graph while preserving edges incident upon it.
java.util.Set<Label>	getLabels(Node srcNode, Node dstNode) Provides the set of all labels on a given directed edge in the graph.
boolean	insertLabel(Node srcNode, Node dstNode, Label label) Inserts a given label on a given directed edge in the graph, also inserting the edge and the nodes of the edge if they do not exist in the graph.
boolean	removeEdge(Node srcNode, Node dstNode) Removes a given directed edge from the graph.
boolean	removeLabel(Node srcNode, Node dstNode, Label label) Removes a given label from a given directed edge in the graph.
boolean	removeNode(Node node) Removes a given node from the graph along with edges incident upon it.
boolean	replaceNode(Node oldNode, Node newNode) Replaces a given node in the graph by another given node.
java.lang.String	toString()
void	union(IGraph<Node> graph) 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.MutableGraph

computeTransitiveClosure, getNodes, getPreds, getRoots, getSuccs, hasEdge, hasNode, hasRoot, insertEdge, insertEdgeStrict, insertNode, insertRoot, insertRootStrict, numNodes, numPreds, numRoots, numSuccs, removeRootStrict

Methods inherited from class chord.util.graph.AbstractGraph

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

Methods inherited from class java.lang.Object

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

Methods inherited from interface chord.util.graph.IMutableGraph

computeTransitiveClosure, insertEdge, insertEdgeStrict, insertNode, insertRoot, insertRootStrict, removeRootStrict

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

Field Detail

nodesToLabels

protected java.util.Map<Pair<Node,Node>,java.util.Set<Label>> nodesToLabels

Map from each pair of nodes (u,v) to the set containing each label l such that u->v is an edge labeled l in the graph.

Constructor Detail

MutableLabeledGraph

public MutableLabeledGraph()

Constructs an empty mutable, labeled, directed graph.

MutableLabeledGraph

public MutableLabeledGraph(java.util.Set<Node> roots,
                           java.util.Map<Node,java.util.Set<Node>> nodeToPreds,
                           java.util.Map<Node,java.util.Set<Node>> nodeToSuccs,
                           java.util.Map<Pair<Node,Node>,java.util.Set<Label>> nodesToLabels)

Constructs a mutable, labeled, directed graph with the specified roots, nodes, edges, and labels on edges.

Parameters:

roots -

nodeToPreds -

nodeToSuccs -

nodesToLabels -

Method Detail

validate

public void validate()

Overrides:

validate in class MutableGraph<Node>

toString

public java.lang.String toString()

Overrides:

toString in class AbstractGraph<Node>

insertLabel

public boolean insertLabel(Node srcNode,
                           Node dstNode,
                           Label label)

Description copied from interface: IMutableLabeledGraph

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

Specified by:

insertLabel in interface IMutableLabeledGraph<Node,Label>

Parameters:

srcNode - The source node of the edge.

dstNode - The target node of the edge.

label - The label to be inserted.

Returns:

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

removeLabel

public boolean removeLabel(Node srcNode,
                           Node dstNode,
                           Label label)

Description copied from interface: IMutableLabeledGraph

Removes a given label from a given directed edge in the graph.

Specified by:

removeLabel in interface IMutableLabeledGraph<Node,Label>

Parameters:

srcNode - The source node of the edge.

dstNode - The target node of the edge.

label - The label to be removed.

Returns:

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

getLabels

public java.util.Set<Label> getLabels(Node srcNode,
                                      Node dstNode)

Description copied from interface: ILabeledGraph

Provides the set of all labels on a given directed edge in the graph.

Specified by:

getLabels in interface ILabeledGraph<Node,Label>

Parameters:

srcNode - The source node of the edge.

dstNode - The target node of the edge.

Returns:

The set of all labels on the edge from srcNode to dstNode in the graph. It is the empty set if either node does not exist, the edge does not exist, or no labels exist on the edge in the graph.

removeNode

public boolean removeNode(Node node)

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>

Overrides:

removeNode in class MutableGraph<Node>

Parameters:

node - A node.

Returns:

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

See Also:

IMutableGraph.bypassNode(Node)

bypassNode

public boolean bypassNode(Node node)

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>

Overrides:

bypassNode in class MutableGraph<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:

IMutableGraph.removeNode(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>

Overrides:

replaceNode in class MutableGraph<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.

removeEdge

public boolean removeEdge(Node srcNode,
                          Node dstNode)

Description copied from interface: IMutableGraph

Removes a given directed edge from the graph.

Specified by:

removeEdge in interface IMutableGraph<Node>

Overrides:

removeEdge in class MutableGraph<Node>

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.

union

public void union(IGraph<Node> graph)

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>

Overrides:

union in class MutableGraph<Node>

Parameters:

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