soot.toolkits.graph
Class HashMutableDirectedGraph

java.lang.Object
  soot.toolkits.graph.HashMutableDirectedGraph

All Implemented Interfaces:

Iterable, DirectedGraph, MutableDirectedGraph

Direct Known Subclasses:

HashReversibleGraph, MemoryEfficientGraph

public class HashMutableDirectedGraph
extends Object
implements MutableDirectedGraph

HashMap based implementation of a MutableBlockGraph.

Field Summary

protected Chain	heads
protected HashMap<Object,LinkedHashSet<Object>>	nodeToPreds
protected HashMap<Object,LinkedHashSet<Object>>	nodeToSuccs
protected Chain	tails

Constructor Summary

HashMutableDirectedGraph()

Method Summary

void	addEdge(Object from, Object to) Adds an edge to the graph between 2 nodes.
void	addNode(Object node) Adds a node to the graph.
void	clearAll() Removes all nodes and edges.
Object	clone()
boolean	containsEdge(Object from, Object to)
boolean	containsNode(Object node)
List	getHeads() Returns a list of entry points for this graph.
List<Object>	getNodes()
List	getPredsOf(Object s) Returns a list of predecessors for the given node in the graph.
Set	getPredsOfAsSet(Object s) Same as getPredsOf(Object) but returns a set.
List	getSuccsOf(Object s) Returns a list of successors for the given node in the graph.
Set	getSuccsOfAsSet(Object s) Same as getSuccsOf(Object) but returns a set.
List	getTails() Returns a list of exit points for this graph.
Iterator	iterator() Returns an iterator for the nodes in this graph.
void	printGraph()
void	removeEdge(Object from, Object to) Removes an edge between 2 nodes in the graph.
void	removeNode(Object node) Removes a node from the graph.
int	size() Returns the node count for this graph.

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

nodeToPreds

protected HashMap<Object,LinkedHashSet<Object>> nodeToPreds

nodeToSuccs

protected HashMap<Object,LinkedHashSet<Object>> nodeToSuccs

heads

protected Chain heads

tails

protected Chain tails

Constructor Detail

HashMutableDirectedGraph

public HashMutableDirectedGraph()

Method Detail

clearAll

public void clearAll()

Removes all nodes and edges.

clone

public Object clone()

Overrides:

clone in class Object

getHeads

public List getHeads()

Description copied from interface: DirectedGraph

Returns a list of entry points for this graph.

Specified by:

getHeads in interface DirectedGraph

getTails

public List getTails()

Description copied from interface: DirectedGraph

Returns a list of exit points for this graph.

Specified by:

getTails in interface DirectedGraph

getPredsOf

public List getPredsOf(Object s)

Description copied from interface: DirectedGraph

Returns a list of predecessors for the given node in the graph.

Specified by:

getPredsOf in interface DirectedGraph

getPredsOfAsSet

public Set getPredsOfAsSet(Object s)

Same as getPredsOf(Object) but returns a set. This is faster than calling getPredsOf(Object). Also, certain operations like Collection.contains(Object) execute faster on the set than on the list. The returned set is unmodifiable.

getSuccsOf

public List getSuccsOf(Object s)

Description copied from interface: DirectedGraph

Returns a list of successors for the given node in the graph.

Specified by:

getSuccsOf in interface DirectedGraph

getSuccsOfAsSet

public Set getSuccsOfAsSet(Object s)

Same as getSuccsOf(Object) but returns a set. This is faster than calling getSuccsOf(Object). Also, certain operations like Collection.contains(Object) execute faster on the set than on the list. The returned set is unmodifiable.

size

public int size()

Description copied from interface: DirectedGraph

Returns the node count for this graph.

Specified by:

size in interface DirectedGraph

iterator

public Iterator iterator()

Description copied from interface: DirectedGraph

Returns an iterator for the nodes in this graph. No specific ordering of the nodes is guaranteed.

Specified by:

iterator in interface Iterable

Specified by:

iterator in interface DirectedGraph

addEdge

public void addEdge(Object from,
                    Object to)

Description copied from interface: MutableDirectedGraph

Adds an edge to the graph between 2 nodes. If the edge is already present no change is made.

Specified by:

addEdge in interface MutableDirectedGraph

Parameters:

from - out node for the edge.

to - in node for the edge.

removeEdge

public void removeEdge(Object from,
                       Object to)

Description copied from interface: MutableDirectedGraph

Removes an edge between 2 nodes in the graph. If the edge is not present no change is made.

Specified by:

removeEdge in interface MutableDirectedGraph

Parameters:

from - out node for the edge to remove.

to - in node for the edge to remove.

containsEdge

public boolean containsEdge(Object from,
                            Object to)

Specified by:

containsEdge in interface MutableDirectedGraph

Returns:

true if the graph contains an edge the 2 nodes false otherwise.

containsNode

public boolean containsNode(Object node)

Specified by:

containsNode in interface MutableDirectedGraph

Parameters:

node - node that we want to know if the graph constains.

Returns:

true if the graph contains the node. false otherwise.

getNodes

public List<Object> getNodes()

Specified by:

getNodes in interface MutableDirectedGraph

Returns:

a list of the nodes that compose the graph. No ordering is implied.

addNode

public void addNode(Object node)

Description copied from interface: MutableDirectedGraph

Adds a node to the graph. Initially the added node has no successors or predecessors. ; as a consequence it is considered both a head and tail for the graph.

Specified by:

addNode in interface MutableDirectedGraph

Parameters:

node - a node to add to the graph.

See Also:

DirectedGraph.getHeads(), DirectedGraph.getTails()

removeNode

public void removeNode(Object node)

Description copied from interface: MutableDirectedGraph

Removes a node from the graph. If the node is not found in the graph, no change is made.

Specified by:

removeNode in interface MutableDirectedGraph

Parameters:

node - the node to be removed.

printGraph

public void printGraph()