Package software.amazon.smithy.utils

Class DependencyGraph<T>

java.lang.Object
software.amazon.smithy.utils.DependencyGraph<T>
Type Parameters:
T - The data type stored in the graph.
All Implemented Interfaces:
Iterable<T>, Collection<T>
public class DependencyGraph<T> extends Object implements Collection<T>, Iterable<T>
A basic dependency graph.

Iteration and ordering in collection methods are based on insertion order. A topographically sorted view of the graph is provided by toSortedList().

  • Constructor Details

    • DependencyGraph

      public DependencyGraph(int initialCapacity)
      Constructs a new, empty dependency graph with the specified initial capacity.
      Parameters:
      initialCapacity - the initial capacity of the dependency graph.

    • DependencyGraph

      public DependencyGraph(Collection<T> c)
      Constructs a new dependency graph with the same elements as the specified collection. The dependency graph is created with an initial capacity equal to the size of the collection.
      Parameters:
      c - the collection whose elements are to be added to this graph.

    • DependencyGraph

      public DependencyGraph()
      Constructs a new dependency graph with the default initial capacity (16).

  • Method Details

    • add

      public boolean add(T t)
      Specified by:
      add in interface Collection<T>

    • addDependency

      public void addDependency(T what, T dependsOn)
      Adds a dependency between two nodes.

      If either node is not already present in the graph, it is added.

      Parameters:
      what - The node to add a dependency to.
      dependsOn - The dependency to add.

    • addDependencies

      public void addDependencies(T what, Collection<T> dependsOn)
      Adds a set of dependencies to a node.

      If any node is not already present in the graph, it is added.

      Parameters:
      what - The node to add dependencies to.
      dependsOn - The dependencies to add.

    • setDependencies

      public void setDependencies(T what, Collection<T> dependsOn)
      Sets the dependencies for a node.

      If the node already has dependencies, they will be replaced.

      Parameters:
      what - The node to set dependencies for.
      dependsOn - The dependencies to set.

    • remove

      public boolean remove(Object o)
      Specified by:
      remove in interface Collection<T>

    • removeDependency

      public void removeDependency(T what, T dependsOn)
      Removes a dependency from a node.
      Parameters:
      what - The node to remove a dependency from.
      dependsOn - The dependency to remove.

    • removeDependencies

      public void removeDependencies(T what, Collection<T> dependsOn)
      Removes a set of dependencies from a node.
      Parameters:
      what - The node to remove dependencies from.
      dependsOn - The dependencies to remove.

    • getIndependentNodes

      public Set<T> getIndependentNodes()
      Returns:
      Returns a set of nodes that have no remaining dependencies.

    • getDirectDependencies

      public Set<T> getDirectDependencies(T node)
      Gets all the direct dependencies of a given node.
      Parameters:
      node - The node whose dependencies should be fetched.
      Returns:
      A set of dependencies.

    • getDirectDependants

      public Set<T> getDirectDependants(T node)
      Gets all the nodes that depend on a given node.
      Parameters:
      node - The node whose dependants should be fetched.
      Returns:
      A set of dependants.

    • findCycles

      public List<List<T>> findCycles()
      Finds all strongly-connected components of the graph.

      Cycles returned are not *elementary* cycles. That is, if two or more cycles share any nodes, they will be returned as a single cycle. For example, take the following graph: 

           A -> B -> C -> A
          B -> D -> B

      This graph has one set of strongly-connected components ({B, C, A, D}) made up of two elementary cycles ({B, C, A} and D, B). This method will return the set of strongly-connected components, {B, C, A, D}.

      Returns:
      A list of all strongly-connected components in the graph.

    • size

      public int size()
      Specified by:
      size in interface Collection<T>

    • isEmpty

      public boolean isEmpty()
      Specified by:
      isEmpty in interface Collection<T>

    • contains

      public boolean contains(Object o)
      Specified by:
      contains in interface Collection<T>

    • iterator

      public Iterator<T> iterator()
      Specified by:
      iterator in interface Collection<T>
      Specified by:
      iterator in interface Iterable<T>

    • toArray

      public Object[] toArray()
      Specified by:
      toArray in interface Collection<T>

    • toArray

      public <T1> T1[] toArray(T1[] a)
      Specified by:
      toArray in interface Collection<T>

    • toSortedList

      public List<T> toSortedList()
      Gets a topographically sorted view of the graph.
      Returns:
      Returns a topographically sorted list view of the graph.

    • toSortedList

      public List<T> toSortedList(Comparator<T> comparator)
      Gets a topographically sorted view of the graph where independent nodes are evaluated in the order given by the comparator.
      Parameters:
      comparator - A comparator used to sort independent nodes.
      Returns:
      Returns a topographically sorted list view of the graph.

    • containsAll

      public boolean containsAll(Collection<?> c)
      Specified by:
      containsAll in interface Collection<T>

    • addAll

      public boolean addAll(Collection<? extends T> c)
      Specified by:
      addAll in interface Collection<T>

    • removeAll

      public boolean removeAll(Collection<?> c)
      Specified by:
      removeAll in interface Collection<T>

    • retainAll

      public boolean retainAll(Collection<?> c)
      Specified by:
      retainAll in interface Collection<T>

    • clear

      public void clear()
      Specified by:
      clear in interface Collection<T>