oracle.javatools.util

Class DependencyGraph<T>

java.lang.Object

oracle.javatools.util.DependencyGraph<T>

Type Parameters:

T - The content type for the graph

All Implemented Interfaces:

java.lang.Iterable<T>, java.util.Collection<T>

public final class DependencyGraph<T>
extends java.lang.Object
implements java.util.Collection<T>

This class implements a dependency graph using a strongly connected Directed Acyclic Graph (DAG) that provides sorting of its nodes in topological order.

Some important characteristics of this class are:

1. Calling toOrderedList() will not destroy the graph: the same graph instance can be safely reused after a topological sort operation.
2. It can optionally be instantiated to work in thread-safe mode.
3. It is capable of detecting cycles (or circular dependencies paths) and for each cycle list all participant nodes (see findCycles()).

Since:

11.1.1.7.2

Constructor Summary

Constructors

Constructor and Description
DependencyGraph() Construct a non-thread-safe graph
DependencyGraph(boolean threadSafe) Constructor
DependencyGraph(int initialCapacity) Construct a non-thread-safe graph
DependencyGraph(int initialCapacity, boolean threadSafe) Constructor

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(T content) Add content to the graph as a new node only if the given content does not exist in the graph already.
boolean	addAll(java.util.Collection<? extends T> content)
void	addDependencies(T dependent, java.util.Collection<T> dependencies) Adds 1 or more dependencies to the given dependent node.
void	addDependencies(T dependent, T... dependencies) See method #addDependencies(T dependent, Collection)
void	clear()
boolean	contains(java.lang.Object content) Check if a given content exists in the graph
boolean	containsAll(java.util.Collection c)
java.util.Collection<java.util.Collection<T>>	findCycles() Identifies all cycles (circular dependency paths) in the graph, if any.
java.util.Collection<T>	getDependentFreeNodes() Identifies all the nodes that no other nodes depend on
java.util.Collection<T>	getDirectDependencies(T content) Retrieves the contents of all nodes that the given content directly depends on.
java.util.Collection<T>	getDirectDependents(T content) Retrieves the contents of all nodes that the given content is a direct dependency of.
java.util.Collection<T>	getIndependentNodes() Identifies all the nodes that do not depend on any other node
boolean	isEmpty()
java.util.Iterator<T>	iterator()
boolean	remove(java.lang.Object object) Will remove the node containing the given content, if it exists in the graph.
boolean	removeAll(java.util.Collection content)
void	removeDependencies(T dependent, T... dependencies) Removes 1 or more dependencies from the given dependent node.
boolean	retainAll(java.util.Collection content)
int	size()
java.lang.Object[]	toArray()
<E> E[]	toArray(E[] array)
java.util.List<T>	toOrderedList() This method will perform a topological sorting of its content, based on the algorithm described by Arthur B.
java.lang.String	toString() Returns a string representation of this collection.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

equals, hashCode

Constructor Detail

DependencyGraph

public DependencyGraph(boolean threadSafe)

Constructor

Parameters:

threadSafe - whether the graph must be thread-safe or not. Thread-safety will impact performance in some degree.

DependencyGraph

public DependencyGraph()

Construct a non-thread-safe graph

DependencyGraph

public DependencyGraph(int initialCapacity,
               boolean threadSafe)

Constructor

Parameters:

initialCapacity - sets the initial capacity for some internal data structures.

threadSafe - whether the graph must be thread-safe or not. Thread-safety will impact performance in some degree.

DependencyGraph

public DependencyGraph(int initialCapacity)

Construct a non-thread-safe graph

Parameters:

initialCapacity - sets the initial capacity for some internal data structures.

Method Detail

size

public int size()

Specified by:

size in interface java.util.Collection<T>

getDependentFreeNodes

public java.util.Collection<T> getDependentFreeNodes()

Identifies all the nodes that no other nodes depend on

Returns:

Collection of nodes that no other nodes depend on

getIndependentNodes

public java.util.Collection<T> getIndependentNodes()

Identifies all the nodes that do not depend on any other node

Returns:

Collection of nodes that do not depend on any other node

add

public boolean add(T content)

Add content to the graph as a new node only if the given content does not exist in the graph already.

Specified by:

add in interface java.util.Collection<T>

Parameters:

content - non-null content to be added to the graph

addDependencies

public void addDependencies(T dependent,
                   java.util.Collection<T> dependencies)

Adds 1 or more dependencies to the given dependent node.

If the dependent content or any of the given dependencies don't exist as nodes in the graph, new nodes will automatically be created and added first.

Because this is a strongly connected digraph, each new dependency will represent 2 new edges (or connections) between 2 nodes (dependent and dependency). For example, if A depends on B then B will have an outgoing connection to A as well as A will have an incoming connection from B.

Parameters:

dependent - The node that depends on each node provided in the dependencies collection

dependencies - All nodes that dependent depends on

addDependencies

public void addDependencies(T dependent,
                   T... dependencies)

See method #addDependencies(T dependent, Collection)

Parameters:

dependent - The node that depends on each node provided in the dependencies array

dependencies - Optional list of nodes that dependent depends on

removeDependencies

public void removeDependencies(T dependent,
                      T... dependencies)

Removes 1 or more dependencies from the given dependent node.

Including nodes in the dependencies array that are not connected to the dependent node won't have any effect.

See method #addDependencies(T dependent, Collection) for more details on some dependency internals.

Parameters:

dependent - The node that depends on each node provided in the dependencies array

dependencies - All nodes that should be removed as dependencies of the dependent node

remove

public boolean remove(java.lang.Object object)

Will remove the node containing the given content, if it exists in the graph. As a result, all edges directly connecting this node to other nodes will also be removed.

Specified by:

remove in interface java.util.Collection<T>

Parameters:

object - The content to be removed from the graph

contains

public boolean contains(java.lang.Object content)

Check if a given content exists in the graph

Specified by:

contains in interface java.util.Collection<T>

Parameters:

content - Content to be verified

Returns:

true only if the given content exists in the graph

getDirectDependencies

public java.util.Collection<T> getDirectDependencies(T content)

Retrieves the contents of all nodes that the given content directly depends on.

Parameters:

content - The node to retrieve all direct dependencies from

Returns:

A collection containing all direct dependencies for the given content. If there aren't any, the collection will be empty.

getDirectDependents

public java.util.Collection<T> getDirectDependents(T content)

Retrieves the contents of all nodes that the given content is a direct dependency of.

Parameters:

content - The node to retrieve all direct dependents from

Returns:

A collection containing all direct dependents of the given content. If there aren't any, the collection will be empty.

toOrderedList

public java.util.List<T> toOrderedList()

This method will perform a topological sorting of its content, based on the algorithm described by Arthur B. Kahn[1962] in article "Topological sorting of large networks", Communications of the ACM 5 (11): 558562

During the sorting, if a directed cycle (or a circular reference) is detected, an IllegalStateException will be thrown.

In order to be non-destructive and keep the graph reusable after this operation, this method will take snapshots of all required internal data structures and use them to perform the sorting.

When running in thread-safe mode, this method will hold a read lock during the entire sort operation in order to avoid unpredicted results if the graph's contents were to be modified during the sorting.

Returns:

A list containing the content of the graph in topological order. In other words, since this is a dependency graph, the elements of the list will be sorted in a correct and safe order of execution. If the graph is empty, then the resulting list will also be empty.

findCycles

public java.util.Collection<java.util.Collection<T>> findCycles()

Identifies all cycles (circular dependency paths) in the graph, if any.

Returns:

A collection of cycles. If there isn't any, the collection is empty, otherwise it will contain 1 or more collections, each one containing the graph nodes that participate in a circular dependency path.

addAll

public boolean addAll(java.util.Collection<? extends T> content)

Specified by:

addAll in interface java.util.Collection<T>

clear

public void clear()

Specified by:

clear in interface java.util.Collection<T>

containsAll

public boolean containsAll(java.util.Collection c)

Specified by:

containsAll in interface java.util.Collection<T>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection<T>

iterator

public java.util.Iterator<T> iterator()

Specified by:

iterator in interface java.lang.Iterable<T>

Specified by:

iterator in interface java.util.Collection<T>

Returns:

removeAll

public boolean removeAll(java.util.Collection content)

Specified by:

removeAll in interface java.util.Collection<T>

retainAll

public boolean retainAll(java.util.Collection content)

Specified by:

retainAll in interface java.util.Collection<T>

toArray

public java.lang.Object[] toArray()

Specified by:

toArray in interface java.util.Collection<T>

toArray

public <E> E[] toArray(E[] array)

Specified by:

toArray in interface java.util.Collection<T>

toString

public java.lang.String toString()

Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator, enclosed in square brackets ("[]"). Adjacent elements are separated by the characters ", " (comma and space). Elements are converted to strings as by String.valueOf(Object).

Overrides:

toString in class java.lang.Object

Returns:

a string representation of this collection