/*
 * 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 edu.ufp.inf.aed2.aulas;

import edu.princeton.cs.algs4.Stack;
import static edu.princeton.cs.algs4.StdOut.print;

/**
 *
 * @author dudar
 */
public class Aed2_Aula7_Graph {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        /*
        Graph g = new Graph(8);
        g.addEdge(0, 1);
        g.addEdge(0, 3);
        g.addEdge(0, 7);
        g.addEdge(1, 2);
        g.addEdge(1, 6);
        g.addEdge(2, 3);
        g.addEdge(2, 5);
        g.addEdge(3, 4);
        g.addEdge(4, 5);
        g.addEdge(4, 7);
        g.addEdge(5, 6);
        g.addEdge(6, 7);
        System.out.println(g);

        Bipartite_AED2 bipartite = new Bipartite_AED2(g);
        System.out.println("Bipartido: "+ bipartite.isBipartite());
        System.out.println("0 e 3 sao adjacentes?: "+ g.areAdjacent(0, 3));
        // resolver a matriz de adjacencias para o exercicio de cima

         */

 /*
        // exercicio de dfs iterativo
        Graph g = new Graph(6);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(0, 3);
        g.addEdge(1, 4);
        g.addEdge(3, 5);
        g.addEdge(1, 2);
        client_dfs_iterativo(g, 0);
         */
        Graph g = new Graph(10);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(0, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 5);
        g.addEdge(3, 5);
        g.addEdge(3, 6);
        g.addEdge(4, 9);
        g.addEdge(5, 7);
        g.addEdge(5, 8);
        g.addEdge(6, 8);

        kNeighbours(g, 0 , 2);
        g.isComplete();

    }

    public static void client_dfs_iterativo(Graph g, int s) {
        boolean[] marked = new boolean[g.V()];
        // for(int i=0; i<g.V();i++){
        //print(marked[i]);
        //}
        Stack<Integer> stack = new Stack<>();
        stack.push(s);

        while (!stack.isEmpty()) {
            s = stack.pop();

            if (!marked[s]) {
                print(s);
                System.out.print(" ");
                marked[s] = true;
                for (Integer v : g.adj(s)) {
                    if (!marked[v]) {
                        stack.push(v);
                    }
                }
            }
        }
    }

    public static void kNeighbours(Graph g, int s, int k) {

        BreadthFirstPaths bfs = new BreadthFirstPaths(g, s);
        for (int i = 0; i < g.V(); i++) {
            if (i != s && bfs.distTo(i) <= k) {
                System.out.println(i);

            }
        }
    }
}