8. cvičenie

import java.util.*;

import sk.upjs.paz.graph.*;

public class GrafovyPrehladavac {

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

        /**
         * Vytvori novy grafovy prehladavac.
         *
         * @param g
         *            graf, ktory ma byt vytvorenym prehladavacom prehladavany.
         */
        public GrafovyPrehladavac(Graph g) {
                this.g = 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>();

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

        public static List<Vertex> cestaZ(Graph g,
                        Map<Vertex, Integer> vzdialenosti, Vertex kam) {
                List<Vertex> cesta = new ArrayList<Vertex>();
                cesta.add(kam);
                while(vzdialenosti.get(kam) != 0){
                        for (Vertex sused : kam.getOutNeighbours()) {
                                if (vzdialenosti.get(sused) == vzdialenosti.get(kam) - 1) {
                                        cesta.add(sused);
                                        kam = sused;
                                        break;
                                }
                        }

                }
                return cesta;
        }

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

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

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

                // Spustime vyhladavanie z aktualneho vrchola
                dfs(start, navstiveny);
                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);

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

                        // Ak uz bol navstiveny, tak "nie je co robit" a ideme dalej
                        if (navstiveny.get(v)) {
                                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);
                }

                return navstiveny;
        }

        /**
         * @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)
                System.out.println(gp.bfs(g.getVertex("A")));

                System.out.println(gp.cestaZ(g, gp.bfs(g.getVertex("A")), g.getVertex("E")));
        }
}

import java.util.*;

import sk.upjs.paz.graph.*;

public class GrafovyPrehladavac {

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

        /**
         * Vytvori novy grafovy prehladavac.
         *
         * @param g
         *            graf, ktory ma byt vytvorenym prehladavacom prehladavany.
         */
        public GrafovyPrehladavac(Graph g) {
                this.g = 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>();

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

        public static List<Vertex> cestaZ(Graph g,
                        Map<Vertex, Integer> vzdialenosti, Vertex kam) {
                List<Vertex> cesta = new ArrayList<Vertex>();
                cesta.add(kam);
                while (vzdialenosti.get(kam) != 0) {
                        for (Vertex sused : kam.getOutNeighbours()) {
                                if (vzdialenosti.get(sused) == vzdialenosti.get(kam) - 1) {
                                        cesta.add(sused);
                                        kam = sused;
                                        break;
                                }
                        }

                }
                return cesta;
        }

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

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

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

                // Spustime vyhladavanie z aktualneho vrchola
                dfs(start, navstiveny);
                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);

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

                        // Ak uz bol navstiveny, tak "nie je co robit" a ideme dalej
                        if (navstiveny.get(v)) {
                                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);
                }

                return navstiveny;
        }

        public boolean suvislostGrafu(Vertex v, Graph g) {

                Map<Vertex, Boolean> navstiveny = g.createVertexMap(false);

                dfs(v, navstiveny);

                for (Vertex vrchol : navstiveny.keySet()) {
                        if (navstiveny.get(vrchol) == false) {

                                return false;
                        }
                }
                return true;
        }

        private void dfsPreKomponenty(Vertex v, Map<Vertex, Integer> navstiveny, int IDkomponent) {
                navstiveny.put(v, IDkomponent);

                // Navstivime vsetkych nenavstivenych susedov
                for (Vertex sused : v.getOutNeighbours())
                        if (navstiveny.get(sused)==-1)
                                dfsPreKomponenty(sused, navstiveny, IDkomponent);
        }

        public Vertex vratNenavstivenyVrchol(Map<Vertex, Integer> navstiveny) {
                for (Vertex v : navstiveny.keySet()) {
                        if(navstiveny.get(v)==-1){
                                return v;
                        }
                }
                return null;
        }

        public int pocetKomponentov(Graph g) {

                int komponent = 0;

                Map<Vertex, Integer> navstiveny = g.createVertexMap(-1);

//              System.out.println(g.getVertices().toArray()[0]);

                while (vratNenavstivenyVrchol(navstiveny)!=null) {

                        dfsPreKomponenty(vratNenavstivenyVrchol(navstiveny), navstiveny, komponent);
                        komponent++;
                }

                System.out.println(navstiveny.values());

                System.out.println(navstiveny.toString());


                int[]pole = new int[komponent];

                for (Vertex v : navstiveny.keySet()) { 
                        pole[navstiveny.get(v)]++;                     
                }

                int max = -10;

                for (int i = 0; i < pole.length; i++) {
                        if (pole[i]> max){
                                max = pole[i];
                        }
                }              

                System.out.println("počet vrcholov najväčšieho komponentu grafu:) " + max);
                return komponent;


        }




        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf nacitanim zo suboru
                Graph g1 = Graph.createFromFile("graf1.txt");
                Graph g2 = Graph.createFromFile("graf2.txt");
                GrafovyPrehladavac prehl = new GrafovyPrehladavac(g1);
                System.out.println(prehl.suvislostGrafu(g1.getVertex("A"), g1));

                GrafovyPrehladavac preh2 = new GrafovyPrehladavac(g2);
                System.out.println(preh2.suvislostGrafu(g2.getVertex("A"), g2));
                System.out.println("pocet komponentov: "+preh2.pocetKomponentov(g2));

        }
}