A8

import java.awt.Color;
import java.util.*;
import sk.upjs.paz.graph.*;
import sk.upjs.paz.graphvisualizer.GraphVisualizer;

public class GrafovyPrehladavac {

        /**
         * Graf, ktory je prehladavany a skumany.
         */
        private Graph g;

        /**
         * Visualizator skumaneho grafu.
         */
        private GraphVisualizer gv;

        /**
         * Vytvori novy grafovy prehladavac.
         *
         * @param g
         *            graf, ktory ma byt vytvorenym prehladavacom prehladavany.
         */
        public GrafovyPrehladavac(Graph g) {
                this.g = g;
                this.gv = new GraphVisualizer(g);
        }

        /**
         * Realizuje prehladavanie do sirky
         *
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public Map<Vertex, Integer> bfs(Vertex start) {
                // Vytvorime mapu vrcholov a vsetky vrcholy nastavime ako nenavstivene
                Map<Vertex, Integer> navstiveny = g.createVertexMap(-1);

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

                // Nechame vizualizovat map-u a rad
                gv.addToMonitor("navstiveny", navstiveny);
                gv.addToMonitor("rad", rad);

                gv.pause("Po inicializacii.");

                // Na zaciatku je navstiveny iba startovaci vrchol
                navstiveny.put(start, 0);
                rad.offer(start);

                gv.setColor(start, Color.green);
                gv.pause("Po spracovani startovacieho vrcholu.");

                // Kym rad nie je prazdny
                while (!rad.isEmpty()) {
                        gv.pause("Nova iteracia while-cyklu");

                        // Vyberieme prvy vrchol v rade
                        Vertex v = rad.poll();

                        gv.setColor(v, Color.red);
                        gv.pause("Po vybrani spracovavaneho vrcholu: " + v);

                        // Postupne vsetkych nenavstivenych susedov vrcholu v oznacime ako
                        // navstivenych a pridame ich do radu
                        for (Vertex sused : v.getOutNeighbours())
                                if (navstiveny.get(sused) == -1) {
                                        navstiveny.put(sused, navstiveny.get(v) + 1);
                                        rad.offer(sused);

                                        // Poznacime objavitelnu hranu a to, ze sused bol navstiveny
                                        gv.setColor(g.getEdge(v, sused), Color.red);
                                        gv.setColor(sused, Color.green);
                                        gv.pause("Novy nenavstiveny sused " + sused + " vrcholu "
                                                        + v);
                                }

                        gv.setColor(v, Color.green);
                }

                gv.pause("BFS skoncene");
                gv.removeFromMonitor(navstiveny);
                gv.removeFromMonitor(rad);
                gv.resetAllColors();

                return navstiveny;
        }

        /**
         * Realizuje rekurzivne prehladavanie do hlbky
         *
         * @param v
         *            vrchol, ktory ideme navstivit
         * @param navstiveny
         *            mapa, v ktorej mame informaciu o tom, ktore vrcholy boli
         *            navstivene
         */
        private void dfs(Vertex v, Map<Vertex, Boolean> navstiveny) {
                navstiveny.put(v, true);
                gv.setColor(v, Color.red);
                gv.pause("Navstevujeme vrchol " + v);

                // Navstivime vsetkych nenavstivenych susedov
                for (Vertex sused : v.getOutNeighbours())
                        if (!navstiveny.get(sused)) {
                                gv.setColor(g.getEdge(v, sused), Color.red);
                                dfs(sused, navstiveny);
                        }

                gv.setColor(v, Color.green);
        }

        /**
         * Realizuje (spusti) rekurzivne prehladavanie do hlbky
         *
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public Map<Vertex, Boolean> dfsRekurzivne(Vertex start) {
                // Vytvorime mapu vrcholov a vsetky vrcholy nastavime ako nenavstivene
                Map<Vertex, Boolean> navstiveny = g.createVertexMap(false);

                // Nechame vizualizovat map-u a rad
                gv.addToMonitor("navstiveny", navstiveny);
                gv.pause("Po inicializacii.");

                // Spustime vyhladavanie z aktualneho vrchola
                dfs(start, navstiveny);

                gv.pause("Po skonceni rekurzivneho DFS");
                gv.removeFromMonitor(navstiveny);
                gv.resetAllColors();
                return navstiveny;
        }

        /**
         * Realizuje nerekurzivne prehladavanie do hlbky
         *
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public Map<Vertex, Boolean> dfsNerekurzivne(Vertex start) {
                // Vytvorime mapu vrcholov a vsetky vrcholy nastavime ako nenavstivene
                Map<Vertex, Boolean> navstiveny = g.createVertexMap(false);

                // Vytvorime zasobnik pre vrcholy, ktore mame navstivit
                Stack<Vertex> zasobnik = new Stack<Vertex>();

                // Poznacime si, ze mame preskumat startovaci vrchol
                zasobnik.push(start);

                // Nechame vizualizovat map-u a zasobnik
                gv.addToMonitor("navstiveny", navstiveny);
                gv.addToMonitor("zasobnik", zasobnik);
                gv.pause("Po inicializacii.");

                // Kym zasobnik nie je prazdny
                while (!zasobnik.isEmpty()) {
                        // Vyberieme vrchol na vrchu zasobnika
                        Vertex v = zasobnik.pop();

                        gv.setColor(v, Color.red);
                        gv.pause("Zo zasobnika sme vybrali " + v);

                        // Ak uz bol navstiveny, tak "nie je co robit" a ideme dalej
                        if (navstiveny.get(v)) {
                                gv.setColor(v, Color.green);
                                continue;
                        }

                        // Oznacime, ze vrchol je navstiveny
                        navstiveny.put(v, true);

                        // Vsetkych nenavstiveny susedov vrcholu v pridame do zasobnika
                        for (Vertex sused : v.getOutNeighbours())
                                if (!navstiveny.get(sused))
                                        zasobnik.push(sused);

                        gv.setColor(v, Color.green);
                        gv.pause("Po spracovani nenavstiveneho " + v);
                }

                gv.pause("Po skonceni nerekurzivneho DFS");
                gv.removeFromMonitor(navstiveny);
                gv.removeFromMonitor(zasobnik);
                gv.resetAllColors();

                return navstiveny;
        }

        public static List<Vertex> cestaZ(Graph g,
                        Map<Vertex, Integer> vzdialenosti, Vertex kam) {
                if (vzdialenosti.get(kam) == -1) {
                        return null;
                }

                List<Vertex> cesta = new ArrayList<Vertex>();
                cesta.add(kam);
                while (vzdialenosti.get(kam) > 0) {
                        for (Vertex sused : kam.getInNeighbours()) {
                                if (vzdialenosti.get(sused) == vzdialenosti.get(kam) - 1) {
                                        cesta.add(sused);
                                        kam = sused;
                                        break;
                                }
                        }
                }

                Collections.reverse(cesta);            
                return cesta;
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf nacitanim zo suboru
                Graph g = Graph.createFromFile("graf.txt");

                // Vytvorime grafovy prehladavac vytvoreneho grafu
                GrafovyPrehladavac gp = new GrafovyPrehladavac(g);

                // Spustime bfs (prehladavanie do sirky)
                Map<Vertex, Integer> vzd = gp.bfs(g.getVertex("A"));
                List<Vertex> cesta = cestaZ(g, vzd, g.getVertex("F"));
        }
}

import java.lang.reflect.Array;
import java.util.*;

import sk.upjs.paz.graph.*;

public class MatGrafy {

        // Vytvori ku neohodnotenemu grafu prisluchajucu maticu susednosti
        public static boolean[][] grafNaMaticuSusednosti(Graph g) {
                Vertex[] vrcholyVPoli = g.createVertexArray();
                System.out.println(Arrays.toString(vrcholyVPoli));
                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[] vzdialenost(boolean[][] matica, int odkialIdx) {
                int n = matica.length;

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

                Queue<Integer> rad = new LinkedList<Integer>();

                vzd[odkialIdx] = 0;
                rad.offer(odkialIdx);

                while (!rad.isEmpty()) {
                        int vIdx = rad.poll();

                        for (int i = 0; i < n; i++)
                                if ((matica[vIdx][i]) && (vzd[i] == -1)) {
                                        vzd[i] = vzd[vIdx] + 1;
                                        rad.offer(i);
                                }
                }

                return vzd;
        }

        public static void znackovaciBFS(boolean[][] matica, int startIdx,
                        int[] idKomponentu, int znacka) {
                int n = matica.length;
                Queue<Integer> rad = new LinkedList<Integer>();
                idKomponentu[startIdx] = znacka;
                rad.offer(startIdx);

                while (!rad.isEmpty()) {
                        int vIdx = rad.poll();

                        for (int i = 0; i < n; i++)
                                // if ((matica[vIdx][i]) && (idKomponentu[i] == -1))
                                if ((matica[vIdx][i]) && (idKomponentu[i] != znacka)) {
                                        idKomponentu[i] = znacka;
                                        rad.offer(i);
                                }
                }
        }

        // Otestuje suvislost neorientovaneho grafu zadaneho maticou susednosti
        public static int pocetKomponentov(boolean[][] matica) {
                int[] idKomponentu = new int[matica.length];
                Arrays.fill(idKomponentu, -1);

                int pocetKomponentov = 0;
                for (int i = 0; i < matica.length; i++)
                        if (idKomponentu[i] == -1) {
                                znackovaciBFS(matica, i, idKomponentu, pocetKomponentov);
                                pocetKomponentov++;
                        }

                return pocetKomponentov;
        }

        public static void main(String[] args) {
                Graph g = Graph.createFromFile("graf.txt");
                boolean[][] matica = grafNaMaticuSusednosti(g);
                int[] vzdialenosti = vzdialenost(matica, 0);
                System.out.println(Arrays.toString(vzdialenosti));
        }

}

import java.util.*;
import sk.upjs.paz.graph.*;

public class MGrafy {

        // 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[] vyratajVzdialenost(boolean[][] matica, int startIdx) {
                int n = matica.length;

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

                Queue<Integer> rad = new LinkedList<Integer>();

                vzdialenosti[startIdx] = 0;
                rad.offer(startIdx);

                while (!rad.isEmpty()) {
                        int vIdx = rad.poll();

                        for (int i = 0; i < n; i++)
                                if ((matica[vIdx][i]) && (vzdialenosti[i] == -1)) {
                                        vzdialenosti[i] = vzdialenosti[vIdx] + 1;
                                        rad.offer(i);
                                }
                }

                return vzdialenosti;
        }

        public void znackovanie(boolean[][] matica, int startIdx, int[] znacky,
                        int znacka) {
                int n = matica.length;

                Queue<Integer> rad = new LinkedList<Integer>();
                znacky[startIdx] = znacka;
                rad.offer(startIdx);

                while (!rad.isEmpty()) {
                        int vIdx = rad.poll();

                        for (int i = 0; i < n; i++)
                                if ((matica[vIdx][i]) && (znacky[i] != znacka)) {
                                        znacky[i] = znacka;
                                        rad.offer(i);
                                }
                }
        }

        public int pocetKomponentov(boolean[][] matica) {
                int[] znacky = new int[matica.length];
                Arrays.fill(znacky, -1);
                int pocetKomponentov = 0;

                for (int i = 0; i < znacky.length; i++)
                        if (znacky[i] == -1) {
                                znackovanie(matica, i, znacky, pocetKomponentov);
                                pocetKomponentov++;
                        }

                return pocetKomponentov;
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                Graph g = Graph.createFromFile("graf.txt");
                boolean[][] ms = grafNaMaticuSusednosti(g);
                System.out.println(suvislostNeorientovaneho(ms));
                System.out.println(Arrays.toString(vyratajVzdialenost(ms, 0)));
        }

}