{ File: progesol.pas }

{ Scopo: esercizio sull'uso di grafi }

program Progetto;
{ Esercizio di esame di Fondamenti di Informatica del 12/2/1998.
  Soluzione completa. }

const
  NumAttivita = 5;

type
  TipoAttivita = 1..NumAttivita;
  TipoProgetto = array [TipoAttivita, TipoAttivita] of real;
     { matrice di adiacenza che rappresenta il grafo associato ad un progetto }

  TipoArco        = record
                      sorgente, destinazione : TipoAttivita;
                      costo                  : real
                    end;
     { elemento della lista di archi }

  TipoListaArchi  = ^TipoRecordLista;
  TipoRecordLista = record
                      arco : TipoArco;
                      next : TipoListaArchi
                    end;   


{ Funzione che risolve il punto 2.
  Vengono fornite due versioni:
  - una non ottimizzata che usa cicli for, ed
  - una ottimizzata che usa cicli indefiniti ed esce dai cicli appena
    possibile. }

  function NonEsisteAttivitaIsolataNonOttim (progetto: TipoProgetto): boolean;
  { Restituisce TRUE se in progetto non esiste un'attivita` isolata
    e FALSE altrimenti.
    Versione non ottimizzata che usa cicli for. }
  var
    i, j    : TipoAttivita;   { indici usati nei cicli }
    isolata : boolean;

  begin { NonEsisteAttivitaIsolataNonOttim }
    NonEsisteAttivitaIsolataNonOttim := TRUE; { assumi che nessuna attivita`
                                                sia isolata }
    for i := 1 to NumAttivita do
    begin                        { considera l'attivita` i-esima }
      isolata := TRUE;           {    assumi che sia isolata }
      for  j := 1 to NumAttivita do
        if (progetto[j,i] <> 0) or    { se vi e` un arco da j entrante in i o }
           (progetto[i,j] <> 0) then  {    vi e` un arco uscente da i verso j }
          isolata := FALSE;           { allora l'attivita` i non e` isolata   }
        { N.B. NON CI DEVE ESSERE il ramo else }
      if isolata then            {    ho verificato che i e` isolata ... }
        NonEsisteAttivitaIsolataNonOttim := FALSE  { e me ne ricordo }
      { N.B. NON CI DEVE ESSERE il ramo else }
    end
  end; { NonEsisteAttivitaIsolataNonOttim }


  function NonEsisteAttivitaIsolata (progetto: TipoProgetto): boolean;
  { Restituisce TRUE se in progetto non esiste un'attivita` isolata
    e FALSE altrimenti.
    Versione ottimizzata che esce dai cicli appena possibile. }
  var
    i, j             : integer;   { indici usati nei cicli }
    nessuna, isolata : boolean;

  begin { NonEsisteAttivitaIsolata }
    nessuna := TRUE;               { assumi che nessuna attivita` sia isolata }
    i := 1;
    while (i <= NumAttivita) and nessuna do
    begin                         { considera l'attivita` i }
      isolata := TRUE;            {   assumi che i sia isolata }
      j := 1;
      while  (j <= NumAttivita) and isolata do
      begin
        if (progetto[j,i] <> 0) or    { se vi e` un arco da j entrante in i o }
           (progetto[i,j] <> 0) then  {    vi e` un arco uscente da i verso j }
          isolata := FALSE;           { allora l'attivita` i non e` isolata   }
        j := j+1
      end;
      nessuna := not isolata;
      i := i+1
    end;
    NonEsisteAttivitaIsolata := nessuna
  end; { NonEsisteAttivitaIsolata }


{ Procedura che risolve il punto 3. }

  procedure ListaArchiCostoAlto (progetto: TipoProgetto; r: real;
                                 var lista: TipoListaArchi);
  { Restituisce in lista la lista degli archi di costo maggiore di r. }
  var
    i, j : TipoAttivita;   { indici usati nei cicli }
    paux : TipoListaArchi;

  begin  { ListaArchiCostoAlto }
    lista := NIL;
    for i := 1 to NumAttivita do
      for j := 1 to NumAttivita do
        if progetto[i,j] > r then
        begin
          new(paux);
          with paux^.arco do
          begin
            sorgente := i;
            destinazione := j;
            costo := progetto[i,j]
          end;
          paux ^.next := lista;
          lista := paux
        end
  end; { ListaArchiCostoAlto }


{ procedure ausialiarie usate dal programma driver }

  procedure LeggiProgetto (nomefile : string; var progetto: TipoProgetto);
  { Legge dal file di testo nomefile le informazioni riguardo alle attivita di
    un progetto, rappresentato tramite matrice di adiacenza.
    Assume che il file contenga una matrice di reali di 5x5 elementi
    nonnegativi. }
  var
    f    : text;
    i, j : TipoAttivita;

  begin { LeggiProgetto }
    assign(f, nomefile);
    reset(f);
    for i := 1 to NumAttivita do
      for j := 1 to NumAttivita do
        read(f, progetto[i, j]);
    close(f)
  end; { LeggiProgetto }


  procedure StampaProgetto (progetto: TipoProgetto);
  { Stampa su video le informazioni riguardo al progetto. }
  var
    i, j : TipoAttivita;

  begin { StampaProgetto }
    for i := 1 to NumAttivita do
    begin
      for j := 1 to NumAttivita do
        write(progetto[i, j]:6:1);
      writeln
    end
  end; { StampaProgetto }


  procedure StampaListaArchi (lista: TipoListaArchi);
  { Stampa su video le informazioni riguardo agli archi in lista. }
  begin { StampaListaArchi }
    writeln('sorgente':10, 'destinazione':14, 'costo':10);
    while lista <> NIL do
    begin
      with lista^.arco do
        writeln(sorgente:10, destinazione:14, costo:10:1);
      lista := lista^.next
    end
  end; { StampaListaArchi }


{ variabili usate nel programma principale }
var
  prog     : TipoProgetto; { progetto sul quale vengono fatte le elaborazioni }
  archi    : TipoListaArchi;  { lista di archi }
  nomefile : string;  { nome del file contenente le informazioni sul progetto }
  r        : real;    { valore reale di soglia usato nel punto 3 }
  isolate  : boolean; { tiene conto dell'esistenza di attivita` isolate }

begin { Progetto }

  { Lettura delle informazioni sul progetto da file. }
  writeln('Immetti il nome del file dal quale leggere le informazioni sul progetto!');
  writeln('(N.B. Il file deve gia` esitere)');
  readln(nomefile);
  LeggiProgetto(nomefile, prog);                   { lettura da file }

  writeln;
  writeln('Matrice di adiacenza che rappresenta il progetto:');
  StampaProgetto(prog);                            { stampa di conferma }

  { Verifica dell'esistenza di attivita` isolate }

  { Attivazione della funzione che risolve il punto 2,
    - prendendo in ingresso la matrice prog che rappresenta le attivita` di un
      progetto
    - e restituendo come valore di ritorno il valore booleano calcolato. }

  isolate := NonEsisteAttivitaIsolata(prog);

  { stampa del risultato dell'attivazione della funzione 2 }
  writeln;
  if isolate then
    writeln('Il progetto ha attivita` isolate.')
  else
    writeln('Il progetto non ha attivita` isolate.');

  { Lettura del valore reale di soglia. }
  writeln;
  write('Valore di soglia (reale positivo)? ');
  readln(r);

  { Attivazione della procedura che risolve il punto 3,
    - prendendo in ingresso
        - la matrice prog che rappresenta le attivita` di un progetto e
        - il valore di soglia r
    - e restituento in archi la lista degli archi che hanno costo maggiore del
      valore di soglia r. }

  ListaArchiCostoAlto(prog, r, archi);

  { stampa del risultato dell'attivazione della procedura 3 }
  writeln;
  writeln('Archi con costo maggiore di ', r:4:1, ':');
  StampaListaArchi(archi)

end. { Progetto }