mentor/src/dgraph/Warshall.m3


 Copyright (C) 1994, Digital Equipment Corporation           
 All rights reserved.                                        
 See the file COPYRIGHT for a full description.              

MODULE Warshall;

IMPORT Algorithm, DGraphAlgClass, DGraphIE, Thread, RefList,
       ZeusPanel, ZeusCodeView, ReadGraph, AdjMatrix;

CONST C = AdjMatrix.Column; R = AdjMatrix.Row;

TYPE
  T = DGraphAlgClass.T BRANDED OBJECT
    OVERRIDES
      run := Run;
    END;

PROCEDURE Run (alg: T) RAISES {Thread.Alerted} =
  VAR
    m: AdjMatrix.T;
    nVertices: INTEGER;
    xF, yF, jF := TRUE;

  PROCEDURE At (line: INTEGER) RAISES {Thread.Alerted} =
    BEGIN
      ZeusCodeView.Event(alg, line);
    END At;
  PROCEDURE AsNameX(var: TEXT; val: INTEGER) RAISES {}=
    BEGIN
      IF xF THEN xF := FALSE ELSE alg.varView.setText(var, m.name(val)); END;
    END AsNameX;
  PROCEDURE AsNameY(var: TEXT; val: INTEGER) RAISES {}=
    BEGIN
      IF yF THEN yF := FALSE ELSE alg.varView.setText(var, m.name(val)); END;
    END AsNameY;
  PROCEDURE AsNameJ(var: TEXT; val: INTEGER) RAISES {}=
    BEGIN
      IF jF THEN jF := FALSE ELSE alg.varView.setText(var, m.name(val)); END;
    END AsNameJ;

  BEGIN
    m := ReadGraph.In(alg);
    IF m = NIL THEN
      RETURN;
    END;

    nVertices := m.nVertices();

    ZeusCodeView.Event(alg, procedureName := "Warshall");
    DGraphIE.Setup(alg, m);

At(1);FOR y <*TRACE AsNameY*> := 0 TO nVertices-1 DO
                                         DGraphIE.MarkVertex(alg, y, 0, C);
At(2);FOR x <*TRACE AsNameX*> := 0 TO nVertices-1 DO

                                         DGraphIE.MarkEdge(alg, x, y, 1);
At(3);  IF m.getEdge(x, y) THEN          DGraphIE.MarkVertex(alg, x, 1, R);
                                         DGraphIE.MarkVertex(alg, y, 2, R);
At(4);    FOR j <*TRACE AsNameJ*> := 0 TO nVertices-1 DO
                                         DGraphIE.MarkEdge(alg, y, j, 2);
At(5);      IF m.getEdge(y, j) THEN
At(6);        m.putEdge(x, j, TRUE);     DGraphIE.AddEdge(alg, x, j);
            END; (* if *)                DGraphIE.UnMarkEdge(alg, y, j, 2);
          END; (* for j *)               DGraphIE.UnMarkVertex(alg, y, 2, R);
        END; (* if *)                    DGraphIE.UnMarkEdge(alg, x, y, 1);
                                         DGraphIE.UnMarkVertex(alg, x, 1, R);
      END; (* for x *)
    END; (* for y *)
  END Run;

PROCEDURE New(): Algorithm.T RAISES {}=
  VAR fv := ZeusPanel.NewForm("DGraphinput.fv");
  BEGIN
    WITH cv = RefList.List1 (
                  RefList.List2 ("Modula-3 Code View", "Warshall.m3.cv")) DO
      RETURN NEW(T, data := fv, codeViews := cv,
                 varRsrc := "WarshallVar.fv").init()
    END; (* with *)
  END New;

BEGIN
  ZeusPanel.RegisterAlg(New, "Warshall", "DGraph");
END Warshall.