edu.iu.dsc.tws.tset.graph

Class DAGMutableGraph<T extends TBase>

java.lang.Object

edu.iu.dsc.tws.tset.graph.DAGMutableGraph<T>

Type Parameters:

T - node type

All Implemented Interfaces:

MutableGraph<T>, java.io.Serializable

public class DAGMutableGraph<T extends TBase>
extends java.lang.Object
implements MutableGraph<T>

DAG graph implementation

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
DAGMutableGraph()

Method Summary

Modifier and Type	Method and Description
boolean	addNode(T node) Adds node if it is not already present.
boolean	allowsSelfLoops() Returns true if this graph allows self-loops (edges that connect a node to itself).
protected boolean	checkCycle(T origin, T target) check if adding this edge to the graph creates an cycle
T	getNodeById(java.lang.String id) returns the node which has the given Id or null if no such node exsists
boolean	isDirected() Returns true if the edges in this graph are directed.
java.util.Set<T>	nodes()
java.util.Set<T>	predecessors(T node) Returns all nodes in this graph adjacent to node which can be reached by traversing node's incoming edges against the direction (if any) of the edge.
boolean	putEdge(T orgin, T target) Adds an edge connecting nodeU to nodeV if one is not already present.
boolean	removeEdge(T origin, T target) Removes the edge connecting nodeU to nodeV, if it is present.
boolean	removeNode(T node) Removes node if it is present; all edges incident to node will also be removed.
java.util.Set<T>	successors(T node) Returns all nodes in this graph adjacent to node which can be reached by traversing node's outgoing edges in the direction (if any) of the edge.

Methods inherited from class java.lang.Object

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

Constructor Detail

DAGMutableGraph

public DAGMutableGraph()

Method Detail

addNode

public boolean addNode(T node)

Description copied from interface: MutableGraph

Adds node if it is not already present.

Nodes must be unique, just as Map keys must be. They must also be non-null.

Specified by:

addNode in interface MutableGraph<T extends TBase>

Returns:

true if the graph was modified as a result of this call

putEdge

public boolean putEdge(T orgin,
                       T target)

Description copied from interface: MutableGraph

Adds an edge connecting nodeU to nodeV if one is not already present.

If the graph is directed, the resultant edge will be directed; otherwise, it will be undirected.

If nodeU and nodeV are not already present in this graph, this method will silently add nodeU and nodeV to the graph.

Specified by:

putEdge in interface MutableGraph<T extends TBase>

Returns:

true if the graph was modified as a result of this call

nodes

public java.util.Set<T> nodes()

Specified by:

nodes in interface MutableGraph<T extends TBase>

removeNode

public boolean removeNode(T node)

Description copied from interface: MutableGraph

Removes node if it is present; all edges incident to node will also be removed.

Specified by:

removeNode in interface MutableGraph<T extends TBase>

Returns:

true if the graph was modified as a result of this call

removeEdge

public boolean removeEdge(T origin,
                          T target)

Description copied from interface: MutableGraph

Removes the edge connecting nodeU to nodeV, if it is present.

Specified by:

removeEdge in interface MutableGraph<T extends TBase>

Returns:

true if the graph was modified as a result of this call

successors

public java.util.Set<T> successors(T node)

Description copied from interface: MutableGraph

Returns all nodes in this graph adjacent to node which can be reached by traversing node's outgoing edges in the direction (if any) of the edge.

Specified by:

successors in interface MutableGraph<T extends TBase>

predecessors

public java.util.Set<T> predecessors(T node)

Description copied from interface: MutableGraph

Returns all nodes in this graph adjacent to node which can be reached by traversing node's incoming edges against the direction (if any) of the edge.

Specified by:

predecessors in interface MutableGraph<T extends TBase>

isDirected

public boolean isDirected()

Description copied from interface: MutableGraph

Returns true if the edges in this graph are directed.

Specified by:

isDirected in interface MutableGraph<T extends TBase>

getNodeById

public T getNodeById(java.lang.String id)

Description copied from interface: MutableGraph

returns the node which has the given Id or null if no such node exsists

Specified by:

getNodeById in interface MutableGraph<T extends TBase>

Parameters:

id - the id of the node to return

checkCycle

protected boolean checkCycle(T origin,
                             T target)

check if adding this edge to the graph creates an cycle

Parameters:

origin - origin of the edge being added

target - target of the edge being added

Returns:

true if a cycle is created

allowsSelfLoops

public boolean allowsSelfLoops()

Description copied from interface: MutableGraph

Returns true if this graph allows self-loops (edges that connect a node to itself). Attempting to add a self-loop to a graph that does not allow them will throw an IllegalArgumentException.

Specified by:

allowsSelfLoops in interface MutableGraph<T extends TBase>