edu.snu.coral.common.dag

Class DAG<V extends Vertex,E extends Edge<V>>

java.lang.Object

edu.snu.coral.common.dag.DAG<V,E>

Type Parameters:

V - the vertex type

E - the edge type

All Implemented Interfaces:

Serializable

public final class DAG<V extends Vertex,E extends Edge<V>>
extends Object
implements Serializable

DAG implementation.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DAG.TraversalOrder Indicates the traversal order of this DAG.

Field Summary

Fields

Modifier and Type	Field and Description
static String	EMPTY_DAG_DIRECTORY

Constructor Summary

Constructors

Constructor and Description
DAG(Set<V> vertices, Map<V,Set<E>> incomingEdges, Map<V,Set<E>> outgoingEdges, Map<V,LoopVertex> assignedLoopVertexMap, Map<V,Integer> loopStackDepthMap) Constructor of DAG, called by the DAGBuilder.

Method Summary

Modifier and Type	Method and Description
<V2 extends Vertex,E2 extends Edge<V2>> DAG<V2,E2>	convert(Function<DAG<V,E>,DAG<V2,E2>> function) Converts a DAG into another DAG according to a function.
List<V>	filterVertices(Predicate<V> condition) Filters the vertices according to the given condition.
List<V>	getAncestors(String vertexId) Retrieves the ancestors of a vertex.
LoopVertex	getAssignedLoopVertexOf(V v) Retrieves the wrapping LoopVertex of the vertex.
List<V>	getChildren(String vertexId) Retrieves the children vertices of the given vertex.
List<V>	getDescendants(String vertexId) Retrieves the descendants of a vertex.
E	getEdgeBetween(String srcVertexId, String dstVertexId) Retrieves the edge between two vertices.
List<E>	getIncomingEdgesOf(String vertexId) Retrieves the incoming edges of the given vertex.
List<E>	getIncomingEdgesOf(V v) Retrieves the incoming edges of the given vertex.
Integer	getLoopStackDepthOf(V v) Retrieves the stack depth of the given vertex.
List<E>	getOutgoingEdgesOf(String vertexId) Retrieves the outgoing edges of the given vertex.
List<E>	getOutgoingEdgesOf(V v) Retrieves the outgoing edges of the given vertex.
List<V>	getParents(String vertexId) Retrieves the parent vertices of the given vertex.
List<V>	getRootVertices() Retrieves the root vertices of this DAG.
List<V>	getTopologicalSort() Gets the DAG's vertices in topologically sorted order.
V	getVertexById(String id) Retrieves the vertex given its ID.
List<V>	getVertices() Retrieves the vertices of this DAG.
Boolean	isCompositeVertex(V v) Checks whether the given vertex is assigned with a wrapping LoopVertex.
Boolean	pathExistsBetween(V v1, V v2) Function checks whether there is a path between two vertices.
void	storeJSON(String directory, String name, String description) Stores JSON representation of this DAG into a file.
void	topologicalDo(Consumer<V> function) Applies the function to each node in the DAG in a topological order.
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

EMPTY_DAG_DIRECTORY

public static final String EMPTY_DAG_DIRECTORY

See Also:

Constant Field Values

Constructor Detail

DAG

public DAG(Set<V> vertices,
           Map<V,Set<E>> incomingEdges,
           Map<V,Set<E>> outgoingEdges,
           Map<V,LoopVertex> assignedLoopVertexMap,
           Map<V,Integer> loopStackDepthMap)

Constructor of DAG, called by the DAGBuilder.

Parameters:

vertices - set of vertices.

incomingEdges - map of incoming edges for each vertex.

outgoingEdges - map of outgoing edges for each vertex.

assignedLoopVertexMap - map of assignedLoopVertex info.

loopStackDepthMap - map of stack depth of LoopVertices.

Method Detail

convert

public <V2 extends Vertex,E2 extends Edge<V2>> DAG<V2,E2> convert(Function<DAG<V,E>,DAG<V2,E2>> function)

Converts a DAG into another DAG according to a function.

Type Parameters:

V2 - the converted DAG's vertex type.

E2 - the converted DAG's edge type.

Parameters:

function - to apply when converting a DAG to another.

Returns:

the converted DAG.

getVertexById

public V getVertexById(String id)

Retrieves the vertex given its ID.

Parameters:

id - of the vertex to retrieve

Returns:

the vertex

Throws:

IllegalVertexOperationException - when the requested vertex does not exist.

getVertices

public List<V> getVertices()

Retrieves the vertices of this DAG.

Returns:

the set of vertices. Note that the result is never null, ensured by DAGBuilder.

getRootVertices

public List<V> getRootVertices()

Retrieves the root vertices of this DAG.

Returns:

the set of root vertices.

getIncomingEdgesOf

public List<E> getIncomingEdgesOf(V v)

Retrieves the incoming edges of the given vertex.

Parameters:

v - the subject vertex.

Returns:

the set of incoming edges to the vertex. Note that the result is never null, ensured by DAGBuilder.

getIncomingEdgesOf

public List<E> getIncomingEdgesOf(String vertexId)

Retrieves the incoming edges of the given vertex.

Parameters:

vertexId - the ID of the subject vertex.

Returns:

the set of incoming edges to the vertex. Note that the result is never null, ensured by DAGBuilder.

getOutgoingEdgesOf

public List<E> getOutgoingEdgesOf(V v)

Retrieves the outgoing edges of the given vertex.

Parameters:

v - the subject vertex.

Returns:

the set of outgoing edges to the vertex. Note that the result is never null, ensured by DAGBuilder.

getOutgoingEdgesOf

public List<E> getOutgoingEdgesOf(String vertexId)

Retrieves the outgoing edges of the given vertex.

Parameters:

vertexId - the ID of the subject vertex.

Returns:

the set of outgoing edges to the vertex. Note that the result is never null, ensured by DAGBuilder.

getParents

public List<V> getParents(String vertexId)

Retrieves the parent vertices of the given vertex.

Parameters:

vertexId - the ID of the subject vertex.

Returns:

the list of parent vertices.

getChildren

public List<V> getChildren(String vertexId)

Retrieves the children vertices of the given vertex.

Parameters:

vertexId - the ID of the subject vertex.

Returns:

the list of children vertices.

getEdgeBetween

public E getEdgeBetween(String srcVertexId,
                        String dstVertexId)
                 throws IllegalEdgeOperationException

Retrieves the edge between two vertices.

Parameters:

srcVertexId - the ID of the source vertex.

dstVertexId - the ID of the destination vertex.

Returns:

the edge if exists.

Throws:

IllegalEdgeOperationException - otherwise.

getTopologicalSort

public List<V> getTopologicalSort()

Gets the DAG's vertices in topologically sorted order. This function brings consistent results.

Returns:

the sorted list of vertices in topological order.

getAncestors

public List<V> getAncestors(String vertexId)

Retrieves the ancestors of a vertex.

Parameters:

vertexId - to find the ancestors for.

Returns:

the list of ancestors.

getDescendants

public List<V> getDescendants(String vertexId)

Retrieves the descendants of a vertex.

Parameters:

vertexId - to find the descendants for.

Returns:

the list of descendants.

filterVertices

public List<V> filterVertices(Predicate<V> condition)

Filters the vertices according to the given condition.

Parameters:

condition - that must be satisfied to be included in the filtered list.

Returns:

the list of vertices that meet the condition.

topologicalDo

public void topologicalDo(Consumer<V> function)

Applies the function to each node in the DAG in a topological order. This function brings consistent results.

Parameters:

function - to apply.

pathExistsBetween

public Boolean pathExistsBetween(V v1,
                                 V v2)

Function checks whether there is a path between two vertices.

Parameters:

v1 - First vertex to check.

v2 - Second vertex to check.

Returns:

Whether or not there is a path between two vertices.

isCompositeVertex

public Boolean isCompositeVertex(V v)

Checks whether the given vertex is assigned with a wrapping LoopVertex.

Parameters:

v - Vertex to check.

Returns:

whether or not it is wrapped by a LoopVertex

getAssignedLoopVertexOf

public LoopVertex getAssignedLoopVertexOf(V v)

Retrieves the wrapping LoopVertex of the vertex.

Parameters:

v - Vertex to check.

Returns:

The wrapping LoopVertex.

getLoopStackDepthOf

public Integer getLoopStackDepthOf(V v)

Retrieves the stack depth of the given vertex.

Parameters:

v - Vertex to check.

Returns:

The depth of the stack of LoopVertices for the vertex.

toString

public String toString()

Overrides:

toString in class Object

storeJSON

public void storeJSON(String directory,
                      String name,
                      String description)

Stores JSON representation of this DAG into a file.

Parameters:

directory - the directory which JSON representation is saved to

name - name of this DAG

description - description of this DAG