Binary predicate taking two nodes of type size_t which is true iff the first node is adjacent to the second node.
Binary function taking two nodes of type size_t which returns the weight of the edge between the first and the second node. The function may be undefined if hasEdge returns false for the given arguments.
Number of nodes in the graph. hasEdge must be defined for every pair of integer in 0 .. n.
SingleSourceShortestPathsSolution
NoDAG if a cycle is detected.
import std.algorithm : equal; // _____________ _____________ // / v / v // (0) --> (1) --> (2) (3) --> (4) enum n = 5; alias hasEdge = (u, v) => (u + 1 == v && u != 2) || (u + 2 == v && u % 2 == 0); alias weight = (u, v) => 1; auto shortestPaths = dagSingleSourceShortestPaths!(hasEdge, weight)(0, n); assert(equal(shortestPaths.reverseShortestPath(4), [4, 2, 0])); assert(shortestPaths.distance(4) == 2); assert(equal(shortestPaths.reverseShortestPath(2), [2, 0])); assert(shortestPaths.distance(2) == 1); assert(equal(shortestPaths.reverseShortestPath(1), [1, 0])); assert(shortestPaths.distance(1) == 1); assert(equal(shortestPaths.reverseShortestPath(3), size_t[].init)); assert(!shortestPaths.isConnected(3));
Calculate all shortest paths in DAG starting at start. The functions hasEdge and weight define the graphs structure and weights, respectively. Nodes are represented as size_t integers. The graph must be directed and acyclic (DAG).