{ File: grafvis.pas }

{ Scopo: procedure di visita in profondita` ed in ampiezza di un grafo }

{ Le procedure di visita richiedono le definizioni di pile e code i cui
  elementi sono i nodi del grafo. }

type
  TipoElemPila = TipoNodo;

{$I PILE.PAS}  { Inclusione della realizzazione del tipo di dato pila }

type
  TipoElemCoda = TipoNodo;

{$I CODE.PAS}  { Inclusione della realizzazione del tipo di dato coda }

{ Le procedure di visita richiedono la definizione della procedura che analizza
  un nodo.  L'analisi di un nodo puo` essere ad esempio la sua stampa:
}

  procedure Analizza (i: TipoNodo);
  begin
    write(' ',i,' ')
  end;

{
  algoritmo visita un grafo a partire dal nodo n
  1.  togli la marca a tutti i nodi del grafo
  2.  insieme dei nodi da visitare := insieme vuoto
  3.  metti n nell'insieme dei nodi da visitare
  4.  finche` l'insieme dei nodi da visitare non e' vuoto
      ripeti
  5.      estrai un nodo i dall'insieme dei nodi da visitare
  6.      se i non e' marcato
          allora
  7.          analizza i (stampa il valore intero i)
  8.          marca i
  9.          per ogni successore j di i che non e' marcato
              ripeti
 10.              metti j nell'insieme dei nodi da visitare
}


    procedure VisitaInProfondita (var grafo: TipoGrafo; nodo_iniz: TipoNodo);
    { Effettua una visita del grafo in profondita` a partire da nodo_iniz.
      Utilizza una pila. }
    var
      i,j              : TipoNodo;
      nodi_da_visitare : TipoPila;
      nodi_visti       : array [TipoNodo] of boolean;
    
    begin
      { inizializzazione }
{ 1 } for i := 1 to NumNodi do
        nodi_visti[i] := FALSE;
{ 2 } InitPila(nodi_da_visitare);
{ 3 } Push(nodi_da_visitare, nodo_iniz);
    
      { cicla finche' ci sono nodi da visitare }
{ 4 } while not TestPilaVuota(nodi_da_visitare) do
      begin
        { prende il prossimo nodo i da visitare }
{ 5 }   Pop(nodi_da_visitare, i);
        
        { analizza il nodo i e lo pone tra i nodi visti }
{ 6 }   if not nodi_visti[i] then
        begin
{ 7 }     Analizza(i);
{ 8 }     nodi_visti[i] := TRUE;
          
          { aggiunge i successori non visitati del nodo i ai nodi da visitare }
{ 9 }     for j := NumNodi downto 1 do
            if TestEsisteArco(grafo, i, j) and (not nodi_visti[j]) then
{10 }         Push(nodi_da_visitare, j)
         end
      end { while }
    end; { VisitaInProfondita }
    

    procedure VisitaInAmpiezza (var grafo: TipoGrafo; nodo_iniz: TipoNodo);
    { Effettua una visita del grafo in ampiezza a partire da nodo_iniz.
      Utilizza una pila. }
    var
      i,j              : TipoNodo;
      nodi_da_visitare : TipoCoda;
      nodi_visti       : array [TipoNodo] of boolean;
    
    begin
      { inizializzazione }
{ 1 } for i := 1 to NumNodi do
        nodi_visti[i] := FALSE;
    
{ 2 } InitCoda(nodi_da_visitare);
{ 3 } InCoda(nodi_da_visitare, nodo_iniz);
    
      { cicla finche' ci sono nodi da visitare }
{ 4 } while not TestCodaVuota(nodi_da_visitare) do
      begin
        { prendi il prossimo nodo i da visitare }
{ 5 }   OutCoda(nodi_da_visitare, i);
    
        { analizza il nodo i e lo pone tra i nodi visti }
{ 6 }   if not nodi_visti[i] then
        begin
{ 7 }     Analizza(i);
{ 8 }     nodi_visti[i] := TRUE;
          
          { aggiunge i successori non visitati del nodo i ai nodi da visitare }
{ 9 }     for j := 1 to NumNodi do
            if TestEsisteArco(grafo, i, j) and (not nodi_visti[j]) then
{10 }         InCoda(nodi_da_visitare, j)
        end
      end
    end; { VisitaInAmpiezza }
    

procedure VisitaRicInProfondita (var grafo: TipoGrafo; nodo_iniz: TipoNodo);
{ Effettua una visita del grafo in profondita` a partire da nodo_iniz.
  Utilizza una procedura ricorsiva. }
var
  i          : TipoNodo;
  nodi_visti : array [TipoNodo] of boolean;

  procedure VisitaRicorsiva (var grafo: TipoGrafo; i: TipoNodo);
  { Procedura ricorsiva che effettua la visita in profondita`. }
  var
    j : TipoNodo;
{ var globale
    nodi_visti : array [TipoNodo] of boolean }

  begin
    if not nodi_visti[i] then
    begin
      { analizza il nodo i e lo pone tra i nodi visti }
      Analizza(i);
      nodi_visti[i] := TRUE;

      { visita i successori non visitati del nodo i }
      for j := 1 to NumNodi do
        if TestEsisteArco(grafo, i, j) and (not nodi_visti[j]) then
          VisitaRicorsiva(grafo, j)
    end
  end; { VisitaRicorsiva }

begin { VisitaRicInProfondita }
  { inizializzazione }
  for i := 1 to NumNodi do
    nodi_visti[i] := FALSE;
    
  { inizia la visita ricorsiva }
  VisitaRicorsiva(grafo, nodo_iniz);
end; { VisitaRicInProfondita }