Groovy web console

subscribe to the feed Subscribe
to this
site

Detect cycles in a directed graph

Published 4 weeks ago by Horia with tags cycles graph
Actions  ➤ Edit in console Back to console Show/hide line numbers View recent scripts
def edges2 = [
        ['u', 'v'],
        ['u', 'x'],
        ['v', 'y'],
        ['w', 'y'],
        ['w', 'z'],
        ['x', 'v'],
        ['y', 'x'],
        ['z', 'z']]

def edges8 = [
        [1, 2],
        [2, 3],
        [3, 4],
        [4, 1],
        [3, 5],
        [5, 6],
        [6, 3]
]

def edges0 = [
        ['u', 'v'],
        ['v', 'x'],
        ['x', 'y'],
        ['y', 'q'],
        ['x', 'r']]

def adj = edges2.groupBy { it[0] }
        .collectEntries { n, egs -> [n, egs.collect { it[1] }] }

println adj

def discovered = new LinkedHashSet()
def finished = new LinkedHashSet()
def cycles = []

for (u in adj.keySet()) {
    if (!(u in discovered) && !(u in finished)) {
        dfs_visit(adj, u, discovered, finished, cycles)
    }
}

println("found $cycles.size cycles")

def dfs_visit(adj, u, discovered, finished, cycles) {

    discovered.add(u)

    for (v in adj[u]) {
        //Detect cycles
        if (v in discovered) {
            def tail = discovered.dropWhile { v != it }
            println("Cycle detected: found a back edge from $u to $v : $tail")
            cycles << tail
            break
        }

        //Recurse into DFS tree
        if (!(v in finished)) {
            dfs_visit(adj, v, discovered, finished, cycles)
        }
    }
    discovered.remove(u)
    finished.add(u)
}