8. cvičenie

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

public class Grafy {

        /**
         * Realizuje prehladavanie do sirky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Integer> bfs(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Integer> navstiveny = new HashMap<Vertex, Integer>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, -1);

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

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

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

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

                return navstiveny;
        }

        /**
         * Realizuje rekurzivne prehladavanie do hlbky
         *
         * @param v
         *            vrchol, ktory ideme navstivit
         * @param navstiveny
         *            mapa, v ktorej mame informaciu o tom, ktore vrcholi boli
         *            navstivene
         */
        public static void dfs(Vertex v, Map<Vertex, Boolean> navstiveny) {
                navstiveny.put(v, true);

                // Navstivime vsetkych nenavstivenych susedov
                for (Vertex sused : v.getOutNeighbours())
                        if (!navstiveny.get(sused))
                                dfs(sused, navstiveny);
        }

        /**
         * Realizuje (spusti) rekurzivne prehladavanie do hlbky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> dfsRekurzivne(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

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

        /**
         * Realizuje nerekurzivne prehladavanie do hlbky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> dfsNerekurzivne(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

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

                // Na zaciatku je navstiveny iba startovaci vrchol
                navstiveny.put(start, true);
                zasobnik.push(start);

                while (!zasobnik.isEmpty()) {
                        // Vyberieme vrchol z vrchu zasobnika
                        Vertex v = zasobnik.pop();

                        // Postupne vsetkych nenavstivenych susedov vrcholu v oznacime ako
                        // navstivenych a pridame ich na vrch zasobnika
                        for (Vertex sused : v.getOutNeighbours())
                                if (!navstiveny.get(sused)) {
                                        navstiveny.put(sused, true);
                                        zasobnik.push(sused);
                                }
                }

                return navstiveny;
        }

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

                List<Vertex> vysledok = new ArrayList<Vertex>();
                Vertex aktualny = kam;
                while (vzdialenosti.get(aktualny) > 0) {
                        vysledok.add(aktualny);
                        Vertex najblizsi = aktualny;
                        for (Vertex sused: aktualny.getInNeighbours())
                                if (vzdialenosti.get(sused) < vzdialenosti.get(najblizsi)) {
                                        najblizsi = sused;
                                }

                        aktualny = najblizsi;
                }
                vysledok.add(aktualny);
                Collections.reverse(vysledok);
                return vysledok;
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf
                Graph fb = new Graph();
                // Nacitame zoznam hran zo suboru
                fb.loadFromFile("graf.txt");

                System.out.println(fb);

                // Spustime rekurzivne dfs
                Map<Vertex, Integer> vzdialenosti = bfs(fb, fb.getVertex("5"));
                System.out.println(cestaZ(vzdialenosti, fb.getVertex("9")));
        }
}

import java.util.*;

import sk.upjs.paz.*;

public class Grafy {

        /**
         * Realizuje prehladavanie do sirky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Integer> bfs(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Integer> navstiveny = new HashMap<Vertex, Integer>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, -1);

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

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

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

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

                return navstiveny;
        }

        /**
         * Realizuje rekurzivne prehladavanie do hlbky
         *
         * @param v
         *            vrchol, ktory ideme navstivit
         * @param navstiveny
         *            mapa, v ktorej mame informaciu o tom, ktore vrcholi boli
         *            navstivene
         */
        public static void dfs(Vertex v, Map<Vertex, Boolean> navstiveny) {
                navstiveny.put(v, true);

                // Navstivime vsetkych nenavstivenych susedov
                for (Vertex sused : v.getOutNeighbours())
                        if (!navstiveny.get(sused))
                                dfs(sused, navstiveny);
        }

        /**
         * Realizuje (spusti) rekurzivne prehladavanie do hlbky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> dfsRekurzivne(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

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

        /**
         * Realizuje nerekurzivne prehladavanie do hlbky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> dfsNerekurzivne(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

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

                // Na zaciatku je navstiveny iba startovaci vrchol
                navstiveny.put(start, true);
                zasobnik.push(start);

                while (!zasobnik.isEmpty()) {
                        // Vyberieme vrchol z vrchu zasobnika
                        Vertex v = zasobnik.pop();

                        // Postupne vsetkych nenavstivenych susedov vrcholu v oznacime ako
                        // navstivenych a pridame ich na vrch zasobnika
                        for (Vertex sused : v.getOutNeighbours())
                                if (!navstiveny.get(sused)) {
                                        navstiveny.put(sused, true);
                                        zasobnik.push(sused);
                                }
                }

                return navstiveny;
        }

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

                List<Vertex> vysledok = new ArrayList<Vertex>();
                Vertex aktualny = kam;
                while (vzdialenosti.get(aktualny) > 0) {
                        vysledok.add(aktualny);
                        Vertex najblizsi = aktualny;
                        for (Vertex sused : aktualny.getInNeighbours())
                                if (vzdialenosti.get(sused) < vzdialenosti.get(najblizsi)) {
                                        najblizsi = sused;
                                }

                        aktualny = najblizsi;
                }
                vysledok.add(aktualny);
                Collections.reverse(vysledok);
                return vysledok;
        }

        // Vytvori ku neohodnotenemu grafu prisluchajucu maticu susednosti
        public static boolean[][] grafNaMaticuSusednosti(Graph g) {
                // Vyrobime pole vrcholov
                Vertex[] vrcholy = new Vertex[g.getVertices().size()];
                int idx = 0;
                for (Vertex v : g.getVertices()) {
                        vrcholy[idx] = v;
                        idx++;
                }

                // Vyrobime maticu susednosti
                boolean[][] matica = new boolean[vrcholy.length][vrcholy.length];
                for (int i = 0; i < vrcholy.length; i++)
                        for (int j = 0; j < vrcholy.length; j++)
                                matica[i][j] = g.hasEdge(vrcholy[i], vrcholy[j]);

                return matica;
        }

        public static void bfsSMaticou(boolean[][] matica, int start,
                        boolean[] bolNavstiveny) {
                Queue<Integer> rad = new LinkedList<Integer>();
                rad.offer(start);
                bolNavstiveny[start] = true;
                while(!rad.isEmpty()){
                        int v = rad.poll();
                        for (int i = 0; i < bolNavstiveny.length; i++) {
                                if ((matica[i][v] == true)&& (bolNavstiveny[i]==false)) {
                                        bolNavstiveny[i]=true;
                                        rad.offer(i);
                                }
                        }
                }
        }

        public static boolean jeNejakyNenavstiveny(boolean[] bolNavstiveny) {
                for (int i = 0; i < bolNavstiveny.length; i++) {
                        if (bolNavstiveny[i] == false) {
                                return true;
                        }
                }
                return false;
        }

        public static int nejakyNenavstivenyIdx(boolean[] bolNavstiveny) {
                for (int i = 0; i < bolNavstiveny.length; i++) {
                        if (bolNavstiveny[i] == false) {
                                return i;
                        }
                }
                return -1;
        }

        public static int pocetKomponentov(boolean[][] matica) {
                boolean[] bolNavstiveny = new boolean[matica.length];
                int vysledok = 0;
                while (jeNejakyNenavstiveny(bolNavstiveny)) {
                        bfsSMaticou(matica, nejakyNenavstivenyIdx(bolNavstiveny),
                                        bolNavstiveny);
                        vysledok++;
                }

                return vysledok;
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf
                Graph fb = new Graph();
                // Nacitame zoznam hran zo suboru
                fb.loadFromFile("graf.txt");

                boolean[][] matica = grafNaMaticuSusednosti(fb);
                System.out.println(pocetKomponentov(matica));

                System.out.println(bfs(fb, fb.getVertex("1")));
        }
}