// Last edited on 2000-09-03 05:15:51 by stolfi
// O grafo de trânsito derivado da planta.

import Nodo;
import CriterioDeParada;

public abstract class Grafo
  {

    // Tabelas de nodos associados a trechos e servicos:
    public Nodo[] trIni;  // Nodo no início de cada trecho
    public Nodo[] trMei;  // Nodo no meio de cada trecho
    public Nodo[] trFim;  // Nodo no fim de cada trecho
    public Nodo[] svEnt;  // Nodo no fim da rampa de entrada de cada serviço
    public Nodo[] svSai;  // Nodo no início da rampa de saída de cada serviço

    public static final double CUSTO_INFINITO = Double.MAX_VALUE;
    public static final double CUSTO_EPSILON = 0.000001;
    
    public final int numNodos()
      { return 
          trIni.length + trMei.length + trFim.length + 
          svEnt.length + svSai.length;
      }
    
    public abstract Nodo[] dijkstra(Nodo[] ini, CriterioDeParada cr);
      // Calcula caminhos ótimos a partir de um conjunto de nós-origem
      // ini[] até cada nó do grafo, em ordem de distância crescente,
      // até atingir o critério especificado por "cr", ou esgotar
      // os nós atingíveis do grafo.
      // 
      // Devolve um vetor com todos os nodos "desejados" encontrados
      // na enumeração, ordenados por distância crescente a partir de "ini". Os
      // caminhos resultantes são definidos implicitamente pelos
      // apontadores "prev" dos nodos "fim[i]".

  }