Binary predicate taking two nodes of type size_t which is true iff the first node is adjacent to the second node.
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); auto topologicalOrder = topologicalSort!hasEdge(n); assert(equal(topologicalOrder, [3, 0, 1, 2, 4]));
import std.exception : assertThrown; // _____________ _____________ // / 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) || u == 4 && v == 0; assertThrown!NoDAG(topologicalSort!hasEdge(n));
Sort nodes of a DAG topologically. The graph structure is defined by hasEdge and n. Nodes are represented as size_t integers. The graph must be directed and acyclic (DAG).