package com.gansuer.algorithms.graphs;

/**
 * Cycle detection: Is a given graph acyclic
 * TODO: to complete
 *
 * Created by Frank on 6/28/16.
 */
public class Cycle {

    public Cycle(Graph g) {

    }

    private boolean hasSelfLoop(Graph g) {
        return false;
    }

    private boolean hasParallelEdges(Graph g) {
        return false;
    }

    public boolean hasCycle() {
        return false;
    }

    public Iterable<Integer> getCycle() {
        return null;
    }


}

@@ -33,16 +33,41 @@
 raphs;%0A%0A
+import java.util.Stack;%0A%0A
 /**%0A * C
@@ -130,16 +130,20 @@
 plete%0A *
+ %3Cp%3E
 %0A * Crea
@@ -202,31 +202,544 @@
    p
-ublic Cycle(Graph g) %7B%0A
+rivate Stack%3CInteger%3E cycle;%0A    private boolean%5B%5D marked;%0A    private int%5B%5D edgeTo;%0A%0A    public Cycle(Graph graph) %7B%0A        if (graph == null) throw new IllegalArgumentException(%22graph is null%22);%0A        if (hasSelfLoop(graph)) return;%0A        if (hasParallelEdges(graph)) return;%0A        marked = new boolean%5Bgraph.getVertices()%5D;%0A        edgeTo = new int%5Bgraph.getVertices()%5D;%0A        for (int v = 0; v %3Cgraph.getVertices();v++)%7B%0A            if (cycle == null && !marked%5Bv%5D)%7B%0A                dfs(graph,-1,v);%0A            %7D%0A        %7D
 %0A   
@@ -773,32 +773,36 @@
 SelfLoop(Graph g
+raph
 ) %7B%0A        retu
@@ -801,76 +801,924 @@
     
-return false;%0A    %7D%0A%0A    private boolean hasParallelEdges(Graph g) %7B
+for (int v = 0; v %3C graph.getVertices(); v++) %7B%0A            for (int w : graph.adj(v)) %7B%0A                if (v == w) %7B%0A                    cycle = new Stack%3C%3E();%0A                    cycle.push(v);%0A                    cycle.push(v);%0A                    return true;%0A                %7D%0A            %7D%0A        %7D%0A        return false;%0A    %7D%0A%0A    private boolean hasParallelEdges(Graph graph) %7B%0A        marked = new boolean%5Bgraph.getVertices()%5D;%0A%0A        for (int v = 0; v %3C graph.getVertices(); v++) %7B%0A            for (int w : graph.adj(v)) %7B%0A                if (marked%5Bw%5D) %7B%0A                    cycle = new Stack%3C%3E();%0A                    cycle.push(v);%0A                    cycle.push(w);%0A                    cycle.push(v);%0A                    return true;%0A                %7D%0A                marked%5Bw%5D = true;%0A            %7D%0A            for (int w : graph.adj(v)) %7B%0A                marked%5Bw%5D = false;%0A            %7D%0A        %7D
 %0A   
@@ -1782,37 +1782,50 @@
 %0A        return 
-false
+this.cycle != null
 ;%0A    %7D%0A%0A    pub
@@ -1874,24 +1874,553 @@
  return 
-null;%0A    %7D%0A
+cycle;%0A    %7D%0A%0A    private void dfs(Graph graph, int v, int w) %7B%0A        marked%5Bw%5D = true;%0A        for (int adj : graph.adj(w))%7B%0A            if (cycle != null) return;%0A            if (!marked%5Badj%5D)%7B%0A                edgeTo%5Badj%5D = w;%0A                dfs(graph,w,adj);%0A            %7Delse if (adj != v)%7B%0A                cycle = new Stack%3C%3E();%0A                for (int x = w; x != adj; x = edgeTo%5Bx%5D)%7B%0A                    cycle.push(x);%0A                %7D%0A                cycle.push(adj);%0A                cycle.push(w);%0A            %7D%0A        %7D%0A    %7D
 %0A%0A%7D%0A

update cycle