C8

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, Boolean> bfs(Vertex start) {
                // Vytvorime mapu vrcholov a vsetky vrcholy nastavime ako nenavstivene
                Map<Vertex, Boolean> navstiveny = g.createVertexMap(false);

                // 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, true);
                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)) {
                                        navstiveny.put(sused, true);
                                        rad.offer(sused);
                                }
                }

                return navstiveny;
        }

        public Map<Vertex, Integer> bfsVzdialenost(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 int pocetKomponentovGrafu() {

                Map<Vertex, Boolean> navstiveny = g.createVertexMap(false);
                int pocetKomponentov = 0;
                while (navstiveny.containsValue(false)) {
                        for (Vertex vrchol : navstiveny.keySet()) {
                                if (navstiveny.get(vrchol) == false) {
                                        Map<Vertex, Boolean> zbfs = bfs(vrchol);
                                        pocetKomponentov++;
                                        for (Vertex vrcholzbfs : zbfs.keySet()) {
                                                if (zbfs.get(vrcholzbfs)) {
                                                        navstiveny.put(vrcholzbfs, true);
                                                }

                                        }
                                }
                        }
                }

                return pocetKomponentov;
        }

        public Map<Vertex, Integer> mapaKomponentovGrafu() {

                Map<Vertex, Integer> cisloKomponentu = g.createVertexMap(-1);
                Map<Vertex, Boolean> navstiveny = g.createVertexMap(false);
                int pocetKomponentov = 0;
                while (navstiveny.containsValue(false)) {
                        for (Vertex vrchol : navstiveny.keySet()) {
                                if (navstiveny.get(vrchol) == false) {
                                        Map<Vertex, Boolean> zbfs = bfs(vrchol);

                                        for (Vertex vrcholzbfs : zbfs.keySet()) {
                                                if (zbfs.get(vrcholzbfs)) {
                                                        navstiveny.put(vrcholzbfs, true);
                                                        cisloKomponentu.put(vrcholzbfs, pocetKomponentov);
                                                }
                                        }
                                        pocetKomponentov++;
                                }
                        }
                }

                return cisloKomponentu;
        }

        public static List<Vertex> cestaZ(Graph g,
                        Map<Vertex, Integer> vzdialenosti, Vertex kam) {

                if (vzdialenosti.get(kam) == -1)
                        return null;
                int aktualnaVzdialenost = vzdialenosti.get(kam);
                List<Vertex> cesta = new ArrayList<>();

                cesta.add(kam);
                Vertex v = kam;
                while (aktualnaVzdialenost > 0) {
                        for (Vertex sused : v.getOutNeighbours()) {
                                // kedze mame neorientovany graf getOutNeighbours() aj
                                // getInNeighbours() su identicke
                                if (vzdialenosti.get(sused) == vzdialenosti.get(v) - 1) {
                                        cesta.add(0, sused);
                                        aktualnaVzdialenost--;

                                        v = sused;
                                        break;// nemusi tam byt
                                }
                        }
                }

                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.bfsVzdialenost(g.getVertex("A")));
                System.out.println(gp.cestaZ(g, gp.bfsVzdialenost(g.getVertex("A")),
                                g.getVertex("C")));
                System.out.println(gp.pocetKomponentovGrafu());
                System.out.println(gp.mapaKomponentovGrafu());
        }
}

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

import sk.upjs.paz.graph.Graph;

public class GrafyMaticou {

        /**
         * @param args
         */

        // 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 void main(String[] args) {
                // TODO Auto-generated method stub

                // Vytvorime graf nacitanim zo suboru
                Graph g = Graph.createFromFile("graf.txt");
                System.out.println(g.getVertices());

                boolean[][] matica=grafNaMaticuSusednosti(g);
                for(int i=0;i<matica.length;i++){
                        for(int j=0;j<matica[0].length;j++){
                                System.out.print(matica[i][j]+" ");
                        }
                        System.out.println();
                }
        }
}