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:
GNetworkX 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:
antichainlist

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]]