Package org.apache.ofbiz.base.util

Class Digraph<T>

java.lang.Object
org.apache.ofbiz.base.util.Digraph<T>
Type Parameters:
T - the type of the nodes
public class Digraph<T> extends 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:

  • Constructor Details

    • Digraph

      public Digraph(Map<T,Collection<T>> spec) throws 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:
      IllegalArgumentException - when a target node is not present in the sources nodes.

  • Method Details

    • sort

      public List<T> sort() throws 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:
      IllegalStateException - when this graph contains a cycle.
      See Also: