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, topo_order=None)[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)

  • topo_order (list or tuple, optional) – A topological order for G (if None, the function will compute one)

Returns

Return type

generator object

Raises

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.