MODULE Graph3;

  IMPORT Out;

  CONST SETSIZE= MAX(SET)+1;
    
  TYPE GraphT*=RECORD
         vertexn-: INTEGER;
         edgen-:   INTEGER;
         a:        POINTER TO ARRAY OF SET;
       END; (*record*)
     

  PROCEDURE (VAR g:GraphT)Init*(v:INTEGER);
  VAR i,j:INTEGER;
  BEGIN (*Init*)
    ASSERT(v>1);
    ASSERT(g.a=NIL); (* ?? *)
    NEW(g.a,(v*(v-1) DIV 2 + SETSIZE -1) DIV SETSIZE);
    ASSERT(g.a#NIL);
    FOR i:=0 TO LEN(g.a^)-1 DO g.a[i]:={} END; (*for*)
    g.edgen:=0;
    g.vertexn:=v;
  END Init;


  PROCEDURE Dreieck(x,y:INTEGER):INTEGER;
    VAR h: INTEGER;
  BEGIN (*Dreieck*)
    IF x<y
      THEN h:=y*(y-1) DIV 2 +x 
      ELSE h:=x*(x-1) DIV 2 +y
    END; (*if*)
    RETURN h
  END Dreieck;


  PROCEDURE (VAR g:GraphT)GetEdge*(x,y:INTEGER):BOOLEAN;
    VAR h:INTEGER;
  BEGIN (*GetEdge*)
    ASSERT((g.a#NIL) & (x>=0) & (x<g.vertexn) & (y>=0) & (y<g.vertexn));
    IF x=y THEN RETURN FALSE END; (*if*)
    h:=Dreieck(x,y);
    RETURN (h MOD SETSIZE) IN g.a[h DIV SETSIZE]
  END GetEdge;


  PROCEDURE (VAR g:GraphT)SetEdge*(x,y:INTEGER);
    VAR h,pos,off:INTEGER;
  BEGIN (*GetEdge*)
    ASSERT((x#y) & (g.a#NIL) & (x>=0) & (x<g.vertexn) & (y>=0) & (y<g.vertexn));
    h:=Dreieck(x,y);
    pos:=h DIV SETSIZE;
    off:=h MOD SETSIZE;
    IF ~(off IN g.a[pos]) THEN
      INC(g.edgen); 
      INCL(g.a[pos], off)
    END (*if*)  
  END SetEdge;

   
  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)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.GetEdge(z,s) THEN Out.Char("*") ELSE Out.Char(".") END (*if*)            
      END (*for*)
    END; (*for*)
    Out.Ln
  END PrGraph;


 
  PROCEDURE(VAR g:GraphT)NrComps*():INTEGER;
    ...
  BEGIN (*NrComps*)
    ...
  END NrComps;

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

  PROCEDURE(VAR g:GraphT)IsTree*():BOOLEAN;
    ...
  BEGIN
    ...
  END IsTree;


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

BEGIN (*Graph3*)
  ASSERT (MIN(SET)=0)
END Graph3.