Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.dag.antichains

antichains(G)[source]

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)
Returns:
Return type:

generator object
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:

https://github.com/sagemath/sage/blob/master/src/sage/combinat/posets/hasse_diagram.py

References

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