Algorithmen und Datenstrukturen 2 WS 1999/2000

7. Übung - abzugeben am 7. 12. 1999 in Ihrer Übungsgruppe

7 Programm Warshall

MODULE Graph;

  TYPE 
    EdgeValT* =LONGINT; (* Typ fuer Kantenbewertung *)
    NodeNrT*=INTEGER;   (* Typ fuer Knotennummer *)
    GraphT* =RECORD     (* kurze Bezeichner nur wegen Tafel und Folien *)
      n-: NodeNrT;      (* Knotenzahl *)
      a:  MatrixT;      (* Adjazenzmatrix *)
      w:  MatrixT;      (* Wegematrix *)
      m:  POINTER TO ARRAY OF ARRAY OF NodeNrT; (* Orientierungsmatrix *)
    END; (*record*)

  CONST 
    NOEDGE=MAX(EdgeValT); (* Kantenbewertung fuer: keine Kante = quasi Unendlich *)
    NONODE=MIN(NodeNrT);  (* Auspraegung fuer: kein Knoten *)

  PROCEDURE (VAR g:GraphT) Init*(v:NodeNrT); (* v= Anzahl Knoten im Graph *)
  PROCEDURE (VAR g:GraphT) CleanUp*(); (* Freigabe Graph und Freigabe dyn. allokierter Platz *)
  PROCEDURE (VAR g:GraphT) SetEdge*(x,y:NodeNrT; value:EdgeValT); (* Kante von x nach y mit Kantenbewertung value aufnehmen *)
  PROCEDURE (VAR g:GraphT) Warshall*(); (*Warshall: Wegematrix und Orientierungsmatrix errechnen *)
  PROCEDURE (VAR g:GraphT) PrintWay*(x,y: NodeNrT); (* Ausgabe kuerzester Weg von von x nach y inkl. Zwischenknoten und Weglaenge *)  
  PROCEDURE (VAR g:GraphT) PrintOrientation*(); (* Ausgabe Orientierungsmatrix m *)
  PROCEDURE (VAR g:GraphT) PrintAdj*(); (* Ausgabe Adjazenzmatrix a *)
  PROCEDURE (VAR g:GraphT) PrintWays*(); (* Ausgabe Wegematrix w *) 

END Graph.

Anmerkungen:

• Zu verwalten sind gewichtete, gerichtete Graphen.
• Für PrintWays, PrintOrientation und PrintWay gilt: Testtreiber (und damit der Tester) ist für die richtige Reihenfolge der Ausführung verantwortlich!
• Besprechung der geforderten Funktionen erfolgt in der Übung.
• Sicherheitsabfragen nicht vergessen!
• Kommentare für das gesamte Modul Graph erforderlich!
• Ein einfachster Testtreiber ist verfügbar.
• Ein Ausschnitt aus dem Modul Graph steht Ihnen ebenfalls als Arbeitsgrundlage zur Verfügung. Adaptieren/korrigieren Sie soweit notwendig bzw. entsprechend Ihren Vorstellungen.
• Testen Sie das Programm mit eigenen Testdaten!