Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

rustworkx.dag_longest_path#

dag_longest_path(graph, /, weight_fn=None)#

Find the longest path in a DAG

Parameters:

  • graph (PyDiGraph) – The graph to find the longest path on. The input object must be a DAG without a cycle.

  • weight_fn – A python callable that if set will be passed the 3 positional arguments, the source node, the target node, and the edge weight for each edge as the function traverses the graph. It is expected to return an unsigned integer weight for that edge. For example, dag_longest_path(graph, lambda: _, __, weight: weight) could be use to just use an integer edge weight. It’s also worth noting that this function traverses in topological order and only checks incoming edges to each node.

Returns:

The node indices of the longest path on the DAG

Return type:

NodeIndices

Raises:

  • Exception – If an unexpected error occurs or a path can’t be found

  • DAGHasCycle – If the input PyDiGraph has a cycle