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

package main;

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

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

public class CorteMinimo {

  /**
   * Este método recebe uma árvore T e um cojunto S de pares fonte-sorvedouro e
   * devolve um multicorte de S que tem peso mí­nimo.
   */
  public static int[] MultiCorteMinimoArvore(Digrafo T, List<Par> S) {
    int[] multicorte = new int[T.vertices.size()];
    Arco a = null;
    S = Ordena.ordenacaoContagem(T, S);
    for (int k = S.size() - 1; k >= 0; k--) {
      Vertice t = S.get(k).t;
      Vertice s = S.get(k).s;
      Vertice u = t;
      a = u.paiFilho;
      int f = a.peso - a.somaFluxo;
      for (; u != s; u = u.pai) {
        a = u.paiFilho;
        if (a.peso - a.somaFluxo < f) {
          f = a.peso - a.somaFluxo;
        }
      }
      u = t;
      for (; u != s; u = u.pai) {
        a = u.paiFilho;
        a.addFluxo(f);
        if (a.somaFluxo == a.peso) {
          multicorte[a.fim.id] = 1;
        }
      }
      S.get(k).setFluxo(f);
    }
    for (int k = 0; k < S.size(); k++) {
      if (S.get(k).fluxo == 0)
        continue;
      Vertice t = S.get(k).t;
      Vertice s = S.get(k).s;
      Vertice u = t;
      Arco arc = null;
      for (; u != s; u = u.pai) {
        a = u.paiFilho;
        if (multicorte[a.fim.id] == 1) {
          arc = a;
        }
      }
      u = t;
      for (; u != s; u = u.pai) {
        a = u.paiFilho;
        if (a == arc)
          break;
        multicorte[a.fim.id] = 0;
      }
    }
    return multicorte;
  }

  /**
   * Este método recebe um anel R e um cojunto S de pares fonte-sorvedouro e
   * devolve um multicorte de S que tem peso mí­nimo.
   */
  public static int[] MultiCorteMinimoAnel(Digrafo R, List<Par> S) {
    int[] M = null;
    Digrafo T = null;
    int somaPesos = 0, pesoMulticorte = 0;
    Par p = S.get(0);
    List<Arco> c = R.achaCaminho(p.s, p.t);
    for (Arco a : c) {
      T = constroiArvore(R, a);
      List<Par> Slinha = constroiSLinha(R, S, T, a);
      int[] MLinha = MultiCorteMinimoArvore(T, Slinha);
      MLinha[a.fim.id] = 1;
      for (int i = 0; i < MLinha.length; i++) {
        if (MLinha[i] == 1) {
          somaPesos += T.vertices.get(i).paiFilho.peso;
        }
      }
      if (somaPesos < pesoMulticorte || M == null) {
        M = MLinha;
      }
    }
    return M;
  }

  private static List<Par> constroiSLinha(Digrafo R, List<Par> S, Digrafo T,
      Arco a) {
    List<Par> Slinha = new ArrayList<Par>();
    for (Par p : S) {
      int b = ((p.s.id - a.fim.id) % R.vertices.size());
      if (b < 0)
        b += R.vertices.size();
      int d = ((p.t.id - a.fim.id) % R.vertices.size());
      if (d < 0)
        d += R.vertices.size();
      Vertice s = T.vertices.get(b);
      Vertice t = T.vertices.get(d);
      List<Arco> c = T.achaCaminho(s, t);
      if (c == null)
        continue;
      Par p2 = new Par(s, t, (T.achaCaminho(T.vertices.get(0), s)).size());
      Slinha.add(p2);
    }

    return Slinha;
  }

  private static Digrafo constroiArvore(Digrafo R, Arco a) {
    Digrafo T = new Digrafo();
    T.init(R.vertices.size());
    a = a.inicio.paiFilho;
    for (int i = R.vertices.size() - 1; i >= 1; i--) {
      Arco arc = new Arco(T.vertices.get(i - 1), T.vertices.get(i), a.peso);
      T.vertices.get(i).id = i;
      T.associaArco(arc);
      a = a.inicio.paiFilho;
    }
    return T;
  }
}