/**
 *  Classe Main.java
 *  Autor: Pedro Luis Furio Raphael
 *  Data 01/02/10
 */

package main;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import classesUteis.Gerador;
import classesUteis.Ordena;
import digrafos.Arco;
import digrafos.Digrafo;
import digrafos.Par;
import digrafos.Vertice;

public class Main {

  /**
   * Recebe um array de strings chamado args como argumento. Neste array esta
   * especificado na primeira posição se o programa irá executar o algoritmo
   * para árvores ou para anéis (args[0] = 1 no caso de árvores e args[0] = 2 no
   * no caso de anéis) além de dizer se os dados serão gerados aleatoriamente ou
   * lidos de um arquivo. Se o programa deve ler um arquivo, então, na segunda
   * posicao deste array deve ter o número 1 e na terceira posição o nome do
   * arquivo a ser lido. Se o programa deve gerar uma instancia aleatória, na
   * segunda posição deve ter 2, na terceira deve ter o numero de vértices
   * árvore a ser gerada e na quarta o tamanho do conjunto de pares
   * fonte-sorvedouro que será gerado, este não podendo exceder o número de
   * vértices menos 1.
   */
  public static void main(String[] args) throws FileNotFoundException {
    int[] multicorte = null;
    List<Par> S = new ArrayList<Par>();
    if (args[0].equals("1")) {
      Digrafo T = new Digrafo();
      if (args[1].equals("1")) {
        if (!leArvore(T, S, args[2]))
          System.out.println("Arquivo incorreto.");
      }
      if (args[1].equals("2")) {
        if (Integer.parseInt(args[3]) >= Integer.parseInt(args[2])) {
          System.out.println("Erro nos parametros.");
          return;
        }
        T = Gerador.constroiArvoreAleatoria(Integer.parseInt(args[2]));
        S = Gerador.geraPares(T, Integer.parseInt(args[3]));
        multicorte = new int[T.vertices.size()];
      }
      Digrafo G = null;
      List<Par> Sg = null;
      // Usado para testes.
      /*
       * Long tempo = 0L; int comprimento =
       * Gerador.calculaSomaDosComprimentos(T, S); for (int i = 0; i < 30; i++)
       * { G = null; Sg = null; multicorte = null; G = clonaArvore(T); Sg =
       * clonaPares(S, G); Sg = Ordena.ordenacaoContagem(G, Sg); long
       * tempoInicial = System.currentTimeMillis(); multicorte =
       * CorteMinimo.MultiCorteMinimoArvore(G, Sg); long tempoFinal =
       * System.currentTimeMillis(); tempo += (tempoFinal - tempoInicial); }
       * System.out.println(comprimento + " " + tempo);
       */

      G = clonaArvore(T);
      Sg = clonaPares(S, G);
      Sg = Ordena.ordenacaoContagem(G, Sg);
      multicorte = CorteMinimo.MultiCorteMinimoArvore(G, Sg);
      if (!Verificador.verificaIgualdade(G, multicorte, Sg))
        System.out.println("Corte DIFERENTE da soma " + "dos Fluxos.");
      if (!Verificador.verificaMultiCorte(G, multicorte, Sg))
        System.out.println("Não é um multicorte.");
      for (int i = 0; i < multicorte.length; i++) {
        if (multicorte[i] == 1) {
          System.out.println("O arco de "
              + T.vertices.get(i).paiFilho.inicio.id + " para "
              + T.vertices.get(i).id + " está no multicorte.");
        }
      }

      T = null;
      S = null;
      multicorte = null;
      System.gc();
    }
    if (args[0].equals("2")) {
      Digrafo R = new Digrafo();
      if (args[1].equals("1")) {
        if (!leAnel(R, S, args[2]))
          System.out.println("Arquivo incorreto.");
      }
      if (args[1].equals("2")) {
        if (Integer.parseInt(args[3]) > Integer.parseInt(args[2])) {
          System.out.println("Erro nos parametros.");
          return;
        }
        R = Gerador.constroiAnelAleatorio(Integer.parseInt(args[2]));
        S = Gerador.geraParesAnel(R, Integer.parseInt(args[3]));
      }
      multicorte = CorteMinimo.MultiCorteMinimoAnel(R, S);
      for (int i = 0; i < multicorte.length; i++) {
        if (multicorte[i] == 1) {
          System.out.println("O arco de "
              + R.vertices.get(i).paiFilho.inicio.id + " para "
              + R.vertices.get(i).id + " está no multicorte.");
        }
      }
    }
  }

  /**
   * Este método recebe uma árvore T, um conjunto S de pares fonte-sorvedouro e
   * um arquivo e devolve verdadeiro se o arquivo contém uma entrada válida ou
   * falso caso contrário. Um arquivo válido tem o seguinte formato: um número
   * n, o número de vértices da árvore, seguido por n-1 triplas de números
   * (v,w,p), sendo v<w, w exatamente i-1, onde i é o número da tripla digitada
   * e p um inteiro positivo qualquer. A seguir um número K, que denota o
   * tamanho do conjunto de pares fonte-sorvedouro, seguido por K pares de
   * numeros (s,t), sendo que s < t e que existe um caminho de s a t na árvore.
   */
  private static boolean leArvore(Digrafo T, List<Par> S, String arquivo)
      throws FileNotFoundException {
    int n, s, t, p, K, v, w;
    Scanner scanner = new Scanner(new File(arquivo));
    n = scanner.nextInt();
    T.init(n);
    int[] c = new int[n];
    for (int i = 0; i < n - 1; i++) {
      v = scanner.nextInt();
      w = scanner.nextInt();
      p = scanner.nextInt();

      if (w != i + 1)
        return false;
      if (v >= w) {
        return false;
      } else {
        T.associaArco(new Arco(T.vertices.get(v), T.vertices.get(w), p));
        c[w] = 1;
      }
    }
    K = scanner.nextInt();
    for (int i = 0; i < K; i++) {
      s = scanner.nextInt();
      t = scanner.nextInt();
      List<Arco> cam;
      cam = T.achaCaminho(T.vertices.get(s), T.vertices.get(t));
      if (cam == null) {
        System.out.println("Par inválido, não " + "existe caminho de " + s
            + " para " + t + ".");
        return false;
      } else {
        // cam = T.achaCaminho(T.raiz, T.vertices.get(s));
        cam = T.achaCaminho(T.vertices.get(0), T.vertices.get(s));
        Par st = new Par(T.vertices.get(s), T.vertices.get(t), cam.size());
        S.add(st);
      }
    }
    return true;
  }

  /**
   * Este método recebe um digrafo R, um conjunto S de pares fonte-sorvedouro e
   * um arquivo e devolve verdadeiro se o arquivo contém uma entrada válida ou
   * falso caso contrário. Um arquivo válido tem o seguinte formato: um número
   * n, o número de vértices da árvore, seguido por n-1 triplas de números
   * (v,w,p), sendo v = i, w = i+1, onde i é o número da tripla digitada e p um
   * inteiro positivo qualquer. A última tripla deve ser a seguinte: (n-1, 0,
   * p). A seguir um número K, que denota o tamanho do conjunto de pares
   * fonte-sorvedouro, seguido por K pares de numeros (s,t), s diferente de t.
   */
  private static boolean leAnel(Digrafo R, List<Par> S, String arquivo)
      throws FileNotFoundException {
    int n, s, t, p, K, v, w;
    Scanner scanner = new Scanner(new File(arquivo));
    n = scanner.nextInt();
    R.init(n);
    for (int i = 0; i < n - 1; i++) {
      v = scanner.nextInt();
      w = scanner.nextInt();
      p = scanner.nextInt();

      if (w != i + 1)
        return false;
      if (v >= w) {
        return false;
      } else {
        R.associaArco(new Arco(R.vertices.get(v), R.vertices.get(w), p));
      }
    }
    v = scanner.nextInt();
    w = scanner.nextInt();
    p = scanner.nextInt();

    if (w != 0) {
      return false;
    } else {
      R.associaArco(new Arco(R.vertices.get(v), R.vertices.get(w), p));
    }
    K = scanner.nextInt();
    for (int i = 0; i < K; i++) {
      s = scanner.nextInt();
      t = scanner.nextInt();
      List<Arco> cam;
      cam = R.achaCaminho(R.vertices.get(s), R.vertices.get(t));
      if (cam == null) {
        System.out.println("Par inválido, não " + "existe caminho de " + s
            + " para " + t + ".");
        return false;
      } else {
        Par st = new Par(R.vertices.get(s), R.vertices.get(t), 0);
        S.add(st);
      }
    }
    return true;
  }

  public static Digrafo clonaArvore(Digrafo T) {
    Digrafo G = new Digrafo();
    G.init(T.vertices.size());
    for (Vertice v : T.vertices) {
      if (v.id == 0)
        continue;
      G.vertices.get(v.id).id = v.id;
      G.associaArco(new Arco(G.vertices.get(v.pai.id), G.vertices.get(v.id),
          T.vertices.get(v.id).paiFilho.peso));
    }
    return G;
  }

  public static List<Par> clonaPares(List<Par> S, Digrafo G) {
    List<Par> Sg = new ArrayList<Par>(S.size());
    for (Par p : S) {
      Par p2 = new Par(G.vertices.get(p.s.id), G.vertices.get(p.t.id), G
          .achaCaminho(G.vertices.get(0), G.vertices.get(p.s.id)).size());
      Sg.add(p2);
    }
    return Sg;
  }

}