Package 

Class DirectedAcyclicGraph

  • 
public final class DirectedAcyclicGraph<T>

    A class which represents a simple directed acyclic graph.

    • Method Summary

      Modifier and Type Method Description
      void addNode(@NonNull() T node) Add a node to the graph.
      boolean contains(@NonNull() T node) Returns true if the node is already present in the graph, false otherwise.
      void addEdge(@NonNull() T node, @NonNull() T incomingEdge) Add an edge to the graph.
      List getIncomingEdges(@NonNull() T node) Get any incoming edges from the given node.
      List<T> getOutgoingEdges(@NonNull() T node) Get any outgoing edges for the given node (i.e.
      boolean hasOutgoingEdges(@NonNull() T node) Checks whether we have any outgoing edges for the given node (i.e.
      void clear() Clears the internal graph, and releases resources to pools.
      ArrayList<T> getSortedList() Returns a topologically sorted list of the nodes in this graph.

      • Methods inherited from class java.lang.Object

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

    • Method Detail

      • addNode

         void addNode(@NonNull() T node)

        Add a node to the graph.

        If the node already exists in the graph then this method is a no-op.

        Parameters:
        node - the node to add

      • contains

         boolean contains(@NonNull() T node)

        Returns true if the node is already present in the graph, false otherwise.

      • addEdge

         void addEdge(@NonNull() T node, @NonNull() T incomingEdge)

        Add an edge to the graph.

        Both the given nodes should already have been added to the graph through addNode.

        Parameters:
        node - the parent node
        incomingEdge - the node which has is an incoming edge to {@code node}

      • hasOutgoingEdges

         boolean hasOutgoingEdges(@NonNull() T node)

        Checks whether we have any outgoing edges for the given node (i.e. nodes which havean incoming edge from the given node).

      • clear

         void clear()

        Clears the internal graph, and releases resources to pools.

      • getSortedList

        @NonNull() ArrayList<T> getSortedList()

        Returns a topologically sorted list of the nodes in this graph. This uses the DFS algorithmas described by Cormen et al. (2001). If this graph contains cyclic dependencies then thismethod will throw a RuntimeException.

        The resulting list will be ordered such that index 0 will contain the node at the bottomof the graph. The node at the end of the list will have no dependencies on other nodes.