findCyclicSubgraphs

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

findCyclicSubgraphs

(

G

)

(

,

G.IncidentEdgesCache incidentEdgesCache = G.IncidentEdgesCache.init

)

if (

is(G : Graph!Params,

Params...

)

)

Return Value

Type: auto

range of cycles in the graph represented as arrays of node indices

Examples

alias G = Graph!int;

//   __
//   \ \
//    `-0 -- 1 -- 2 -- 3
//      |       / |    |
//      |      /  |    |
//      4 -- 5 -- 6    7
auto g = G([0, 1, 2, 3, 4, 5, 6, 7], [
    G.edge(0, 0),
    G.edge(0, 1),
    G.edge(0, 4),
    G.edge(1, 2),
    G.edge(2, 3),
    G.edge(2, 5),
    G.edge(2, 6),
    G.edge(3, 7),
    G.edge(4, 5),
    G.edge(5, 6),
]);
auto cycles = g.findCyclicSubgraphs();

import std.algorithm : equal;

assert(cycles.equal([
    [0],
    [2, 6, 5],
    [1, 2, 5, 4, 0],
]));

Meta

Source

See Implementation