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.
Array of components represented as arrays of node indices.
import std.algorithm : equal, min; // _____________ // / \ // (0) --- (1) --- (2) (3) --- (4) enum n = 5; alias connect = (u, v, x, y) => (u == x && v == y) || (u == y && v == x); alias hasEdge = (u, v) => connect(u, v, 0, 1) || connect(u, v, 1, 2) || connect(u, v, 2, 0) || connect(u, v, 3, 4); auto components = connectedComponents!hasEdge(n); assert(equal(components, [ [0, 1, 2], [3, 4], ]));
import std.algorithm : equal, min; // _____________ // / \ // (0) --- (1) --- (2) (3) --- (4) // \_____________________/ enum n = 5; alias connect = (u, v, x, y) => (u == x && v == y) || (u == y && v == x); alias hasEdge = (u, v) => connect(u, v, 0, 1) || connect(u, v, 1, 2) || connect(u, v, 2, 0) || connect(u, v, 0, 3) || connect(u, v, 3, 4); auto components = connectedComponents!hasEdge(n); import std.stdio; assert(equal(components, [ [0, 1, 2, 3, 4], ]));
Calculate connected components of the graph defined by hasEdge.