dominance_frontiers#

dominance_frontiers(G, start)[source]#

Returns the dominance frontiers of all nodes of a directed graph.

Parameters:
Ga DiGraph or MultiDiGraph

The graph where dominance is to be computed.

startnode

The start node of dominance computation.

Returns:
dfdict keyed by nodes

A dict containing the dominance frontiers of each node reachable from start as lists.

Raises:
NetworkXNotImplemented

If G is undirected.

NetworkXError

If start is not in G.

References

[1]

Cooper, Keith D., Harvey, Timothy J. and Kennedy, Ken. “A simple, fast dominance algorithm.” (2006). https://hdl.handle.net/1911/96345

Examples

>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
>>> sorted((u, sorted(df)) for u, df in nx.dominance_frontiers(G, 1).items())
[(1, []), (2, [5]), (3, [5]), (4, [5]), (5, [])]