rustworkx.dag_weighted_longest_path#

dag_weighted_longest_path(graph, weight_fn, /)#

Find the weighted longest path in a DAG

This function differs from rustworkx.dag_longest_path() in that this function requires a weight_fn parameter, and the weight_fn is expected to return a float not an int.

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 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 a float weight for that edge. For example, dag_longest_path(graph, lambda: _, __, weight: weight) could be used to just use a float 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