Class Digraph<T>

  • Type Parameters:
    T - the type of the nodes

    public class Digraph<T>
    extends java.lang.Object
    A basic directed graph utilitary.

    A directed graph is a data structure consisting of nodes and arrows connecting those nodes which are called edges. In a directed graph edges are ordered pairs of respectively source and target nodes.

    This implementation is adapted to small in-memory graphs.

    See Also:
    Directed graph
    • Constructor Summary

      Constructors 
      Constructor Description
      Digraph​(java.util.Map<T,​java.util.Collection<T>> spec)
      Constructs a directed graph from a specification Map.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.List<T> sort()
      Sort nodes in a topological ordering assuming that this graph is acyclic.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • Digraph

        public Digraph​(java.util.Map<T,​java.util.Collection<T>> spec)
                throws java.lang.IllegalArgumentException
        Constructs a directed graph from a specification Map.
        Parameters:
        spec - the map defining a set of source nodes (keys) that are linked to a collection of adjacent target nodes (values). Both keys and values must not be null.
        Throws:
        java.lang.IllegalArgumentException - when a target node is not present in the sources nodes.
    • Method Detail

      • sort

        public java.util.List<T> sort()
                               throws java.lang.IllegalStateException
        Sort nodes in a topological ordering assuming that this graph is acyclic.

        A graph without cycles is often called a Directed Acyclic Graph (DAG).

        Returns:
        a linear ordering of nodes such for every edge in the graph its target node is present before its source node.
        Throws:
        java.lang.IllegalStateException - when this graph contains a cycle.
        See Also:
        topological sorting, DAG