[ALGO 2 Homepage] Algorithmen und Datenstrukturen 2 WS 1999/2000

3. Übung - abzugeben am 9. 11. 1999 in Ihrer Übungsgruppe

3 Programm

Schreiben/ergänzen Sie ein Programm gemäß folgender Interface-Definition und testen Sie es:
DEFINITION OF MODULE Graph;

  TYPE Graph*=RECORD
    vertexn-: INTEGER;                             (* Anzahl Knoten im Graphen *)
    edgen-:   INTEGER;                             (* Anzahl Kanten im Graphen *) 
  END; (*record*)

  PROCEDURE (VAR g:Graph)Init*(v:INTEGER);         (* v=Anzahl der Knoten im Graphen *)
  PROCEDURE (VAR g:Graph)CleanUp*();               (* Freigabe des Graphen = Freigabe des dynamisch allokierten Speicherplatzes *)
  PROCEDURE (VAR g:Graph)SetEdge*(x,y:INTEGER);    (* Kante x,y in den ungerichteten Graphen aufnehmen *)
  PROCEDURE (VAR g:Graph)PrGraph*();               (* Ausgabe der Adjazenzmatrix für den Test *)
  PROCEDURE (VAR g:Graph)Warshall*(VAR res:Graph); (* Anwenden des Algorithmus von Warshall auf den Graphen g; Ergebnis in res *)
END Graph;

Anmerkungen:


Ein einfachster Testtreiber (ohne jegliche eigenständige Überprüfungen) könnte z.B. wie folgt aussehen:

MODULE GraphTst;

  IMPORT Graph, In, Out;

  PROCEDURE ProgMain*;
  VAR g1, g2: Graph.GraphT;
      x,y: INTEGER;     
      code: CHAR;
  BEGIN (*ProgMain*)
    REPEAT
      In.Echo(FALSE);
      In.Prompt("?/1/2/3/4/5/E: "); In.Char(code); code:=CAP(code);
      In.Echo(TRUE);
      IF ~In.Done THEN code:="E" END; (*if*)
      CASE code OF
        "0", "H", "?":
          Out.String("(?) HILFE der Befehlscodes: ?=Hilfe / 1=Init / 2=Kante / 3=Adjazenzmatrix / 4=Warshall / 5=Loeschen / E=Ende")  
        | "1", "I":
          Out.String("(1) INIT Graph: "); In.Prompt("Anzahl Knoten="); In.Int(x);
          g1.Init(x)
        | "2", "K": 
          Out.String("(2) KANTE einfuegen: ");
          In.Prompt("Knoten 1= "); In.Int(x); Out.String("   ");
          In.Prompt("Knoten 2= "); In.Int(y);
          g1.SetEdge(x,y)
        | "3", "A", "M": 
          Out.F2("(3) ADJAZENZMATRIX ausgeben: (Anzahl Knoten=#  Anzahl Kanten=#)$",
                 g1.vertexn, g1.edgen);
          g1.PrGraph
        | "4", "W": 
          Out.String("(4) WARSHALL auf Graph ausfuehren: "); Out.Ln; 
          g1.Warshall(g2);
          g2.PrGraph;
          g2.CleanUp
        | "5", "L": 
          Out.String("(5) Loeschen Graph"); 
          g1.CleanUp    
        | "6", "E":
          Out.String("(6) ENDE des Tests"); 
        ELSE
          Out.String("(x) FEHLER!!! Befehlscodes: ?=Hilfe / 1=Init / 2=Kante / 3=Adjazenzmatrix / 4=Warshall / 5=Loeschen / E=Ende")
      END; (*case*)
      Out.Ln
    UNTIL ~In.Done OR (code="E") OR (code="6")
  END ProgMain;

END GraphTst.
Der Testtreiber ist für das Pow! System ausgelegt und bedarf in anderen Umgebungen eventuell einer leichten Modifikation.


Damit Sie das Modul Graph nicht vollständig neu schreiben müssen, hier kurz ein Codefragment (als unverbindlicher Vorschlag) dazu:

MODULE Graph;

  IMPORT Out;

  TYPE GraphT*=RECORD
         vertexn-: INTEGER;
         edgen-:   INTEGER;
         a:        POINTER TO ARRAY OF ARRAY OF BOOLEAN
       END; (*record*)

  PROCEDURE (VAR g:GraphT)Init*(v:INTEGER);
  VAR i,j:INTEGER;
  BEGIN (*Init*)
    ASSERT(v>0);
    ASSERT(g.a=NIL);
    NEW(g.a,v,v); ASSERT(g.a#NIL);
    g.edgen:=0;
    g.vertexn:=v;
    FOR i:=0 TO v-1 DO
      FOR j:=0 TO v-1 DO
        g.a[i,j]:=FALSE
      END (*for*)
    END (*for*)
  END Init;

  PROCEDURE (VAR g:GraphT)CleanUp*();
  BEGIN (*CleanUp*)
    ASSERT(g.a#NIL);
    DISPOSE(g.a); g.a:=NIL;
    g.edgen:=0;
    g.vertexn:=0;
  END CleanUp;

  PROCEDURE (VAR g:GraphT)SetEdge*(x,y:INTEGER);
  BEGIN (*SetEdge*)
    ...
  END SetEdge;

  PROCEDURE (VAR g:GraphT)PrGraph*();
  VAR z,s:INTEGER;
  BEGIN (*PrGraph*)
    ASSERT(g.a#NIL);
    Out.String("     ");
    FOR s:=0 TO g.vertexn-1 DO Out.Int(s,3) END; (*for*)
    FOR z:=0 TO g.vertexn-1 DO
      Out.Ln; Out.Int(z,3); Out.String(": ");
      FOR s:=0 TO g.vertexn-1 DO
        Out.String("  ");
        IF(g.a[z,s]) THEN Out.Char("*") ELSE Out.Char(".") END (*if*)            
      END (*for*)
    END; (*for*)
    Out.Ln
  END PrGraph;

  PROCEDURE (VAR g:GraphT)Warshall*(VAR res:GraphT);
  ...
  BEGIN (*Warshall*)
    ...
  END Warshall;

END Graph.
Bitte dokumentieren Sie das Programm (quasi als Nachweis, daß Sie es gelesen/verstanden haben)! Überlegen Sie auch, ob alle Assertions notwendig/günstig sind.
(Denken Sie auch daran, daß wir Assertions in diesen Beispielen zur Kennzeichnung von Sonderfällen verwenden, die wir hier softwaretechnisch nicht behandeln, da wir uns auf die Algorithmen konzentrieren wollen.)


Last modified: Hörmanseder 1999-10-18