cyclesIn returns the set of elementary cycles in the graph g.
(g graph)
| 22 | |
| 23 | // cyclesIn returns the set of elementary cycles in the graph g. |
| 24 | func cyclesIn(g graph) [][]int { |
| 25 | j := johnson{ |
| 26 | adjacent: g.clone(), |
| 27 | b: make([]set, len(g)), |
| 28 | blocked: make([]bool, len(g)), |
| 29 | } |
| 30 | |
| 31 | // len(j.adjacent) will be the order of g until Tarjan's analysis |
| 32 | // finds no SCC, at which point t.sccSubGraph returns nil and the |
| 33 | // loop breaks. |
| 34 | for j.s < len(j.adjacent)-1 { |
| 35 | // We use the previous SCC adjacency to reduce the work needed. |
| 36 | t := newTarjan(j.adjacent.subgraph(j.s)) |
| 37 | // A_k = adjacency structure of strong component K with least |
| 38 | // vertex in subgraph of G induced by {s, s+1, ... ,n}. |
| 39 | j.adjacent = t.sccSubGraph(2) // Only allow SCCs with >= 2 vertices. |
| 40 | if len(j.adjacent) == 0 { |
| 41 | break |
| 42 | } |
| 43 | |
| 44 | // s = least vertex in V_k |
| 45 | for _, v := range j.adjacent { |
| 46 | s := len(j.adjacent) |
| 47 | for n := range v { |
| 48 | if n < s { |
| 49 | s = n |
| 50 | } |
| 51 | } |
| 52 | if s < j.s { |
| 53 | j.s = s |
| 54 | } |
| 55 | } |
| 56 | for i, v := range j.adjacent { |
| 57 | if len(v) > 0 { |
| 58 | j.blocked[i] = false |
| 59 | j.b[i] = make(set) |
| 60 | } |
| 61 | } |
| 62 | |
| 63 | //L3: |
| 64 | _ = j.circuit(j.s) |
| 65 | j.s++ |
| 66 | } |
| 67 | |
| 68 | return j.result |
| 69 | } |
| 70 | |
| 71 | // circuit is the CIRCUIT sub-procedure in the paper. |
| 72 | func (j *johnson) circuit(v int) bool { |