import it.uniupo.graphLib.GraphInterface;

import java.util.Arrays;
import java.util.ArrayList;

public class BFSAndDFSApp {
    private GraphInterface myGraph;
    private BFS bfs;
    private DFS dfs;

    private boolean[] scoperti;
    private int[] fathers;
    GraphInterface treeDFS;

    public BFSAndDFSApp(GraphInterface g){
        myGraph = g;
        BFS bfs = new BFS(g);
        DFS dfs = new DFS(g);
        this.scoperti = new boolean[myGraph.getOrder()];
        this.treeDFS = this.myGraph.create();
        this.fathers = new int[myGraph.getOrder()];
        Arrays.fill(this.fathers, -1);
    }

    private boolean visitaDFS(int sorg) {
        if (sorg >= this.myGraph.getOrder() || sorg < 0) {
            throw new IllegalArgumentException("Sorgente non presenten nel grafo");
        }
        scoperti[sorg] = true;
        for (int node : this.myGraph.getNeighbors(sorg)) {
            if (!scoperti[node]) {
                fathers[node] = node;
                treeDFS.addEdge(sorg, node);
                return visitaDFS(node);
            }
            else if (node != fathers[node]){
                return true;
            }
        }
        return false;
    }

    public boolean hasUndirectedCycle() {
        for (int nodo = 0; nodo < this.myGraph.getOrder(); nodo++) {
            if(visitaDFS(nodo)){
                return true;
            }
        }
        return false;
    }

    private void visitaDFSPostVisit(int sorg, ArrayList<Integer> orderPostVisit) {
        if (sorg >= this.myGraph.getOrder() || sorg < 0) {
            throw new IllegalArgumentException("Sorgente non presenten nel grafo");
        }
        scoperti[sorg] = true;
        for (int node : this.myGraph.getNeighbors(sorg)) {
            if (!scoperti[node]) {
                visitaDFSPostVisit(node, orderPostVisit);
            }
        }
        orderPostVisit.add(sorg);
    }

    public ArrayList<Integer> getNodesInOrderPostVisit(int sorg){
        ArrayList<Integer> orderPostVisit = new ArrayList<>();
        visitaDFSPostVisit(sorg, orderPostVisit);
        return orderPostVisit;
    }
}