BFSAndDFSApp.java

import it.uniupo.graphLib.GraphInterface;
import it.uniupo.graphLib.UndirectedGraph;

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;
    }

    private boolean hasDirCycleImpl(int sorg) {
        scoperti[sorg] = true;
        for (Integer node : myGraph.getNeighbors(sorg)) {
            if (!scoperti[node]) {
                fathers[node] = sorg;
                return hasDirCycleImpl(node);
            } else if (node != fathers[sorg]) {
                return true;
            }
        }
        return false;
    }

    public boolean hasDirCycle() {
        if (myGraph instanceof UndirectedGraph) {
            throw new IllegalArgumentException("Impossibile usare hasDirCycle su un grafo non orientato");
        }
        for (int i = 0; i < myGraph.getOrder(); i++) {
            fathers = new int[myGraph.getOrder()];
            scoperti = new boolean[myGraph.getOrder()];
            if (hasDirCycleImpl(i)) {
                return true;
            }
        }
        return false;
    }
}