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
Examples
>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 4), (3, 4)]) >>> nx.dag.antichain_width(G) 2