antichain_width#

antichain_width(G)[source]#

Returns the width of the partial order defined by the DAG G.

The width is the largest number of nodes in G such that no node in the set can reach another node in the set.

By Dilworth’s theorem [1] the width is also equal to the minimum number of chains needed to cover all nodes. This function reduces the problem to a maximum bipartite matching on the transitive closure of G.

Parameters:

GNetworkX DiGraph: A directed acyclic graph representing a partial order.

Returns:

int: The width of the poset (size of a maximum antichain).

Raises:

NetworkXUnfeasible: If G is not acyclic.
NetworkXNotImplemented: If G is not directed

References

[1]

https://en.wikipedia.org/wiki/Antichain

Examples

>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 4), (3, 4)])
>>> nx.dag.antichain_width(G)
2