package grafica;

/**
 * Título:       Graficas
 * Descripcion:
 * Copyright:    Copyright (c) 2002
 * Empresa:      UMSNH
 * @author Felix Calderon Solorio
 * @version 1.0
 */

public class grafo {
  final int MAX_VERTICES = 20;  // numero maximo de vertices
  final int INFINITO = 10000;   // definicion de infinito
  int MatAdj[][];               // Matriz de Adjacencia
  int NumVert;                  // numero de vertices
  vertice ListaVert[];          // lista de vertices

  public grafo()
  {
    ListaVert = new vertice[MAX_VERTICES];
    MatAdj = new int[MAX_VERTICES][MAX_VERTICES];
    NumVert = 0;
    for(int i=0; i<MAX_VERTICES; i++)
      for(int j=0; j<MAX_VERTICES; j++)
        MatAdj[i][j] = INFINITO;
  }

  void Agrega_Vertice(String l)
  {
    if(NumVert < MAX_VERTICES)
    {
     ListaVert[NumVert] = new vertice(l, NumVert);
     NumVert++;
    }
    else System.out.println("se exedio el numero maximo de vertices");
    return;
  }

  void Agrega_Arista(int inicio, int fin, int peso)
  {
    if (inicio < NumVert && fin < NumVert) MatAdj[inicio][fin] = peso;
  }

  void Imprime_MatAdj()
  {
    int i, j;

    System.out.println("Matriz de Adyacencia");
    for(i=0; i<NumVert; i++)
    {
      for(j=0; j<NumVert; j++)
      {
        System.out.print(MatAdj[i][j] + " " + '\t' + " " + '\t');
      }
      System.out.print('\n');
    }
  }

  void Imprime_Lista()
  {
    int i;

    for(i=0; i<NumVert; i++)
      ListaVert[i].Imprime();
  }

  // algoritmo de busqueda en profundidad

  void dfs()
  {
    pila la_pila = new pila();
    ListaVert[0].conocido = 1;

   la_pila.encola(0);
    while(la_pila.inicio != null)
    {
      //System.out.println("cola = " + la_pila.imprime());
      //Imprime_Lista();

      int v = VerticeNoVisitado(la_pila.inicio.info());
      if(v== -1) la_pila.desencola();
      else
      {
        ListaVert[v].conocido = 1;
        ListaVert[v].Imprime();
        la_pila.encola(v);
      }
    }
  }

  int VerticeNoVisitado(int v)
  {
      for(int j = 0; j < NumVert; j++)
      {
        //System.out.println(v + " " +j);
        if(MatAdj[v][j] != INFINITO && ListaVert[j].conocido == 0)
          return j;
      }
      return -1;
  }

  // algoritmo de Dijktra para busqueda en anchura y calculo de distancias minimas

  void Dijkstras(vertice s)
  {
    cola q = new cola();

    int v, w;

    q.encola(s.numero, 0);
    s.distancia = 0;

    while(q.inicio != null)
    {
      //System.out.println("cola = " + q.imprime());
      //Imprime_Lista();
      v = q.desencola();

      ListaVert[v].conocido = 1;
      for(w = 0; w < NumVert; w++)
      {
        if(MatAdj[v][w] != INFINITO)
        {
          if(ListaVert[w].distancia == INFINITO)
          {
            ListaVert[w].distancia = ListaVert[v].distancia + 1;
            ListaVert[w].ruta = ListaVert[v];
            q.encola(w, 0);
          }
        }
      }
    }
  }

  // algoritmo de Prim para calculo de arboles de expancion minima

  void Prims(vertice s)
  {
    cola q = new cola();

    int v, w, costo;

    q.encola(s.numero, 0);
    s.distancia = 0;

    while(q.inicio != null)
    {
      System.out.println("cola = " + q.imprime());
      Imprime_Lista();
      v = q.desencola();

      ListaVert[v].conocido = 1;
      for(w = 0; w < NumVert; w++)
      {
        if(MatAdj[v][w] != INFINITO && ListaVert[w].conocido == 0 )
        {
          costo = MatAdj[v][w];
          if(ListaVert[w].distancia > costo)
          {
            ListaVert[w].distancia = costo;
            ListaVert[w].ruta = ListaVert[v];
            q.encola_prioridad(w, costo);
          }
        }
      }
    }
  }

}