lexicographical_topological_sort(G, key=None)
A topological sort is a nonunique permutation of the nodes such that an edge from u to v implies that u appears before v in the topological sort order.
This algorithm is based on a description and proof in "Introduction to Algorithms: A Creative Approach" .
A directed acyclic graph (DAG)
This function maps nodes to keys with which to resolve ambiguities in the sort order. Defaults to the identity function.
Topological sort is defined for directed graphs only. If the graph G
is undirected, a NetworkXError
is raised.
If G
is not a directed acyclic graph (DAG) no topological sort exists and a NetworkXUnfeasible
exception is raised. This can also be raised if G
is changed while the returned iterator is being processed
If G
is changed while the returned iterator is being processed.
Returns a generator of nodes in lexicographically topologically sorted order.
Yields the nodes in lexicographical topological sort order.
>>> DG = nx.DiGraph([(2, 1), (2, 5), (1, 3), (1, 4), (5, 4)])
... list(nx.lexicographical_topological_sort(DG)) [2, 1, 3, 5, 4]
>>> list(nx.lexicographical_topological_sort(DG, key=lambda x: -x)) [2, 5, 1, 4, 3]See :
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.dag.lexicographical_topological_sort
networkx.algorithms.dag.topological_sort
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them