package PAZ1b.cvicenie08;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

import sk.upjs.jpaz2.*;

public class Launcher {

        // Vytvori ku neohodnotenemu grafu prisluchajucu maticu susednosti
//      public static boolean[][] grafNaMaticuSusednosti(Graph g) {
//              Vertex[] vrcholyVPoli = g.createVertexArray();
//              boolean[][] matica = g.createAdjacencyMatrix(vrcholyVPoli);
//              return matica;
//      }

        // Otestuje suvislost neorientovaneho grafu zadaneho maticou susednosti
        public static boolean suvislostNeorientovaneho(boolean[][] matica) {
                // Vyberieme pocet vrcholov grafu
                int n = matica.length;

                // Vytvorime pole na evidenciu navstivenia vrcholu (default je false)
                boolean[] navstiveny = new boolean[n];

                // Vytvorime rad pre navstivene vrcholy, ktorych susedov sme zatial
                // neskusali navstivit
                Queue<Integer> rad = new LinkedList<Integer>();

                // Na zaciatku je navstiveny iba startovaci vrchol
                navstiveny[0] = true;
                rad.offer(0);

                // Kym rad nie je prazdny
                while (!rad.isEmpty()) {
                        // Vyberieme prvy vrchol v rade
                        int vIdx = rad.poll();

                        // Postupne vsetkych nenavstivenych susedov vrcholu oznacime ako
                        // navstivenych a pridame ich do radu
                        for (int i = 0; i < n; i++)
                                if ((matica[vIdx][i]) && (!navstiveny[i])) {
                                        navstiveny[i] = true;
                                        rad.offer(i);
                                }
                }

                // Zistime, ci ostal nejaky vrchol nenavstiveny
                for (int i = 0; i < n; i++)
                        if (!navstiveny[i])
                                return false;

                return true;
        }

        public static int[] vzdialenostiOdStartovaciehoVrcholu(boolean[][] matica, int start) {
                // metoda vrati pole kde na i-tom indexe je vzdialenost vrcholu i od
                // startovacieho vrcholu
                // Vyberieme pocet vrcholov grafu
                int n = matica.length;

                int[] vzdialenosti = new int[n];
                Arrays.fill(vzdialenosti, -1);

                // Vytvorime rad pre navstivene vrcholy, ktorych susedov sme zatial
                // neskusali navstivit
                Queue<Integer> rad = new LinkedList<Integer>();

                // Na zaciatku je navstiveny iba startovaci vrchol
                vzdialenosti[start] = 0;
                rad.offer(start);

                // Kym rad nie je prazdny
                while (!rad.isEmpty()) {
                        // Vyberieme prvy vrchol v rade
                        int vIdx = rad.poll();

                        // Postupne vsetkych nenavstivenych susedov vrcholu oznacime ako
                        // navstivenych a pridame ich do radu
                        for (int i = 0; i < n; i++)
                                if ((matica[vIdx][i]) && (vzdialenosti[i] == -1)) {
                                        rad.offer(i);
                                        vzdialenosti[i] = vzdialenosti[vIdx] + 1;
                                }
                }

                return vzdialenosti;
        }

        public static void vypisCestu(boolean[][] matica, int start, int ciel) {
                // metoda vypise cestu zo startovacieho vrcholu do cieloveho vrcholu
        }

        public static void main(String[] args) {
                // vytvorim si maticu susednosti pre graf
                boolean[][] graf = new boolean[5][5];
                graf[0][1] = true;
                graf[1][0] = true;
                graf[1][2] = true;
                graf[2][1] = true;
                graf[2][3] = true;
                graf[3][2] = true;
                graf[3][4] = true;
                graf[4][3] = true;
                graf[2][4] = true;
                graf[4][2] = true;

                // vypisem maticu susednosti pre graf
                for (int i = 0; i < graf.length; i++) {
                        for (int j = 0; j < graf[0].length; j++) {
                                System.out.print(graf[i][j] + "\t");
                        }
                        System.out.println();
                }

                System.out.println(Arrays.toString(vzdialenostiOdStartovaciehoVrcholu(graf, 2)));

        }
}