range of cycles in the graph represented as arrays of node indices
1 alias G = Graph!int; 2 3 // __ 4 // \ \ 5 // `-0 -- 1 -- 2 -- 3 6 // | / | | 7 // | / | | 8 // 4 -- 5 -- 6 7 9 auto g = G([0, 1, 2, 3, 4, 5, 6, 7], [ 10 G.edge(0, 0), 11 G.edge(0, 1), 12 G.edge(0, 4), 13 G.edge(1, 2), 14 G.edge(2, 3), 15 G.edge(2, 5), 16 G.edge(2, 6), 17 G.edge(3, 7), 18 G.edge(4, 5), 19 G.edge(5, 6), 20 ]); 21 auto cycles = g.findCyclicSubgraphs(); 22 23 import std.algorithm : equal; 24 25 assert(cycles.equal([ 26 [0], 27 [2, 6, 5], 28 [1, 2, 5, 4, 0], 29 ]));
Find a cycle base of an undirected graph using the Paton's algorithm.
The algorithm is described in
> K. Paton, An algorithm for finding a fundamental set of cycles > for an undirected linear graph, Comm. ACM 12 (1969), pp. 514-518.
and the implementation is adapted from the [Java implementation][1] of K. Paton originally licensed under [Apache License 2.0][2].
[1]: https://code.google.com/archive/p/niographs/ [2]: http://www.apache.org/licenses/LICENSE-2.0