Finding cycles in a directed graph using DFS and back edges

cycle-finder.groovy

interface DfsVisitor {
    void preorder(v)
    
    void postorder(v)
    
    void beforeChild(v)
    
    void afterChild(v)
    
    void skipChild(v)
}


class Dfs {

    /**
     * Set V of vertices
     */
    def V
    
    /**
     * Adj(v) - all vertices adjacent to v
     */
    def Adj

    def visited = [:]
    
    public Dfs(V, Adj) {
        this.V   = V
        this.Adj = Adj
    }

    public visit(DfsVisitor visitor) {
      for(u in V) {
            if(!visited[u]) {
                dfsVisit(u, visitor)
            }
        } 
    }
    
    def private dfsVisit(u, visitor) {
        visited[u] = true
        visitor.preorder(u)
        for(v in Adj(u)) {     
            if(!visited[v]) {
                visitor.beforeChild(v)
                dfsVisit(v, visitor)
                visitor.afterChild(v)
            } else {
                visitor.skipChild(v)
            }
        }
        visitor.postorder(u)
    }
}



/**
 * Detecting cycles in a directed graph
 */
class CycleFinder implements DfsVisitor{

    def path = new Stack()
     
    def cycles = []
    
     
    void preorder(v) {
        path.push(v)
    }
    
    void postorder(v) {
        path.pop()
    }
    
    void beforeChild(v) {
      findBackEdge(v)
    }
    
    void afterChild(v) {
    
    }
    
    void skipChild(v) {
      findBackEdge(v)
    }
    
    def private findBackEdge(v) {
        int i = path.indexOf(v)
        if(i != -1) {
            def cycle = new ArrayList(path[i..-1])
            cycles.add(cycle)
        }       
    }
    
    def cycles() { return cycles}
}