MODULE JMGraphs EXPORTS Main;

(* Enumerates the "Xoral" graphs of Joćo Meidānis *)

IMPORT Wr, Thread, Fmt;
FROM Stdio IMPORT stdout, stdin, stderr;

CONST NV = 4;

VAR nGraphs: NAT := 0;

TYPE 
  AdjacencyMatrix = ARRAY [0..NV-1] OF ARRAY [0..NV-1] OF BOOLEAN;
  NAT = CARDINAL;

PROCEDURE Main( ) =
  <* FATAL Wr.Failure, Thread.Alerted *>
  VAR x: AdjacencyMatrix;
  BEGIN
    FOR i := 0 TO NV-1 DO 
      x[i,i] := FALSE;  (* Just in case *)
    END;
    Enum(x, skip := 1, u := 0);
    Wr.PutText(stdout, Fmt.Int(nGraphs) & " connected labeled graphs found\n");
    Wr.Close(stdout);
  END Main;

PROCEDURE Enum(
    VAR x: AdjacencyMatrix;
    skip: NAT;  (* How many vertices each edge should skip *)
    u: NAT;     (* First edge to vary is (u,u+skip) *)
  ) =
  (* 
    Enumerates all connected Xoral graphs whose adjacencies
    match the given matrix x[i,j] for (|i-j| < skip) or 
    (|i-j| = skip and i < u).
  *)
  VAR f: BOOLEAN;
  BEGIN
    IF u+skip > NV-1 THEN
      INC(skip); u := 0
    END;
    IF (skip > NV-1) THEN
      IF Connected(x) THEN
        Output(x)
      END
    ELSE
      WITH 
        w = u + skip
      DO      
        f := TRUE;
        FOR v := u+1 TO w-1 DO 
          f := f AND (x[u,v] # x[v,w])
        END;
        x[u,w] := f; x[w,u] := f;
        Enum(x, skip := skip, u := u+1);
        IF f THEN
          x[u,w] := FALSE; x[w,u] := FALSE;
          Enum(x, skip := skip, u := u+1)
        END
      END
    END;
  END Enum;
  
PROCEDURE Connected(READONLY x: AdjacencyMatrix): BOOLEAN =
  VAR b: ARRAY [0..NV-1] OF BOOLEAN;
      q: ARRAY [0..NV-1] OF NAT;
      qlo, qhi: NAT := 0;
      i: INTEGER;
  BEGIN
    b[0] := TRUE;
    q[0] := 0;
    qlo := 0; qhi := 1;
    WHILE qlo < qhi AND qhi < NV DO
      i := q[qlo]; INC(qlo);
      FOR j := 1 TO NV-1 DO 
        IF x[i,j] AND NOT b[j] THEN
          q[qhi] := j; INC(qhi);
          b[j] := TRUE
        END
      END
    END;
    RETURN qhi >= NV
  END Connected;
  
PROCEDURE Output(READONLY x: AdjacencyMatrix) =
  <* FATAL Wr.Failure, Thread.Alerted *>
  BEGIN
    WITH wr = stdout DO
      Wr.PutText(wr, "--- " & Fmt.Int(nGraphs) & " ---\n");
      FOR u := 0 TO NV-2 DO 
        FOR v := u+1 TO NV-1 DO 
          IF x[u,v] THEN 
            Wr.PutText(wr, Fmt.Pad(Fmt.Int(u),3) & " " & Fmt.Pad(Fmt.Int(v),3) & "\n");
          END
        END 
      END;
      Wr.Flush(wr);
    END;
    INC(nGraphs);    
  END Output;

BEGIN
  Main()
END JMGraphs.