Detect Cycle in Directed Graph

Given a directed graph, check whether the graph contains a cycle or not. Your function should return complete cycle path if given graph contains at least one cycle, else return null.

Java
Time complexity: O(V+E)
Space complexity: O(V) + O(h), where h is the longest path on call stack

public class DirectCycle<V>{


    public DirectCycle(){
    }

    public List<DirectedEdge<V>> getCycle(Digraph<V> g){
        if (g == null){
            throw new IllegalArgumentException("Invalid param passed!");
        }
        if (g.V() == 0 || g.E() == 0){
            return new ArrayList<>();
        }

        Set<V> whiteSet = new HashSet<>();//initial set of all vertexes
        Set<V> greySet = new HashSet<>();//vertexes processed on current stack
        Set<V> blackSet = new HashSet<>();//already processed vertexes
        Map<V,V> path = new HashMap<>();

        for (V v : g.getVertexes()){
            whiteSet.add(v);
        }

        while (!whiteSet.isEmpty()){
            V v = whiteSet.iterator().next();

            if (dfs(v, g, whiteSet, greySet, blackSet, path)){
                List<DirectedEdge<V>> cycle = buildCycle(v, path);
                return cycle;
            }
        }

        return null;
    }

    private List<DirectedEdge<V>> buildCycle(V v, Map<V, V> path) {
        List<DirectedEdge<V>> cycle = new ArrayList<>();
        V curr = v;
        while (path.containsKey(curr)){
            cycle.add(new DirectedEdge<V>(curr, path.get(curr)));
            V temp = path.get(curr);
            path.remove(curr);
            curr = temp;
        }
        return cycle;
    }

    private boolean dfs(V v, Digraph<V> g, Set<V> whiteSet, Set<V> greySet, Set<V> blackSet, Map<V,V> path){

        move(whiteSet, greySet, v);

        for (DirectedEdge<V> de : g.adj(v)){

            V neighb = de.to();
            path.put(v, neighb);

            if (blackSet.contains(neighb)){
                continue;
            }

            if (greySet.contains(neighb)){
                return true;
            }

            if (dfs(neighb, g, whiteSet, greySet, blackSet, path)){
                return true;
            }
        }

        move(greySet, blackSet, v);
        return false;

    }

    private void move(Set<V> source, Set<V> dest, V v){
        source.remove(v);
        dest.add(v);
    }

}

Advertisements

One thought on “Detect Cycle in Directed Graph

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s