dag_longest_path#
- dag_longest_path(G, weight='weight', default_weight=1, topo_order=None)[source]#
Returns the longest path in a directed acyclic graph (DAG).
If
G
has edges withweight
attribute the edge data are used as weight values.- Parameters:
- GNetworkX DiGraph
A directed acyclic graph (DAG)
- weightstr, optional
Edge data key to use for weight
- default_weightint, optional
The weight of edges that do not have a weight attribute
- topo_order: list or tuple, optional
A topological order for
G
(if None, the function will compute one)
- Returns:
- list
Longest path
- Raises:
- NetworkXNotImplemented
If
G
is not directed
See also
Examples
>>> DG = nx.DiGraph([(0, 1, {'cost':1}), (1, 2, {'cost':1}), (0, 2, {'cost':42})]) >>> list(nx.all_simple_paths(DG, 0, 2)) [[0, 1, 2], [0, 2]] >>> nx.dag_longest_path(DG) [0, 1, 2] >>> nx.dag_longest_path(DG, weight="cost") [0, 2]
In the case where multiple valid topological orderings exist,
topo_order
can be used to specify a specific ordering:>>> DG = nx.DiGraph([(0, 1), (0, 2)]) >>> sorted(nx.all_topological_sorts(DG)) # Valid topological orderings [[0, 1, 2], [0, 2, 1]] >>> nx.dag_longest_path(DG, topo_order=[0, 1, 2]) [0, 1] >>> nx.dag_longest_path(DG, topo_order=[0, 2, 1]) [0, 2]