#NEWLINE# @ not_implemented_for ( 'undirected' ) #NEWLINE# def antichains( G ) : #NEWLINE# #INDENT# "Generates antichains from a DAG.\n\n    An antichain is a subset of a partially ordered set such that any\n    two elements in the subset are incomparable.\n\n    Parameters\n    ----------\n    G : NetworkX DiGraph\n        Graph\n\n    Returns\n    -------\n    antichain : generator object\n\n    Raises\n    ------\n    NetworkXNotImplemented\n        If G is not directed\n\n    NetworkXUnfeasible\n        If G contains a cycle\n\n    Notes\n    -----\n    This function was originally developed by Peter Jipsen and Franco Saliola\n    for the SAGE project. It's included in NetworkX with permission from the\n    authors. Original SAGE code at:\n\n    https://sage.informatik.uni-goettingen.de/src/combinat/posets/hasse_diagram.py\n\n    References\n    ----------\n    .. [1] Free Lattices, by R. Freese, J. Jezek and J. B. Nation,\n       AMS, Vol 42, 1995, p. 226.\n    " #NEWLINE# TC = nx . transitive_closure ( G ) #NEWLINE# antichains_stacks = [ ( [ ] , list ( reversed ( list ( nx . topological_sort ( G ) ) ) ) ) ] #NEWLINE# while antichains_stacks : #NEWLINE# #INDENT# ( antichain , stack ) = antichains_stacks . pop ( ) #NEWLINE# ( yield antichain ) #NEWLINE# while stack : #NEWLINE# #INDENT# x = stack . pop ( ) #NEWLINE# new_antichain = ( antichain + [ x ] ) #NEWLINE# new_stack = [ t for t in stack if ( not ( ( t in TC [ x ] ) or ( x in TC [ t ] ) ) ) ] #NEWLINE# antichains_stacks . append ( ( new_antichain , new_stack ) )