alluxio.collections

Class DirectedAcyclicGraph<T>

java.lang.Object

alluxio.collections.DirectedAcyclicGraph<T>

Type Parameters:

T - the payload of each node

@NotThreadSafe
public class DirectedAcyclicGraph<T>
extends Object

A Directed Acyclic Graph (DAG).

Constructor Summary

Constructors

Constructor and Description
DirectedAcyclicGraph() A Directed Acyclic Graph (DAG).

Method Summary

Modifier and Type	Method and Description
void	add(T payload, List<T> parents) Adds a node to the DAG, that takes the given payload and depends on the specified parents.
boolean	contains(T payload) Checks if a node with the given payload is in the DAG.
void	deleteLeaf(T payload) Deletes a leaf DAG node that carries the given payload.
List<T>	getAllInTopologicalOrder() Gets all payloads of the DAG in the topological order.
List<T>	getChildren(T payload) Gets the payloads for the children of the given node.
List<T>	getParents(T payload) Gets the payloads for the given nodes parents.
List<T>	getRoots() Gets the payloads of all the root nodes of the DAG.
boolean	isRoot(T payload) Checks if a given payload is in a root of the DAG.
List<T>	sortTopologically(Set<T> payloads) Sorts a given set of payloads topologically based on the DAG.

Methods inherited from class java.lang.Object

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

Constructor Detail

DirectedAcyclicGraph

public DirectedAcyclicGraph()

A Directed Acyclic Graph (DAG).

Method Detail

add

public void add(T payload,
                List<T> parents)

Adds a node to the DAG, that takes the given payload and depends on the specified parents.

Parameters:

payload - the payload

parents - the parents of the created node

deleteLeaf

public void deleteLeaf(T payload)

Deletes a leaf DAG node that carries the given payload.

Parameters:

payload - the payload of the node to delete

contains

public boolean contains(T payload)

Checks if a node with the given payload is in the DAG.

Parameters:

payload - the payload of the node to check

Returns:

true if there a node in the DAG contains the given value as payload, false otherwise

getChildren

public List<T> getChildren(T payload)

Gets the payloads for the children of the given node.

Parameters:

payload - the payload of the parent node

Returns:

the children's payloads, an empty list if the given payload doesn't exist in the DAG

getParents

public List<T> getParents(T payload)

Gets the payloads for the given nodes parents.

Parameters:

payload - the payload of the children node

Returns:

the parents' payloads, an empty list if the given payload doesn't exist in the DAG

isRoot

public boolean isRoot(T payload)

Checks if a given payload is in a root of the DAG.

Parameters:

payload - the payload to check for root

Returns:

true if the payload is in the root of the DAG, false otherwise

getRoots

public List<T> getRoots()

Gets the payloads of all the root nodes of the DAG.

Returns:

all the root payloads

sortTopologically

public List<T> sortTopologically(Set<T> payloads)

Sorts a given set of payloads topologically based on the DAG. This method requires all the payloads to be in the DAG.

Parameters:

payloads - the set of input payloads

Returns:

the payloads after topological sort

getAllInTopologicalOrder

public List<T> getAllInTopologicalOrder()

Gets all payloads of the DAG in the topological order.

Returns:

the payloads of all the nodes in topological order