/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package Laboratoria6;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 * @author Mateusz Szczypek
 */
public class BFSGraph extends AGraph{

    public BFSGraph(int vertexCount) {
        super(vertexCount);
    }

   @Override
    public void writeMatrix() {
        System.out.print("\t");

        System.out.print("\n\n");

        for (int a=0;a<getSize();a++){
            System.out.println();
            for (int b=0;b<getSize();b++){
                System.out.print(matrix[a][b]+" ");
            }
        }
        System.out.print("\n\n\n");
    }

    @Override
    public boolean check(int i, int j) throws IllegalArgumentException {
        if (matrix[i][j]==1){
            return true;
        } else return false;
    }

    @Override
    public void connect(int i, int j) throws IllegalArgumentException {
                matrix[i][j]=1;
    }

    @Override
    public void writeList() {
        for (int a=0;a<getSize();a++){
            for (int b=0;b<getSize();b++){
                if (matrix[a][b]==1){
                    System.out.print(a+1+" "+(b+1)+"\n");
                }
            }
            System.out.print("\n");
        }
    }

    @Override
    public void bfs(int start) throws IllegalArgumentException {
        List<Integer> q = new ArrayList<>();
        boolean[] odwiedzony = new boolean[getSize()];
        for (int i = 0; i < getSize(); i++) {
            odwiedzony[i] = false;
        }
        odwiedzony[start] = true;
        q.add(start);
        System.out.print((start+1)+", ");
        while (q.isEmpty() == false) {
            int v = q.remove(0);
            for (int j = 0; j < getSize(); j++) {
                if (check(v, j)==true) {
                    if (odwiedzony[j] == false) {
                        odwiedzony[j] = true;
                        System.out.print((j+1) + ", ");
                        q.add(j);
                    }
                }
            }
        }
        System.out.println();
    }

    public void odleglosc(int start) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] odwiedzony = new boolean[getSize()];
        int[] odleglosc = new int[getSize()];
        for (int i = 0; i < getSize(); i++) {
            odwiedzony[i] = false;
            odleglosc[i] = 0;
        }
        odwiedzony[start] = true;
        q.add(start);
        while (q.isEmpty() == false) {
            int v = q.remove();
            for (int j = 0; j < getSize(); j++) {
                if (check(v, j)) {
                    if (odwiedzony[j] == false) {
                        odwiedzony[j] = true;
                        odleglosc[j] = odleglosc[v] + 1;
                        q.add(j);
                    }
                }
            }
        }
        System.out.println();
        for (int i = 0; i < getSize(); i++) {
            System.out.println("Od: " + start + " do: " + i + " Najkrotsza droga = " + odleglosc[i]);
        }
        System.out.println();
    }

    public void odleglosc(int start, int end) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] odwiedzony = new boolean[getSize()];
        String[] droga = new String[getSize()];
        for (int i = 0; i < getSize(); i++) {
            odwiedzony[i] = false;
            droga[i] = "";
        }
        odwiedzony[start] = true;
        q.add(start);
        while (q.isEmpty() == false) {
            int v = q.remove();
            for (int j = 0; j < getSize(); j++) {
                if (check(v, j)) {
                    if (odwiedzony[j] == false) {
                        odwiedzony[j] = true;
                        droga[j] = droga[v] + j + " ";
                        q.add(j);
                    }
                }
            }
        }
        System.out.print("#Najkrotsza droga z: " + start + " do: " + end + ": " + droga[end]);
        System.out.println();
    }
}