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

package classesUteis;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import digrafos.Arco;
import digrafos.Digrafo;
import digrafos.Par;
import digrafos.Vertice;

public class Gerador {
  // static long seed = System.currentTimeMillis();
  static long seed = 123L;

  /**
   * Este método gera uma árvore aleatória com n vértices. Os arcos da árvore
   * recebem pesos aleatórios entre 1 e 20.
   */
  public static Digrafo constroiArvoreAleatoria(int n) {
    Random r = new Random(seed);
    Digrafo T = new Digrafo();
    T.init(n);
    for (int i = 1; i < n; i++) {
      int j = r.nextInt(i);
      Arco a = new Arco(T.vertices.get(j), T.vertices.get(i), r.nextInt(20) + 1);
      T.associaArco(a);
      T.vertices.get(j).id = j;
      T.vertices.get(i).id = i;
    }
    return T;
  }

  /**
   * Este método recebe um inteiro K e uma árvore T e devolve um conjunto de
   * pares fonte-sorvedouro relevantes de tamanho K, tal que a fonte e o
   * sorvedouro são vértices de T.
   */
  public static List<Par> geraPares(Digrafo T, int K) {
    Random r = new Random(seed);
    List<Par> S = new ArrayList<Par>();
    List<Arco> c = new ArrayList<Arco>();
    int[] sorv = new int[T.vertices.size()];
    int i = 0;
    int n = T.vertices.size();
    while (i < K) {
      int t = r.nextInt(n - 1) + 1;
      if (sorv[t] == 1)
        continue;
      c = T.achaCaminho(T.vertices.get(0), T.vertices.get(t));
      Vertice s = null;
      s = c.get(r.nextInt(c.size())).inicio;
      sorv[t] = 1;
      c = T.achaCaminho(T.vertices.get(0), s);
      Par p = new Par(s, T.vertices.get(t), c.size());
      S.add(p);
      i++;
    }
    return S;
  }

  /**
   * Este método recebe um conjunto de pares fonte-sorvedouro S de uma árvore T
   * e devolve a soma dos comprimentos dos caminhos da fonte ao sorvedouro para
   * cada par de S.
   */
  public static int calculaSomaDosComprimentos(Digrafo T, List<Par> S) {
    int soma = 0;
    for (Par p : S) {
      List<Arco> caminho = T.achaCaminho(p.s, p.t);
      soma += caminho.size();
    }
    return soma;
  }

  public static Digrafo constroiAnelAleatorio(int n) {
    Random r = new Random(seed);
    Digrafo R = new Digrafo();
    R.init(n);
    for (int i = 0, j = 1; j < n; i++, j++) {
      Arco a = new Arco(R.vertices.get(i), R.vertices.get(j), r.nextInt(20) + 1);
      R.associaArco(a);
      R.vertices.get(j).id = j;
      R.vertices.get(i).id = i;
    }
    Arco a = new Arco(R.vertices.get(n - 1), R.vertices.get(0),
        r.nextInt(20) + 1);
    R.associaArco(a);
    return R;
  }

  public static List<Par> geraParesAnel(Digrafo R, int K) {
    List<Par> S = new ArrayList<Par>(K);
    Random r = new Random(seed);
    int n = R.vertices.size();
    for (int i = 0; i < K; i++) {
      int t = r.nextInt(n);
      int s = r.nextInt(n);
      boolean jaExiste = false;
      for (Par p : S) {
        if (p.s == R.vertices.get(s) && p.t == R.vertices.get(t)) {
          jaExiste = true;
          break;
        }
      }
      if (!jaExiste) {
        Par p = new Par(R.vertices.get(s), R.vertices.get(t), 0);
        S.add(p);
      }
    }
    return S;
  }
}