Skip to main content
`Ctrl`+`K`

# antichains

antichains(G, topo_order=None)

  Generates antichains from a directed acyclic graph (DAG).

  An antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable.

  Parameters:
    G NetworkX DiGraph

      A directed acyclic graph (DAG)

    topo_order: list or tuple, optional

      A topological order for G (if None, the function will compute one)

  Yields:
    antichain list

      a list of nodes in `G` representing an antichain

  Raises:
    NetworkXNotImplemented

      If `G` is not directed

    NetworkXUnfeasible

      If `G` contains a cycle

  Notes

  This function was originally developed by Peter Jipsen and Franco Saliola for the SAGE project. It’s included in NetworkX with permission from the authors. Original SAGE code at:

  sagemath/sage

  References

  [1]

  Free Lattices, by R. Freese, J. Jezek and J. B. Nation, AMS, Vol 42, 1995, p. 226.

  Examples

      >>> DG = nx.DiGraph([(1, 2), (1, 3)])
      >>> list(nx.antichains(DG))
      [[], [3], [2], [2, 3], [1]]