BFS.java

import it.uniupo.graphLib.*;

import java.awt.List;
import java.util.*;

public class BFS {

    private GraphInterface myGraph;

    public BFS(GraphInterface g) {
        //System.out.println(g);
        this.myGraph = g;
    }

    //ES 1

    //Con questa variamente utilizzi founded al posto di S.
    //Founded è un array di Booleani, in questo modo puoi fare accesso posizionale ed ottimizzi l'algoritmo. (La contains ha costo n)
    public ArrayList<Integer> getNodesInOrderOfVisit(int sorgente) {
        if (this.myGraph.getOrder() <= sorgente) {
            throw new IllegalArgumentException("Sorgente errata");
        }
        ArrayList<Integer> returnList = new ArrayList<>();
        returnList.add(sorgente);
        boolean[] founded = new boolean[myGraph.getOrder()];
        Queue<Integer> q = new LinkedList<>();
        founded[sorgente] = true;
        q.add(sorgente);
        while (!q.isEmpty()) {
            int u = q.remove();
            Iterable<Integer> neighbors = this.myGraph.getNeighbors(u);
            for (int v : neighbors) {
                if (!founded[v]) {
                    founded[v] = true;
                    q.add(v);
                    returnList.add(v);
                }
            }
        }
        return returnList;
    }
    /*
    public ArrayList<Integer> getNodesInOrderOfVisit(int sorgente) {
        if (this.myGraph.getOrder() <= sorgente) {
            throw new IllegalArgumentException("Dimensione della Sorgente errata");
        }
        ArrayList<Integer> s = new ArrayList<>();
        ArrayList<Integer> valueToReturn = new ArrayList<>();
        s.add(sorgente);
        valueToReturn.add(sorgente);
        Queue<Integer> q = new LinkedList<>();
        q.add(sorgente);
        while (!q.isEmpty()) {
            int u = q.remove();
            List<Integer> neighbors = (List<Integer>) this.myGraph.getNeighbors(u);
            for (Integer v : neighbors) {
                if (!s.contains(v)) {
                    s.add(v);
                    q.add(v);
                    valueToReturn.add(v);
                }
            }
        }
        return valueToReturn;
    }
    */

    //ES 2
    public int[] getDistance(int sorgente) {
        if (this.myGraph.getOrder() <= sorgente) {
            throw new IllegalArgumentException("Dimensione della Sorgente errata");
        }
        boolean[] founded = new boolean[this.myGraph.getOrder()];
        Queue<Integer> q = new LinkedList<>();
        int[] returnArray = new int[this.myGraph.getOrder()];
        Arrays.fill(returnArray, -1);

        founded[sorgente] = true;
        q.add(sorgente);
        returnArray[sorgente] = 0;

        while (!q.isEmpty()) {
            int u = q.remove();
            Iterable<Integer> neighbors = this.myGraph.getNeighbors(u);
            for (Integer v : neighbors) {
                if (!founded[v]) {
                    founded[v] = true;
                    q.add(v);
                    returnArray[v] = returnArray[u] + 1;
                }
            }
        }
        return returnArray;
    }

    //Funzioni aggiuntive che trovi qui
    //https://www.dir.uniupo.it/pluginfile.php/1252187/mod_resource/content/23/BFSjava.pdf

    public int getDistance(int sorgente, int nodo) {
        if (this.myGraph.getOrder() <= sorgente) {
            throw new IllegalArgumentException("Nodo sorgente non presente nel grafo");
        }
        if (this.myGraph.getOrder() <= nodo) {
            throw new IllegalArgumentException("Nodo destinazione non presente nel grafo");
        }

        int[] distance = getDistance(sorgente);
        return distance[nodo];
    }

    public GraphInterface bfsTree(int sorgente) {
        if (this.myGraph.getOrder() <= sorgente) {
            throw new IllegalArgumentException("Dimensione della Sorgente errata");
        }
        boolean[] founded = new boolean[this.myGraph.getOrder()];
        Queue<Integer> q = new LinkedList<>();
        GraphInterface alberoBFSdallaSorgente = new UndirectedGraph(this.myGraph.getOrder());

        founded[sorgente] = true;
        q.add(sorgente);

        while (!q.isEmpty()) {
            int u = q.remove();
            Iterable<Integer> neighbors = this.myGraph.getNeighbors(u);
            for (Integer v : neighbors) {
                if (!founded[v]) {
                    founded[v] = true;
                    q.add(v);
                    alberoBFSdallaSorgente.addEdge(u, v);
                    //returnArray[v] = returnArray[u] + 1;
                }
            }
        }
        return alberoBFSdallaSorgente;
    }

    private DirectedGraph bfsTreeDirected(int sorgente) {
        if (this.myGraph.getOrder() <= sorgente) {
            throw new IllegalArgumentException("Dimensione della Sorgente errata");
        }
        boolean[] founded = new boolean[this.myGraph.getOrder()];
        Queue<Integer> q = new LinkedList<>();
        DirectedGraph alberoBFSdallaSorgente = new DirectedGraph(this.myGraph.getOrder());

        founded[sorgente] = true;
        q.add(sorgente);

        while (!q.isEmpty()) {
            int u = q.remove();
            Iterable<Integer> neighbors = this.myGraph.getNeighbors(u);
            for (Integer v : neighbors) {
                if (!founded[v]) {
                    founded[v] = true;
                    q.add(v);
                    alberoBFSdallaSorgente.addEdge(u, v);
                }
            }
        }
        return alberoBFSdallaSorgente;
    }

    private void cammminoMinimoImpl(DirectedGraph bfsAlbero, int sorg, int dest, ArrayList<Integer> path) {
        //Se ho trovato il nodo
        if (sorg == dest) {
            return;
        }

        //Se sono nella foglia sbagliata

        if (((Collection<?>) bfsAlbero.getNeighbors(sorg)).isEmpty()) {
            //Pulisco il percorso corrente perché errato
            path.clear();
        }


        //Allora devo ancora esplorare
        for (Integer node : bfsAlbero.getNeighbors(sorg)) {
            path.add(node);
            //System.out.println(">>> Nodo: " + node);
            cammminoMinimoImpl(bfsAlbero, node, dest, path);
            if (node == dest) {
                break;
            }
        }

    }


    public ArrayList<Integer> camminoMinimo(int sorgente, int destinazione) {
        //L'idea è quella di usare il BFS Albero, perché aciclico, ed in questo modo trovare il percorso.

        //Proviamo con la ricorsione

        //Implementazione sbagliata, ma l'idea credo sia giusta

        DirectedGraph bfsAlbero = bfsTreeDirected(sorgente);
        boolean[] founded = new boolean[this.myGraph.getOrder()];
        ArrayList<Integer> returnArray = new ArrayList<>();

        System.out.println(bfsAlbero);

        cammminoMinimoImpl(bfsAlbero, sorgente, destinazione, returnArray);


        return returnArray;
    }
}