dev.nm.graph.type

Class SparseDAGraph<V,E extends Arc<V>>

java.lang.Object

dev.nm.graph.type.SparseGraph<V,E>

dev.nm.graph.type.SparseDiGraph<V,E>

dev.nm.graph.type.SparseDAGraph<V,E>

Type Parameters:

V - vertex type

E - arc type

All Implemented Interfaces:

DAGraph<V,E>, DiGraph<V,E>, Graph<V,E>

public class SparseDAGraph<V,E extends Arc<V>>
extends SparseDiGraph<V,E>
implements DAGraph<V,E>

This class implements the sparse directed acyclic graph representation.

Constructor Summary

Constructors

Constructor and Description
SparseDAGraph() Construct an empty directed acyclic graph.
SparseDAGraph(boolean toCheckCyclicity) Construct an empty directed acyclic graph.
SparseDAGraph(DAGraph<V,E> g) (Copy) construct a directed acyclic graph from another directed acyclic graph.

Method Summary

Modifier and Type	Method and Description
SparseDAGraph<V,E>	addEdge(E e) Adds an edge to this graph.
boolean	isAcyclic() Runs validity check to ensure that this DA graph is indeed acyclic.
int	topologicalOrder(V v) Get the topological order of a vertex.

Methods inherited from class dev.nm.graph.type.SparseDiGraph

children, incomingArcs, outgoingArcs, parents, toString, vertices

Methods inherited from class dev.nm.graph.type.SparseGraph

addVertex, contains, edges, edges, removeEdge, removeVertex

Methods inherited from class java.lang.Object

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

Methods inherited from interface dev.nm.graph.DiGraph

children, incomingArcs, outgoingArcs, parents

Methods inherited from interface dev.nm.graph.Graph

addVertex, edges, edges, removeEdge, removeVertex, vertices

Constructor Detail

SparseDAGraph

public SparseDAGraph(boolean toCheckCyclicity)

Construct an empty directed acyclic graph.

Parameters:

toCheckCyclicity - true if to check cyclicity each time an edge is added (slow performance)

SparseDAGraph

public SparseDAGraph()

Construct an empty directed acyclic graph.

SparseDAGraph

public SparseDAGraph(DAGraph<V,E> g)

(Copy) construct a directed acyclic graph from another directed acyclic graph.

Parameters:

g - a graph

Method Detail

addEdge

public SparseDAGraph<V,E> addEdge(E e)

Description copied from interface: Graph

Adds an edge to this graph. Does nothing if e is already in the graph. If the edge contains new vertices, those will be added to the graph.

Specified by:

addEdge in interface Graph<V,E extends Arc<V>>

Overrides:

addEdge in class SparseGraph<V,E extends Arc<V>>

Parameters:

e - the edge to add

Returns:

this graph (for builder pattern)

topologicalOrder

public int topologicalOrder(V v)

Description copied from interface: DAGraph

Get the topological order of a vertex.

Specified by:

topologicalOrder in interface DAGraph<V,E extends Arc<V>>

Parameters:

v - a vertex

Returns:

the topological order of a vertex

isAcyclic

public boolean isAcyclic()

Runs validity check to ensure that this DA graph is indeed acyclic.

Returns:

true if this graph is acyclic