BEGIN "SPNTRE"
   REQUIRE 10000 NEW!ITEMS;
   ITEM DAD; COMMENT SET MEMBERSHIP RELATION NAME: (DAD,ELT,SET);
   INTEGER NVERTEXSETS; COMMENT NUMBER OF DISJOINT SETS OF NODES;

   LIST EDGES; COMMENT THE PRIORITY QUEUE OF EDGES OF THE GRAPH;
   LIST INTLIST;
   LIST VERTEXLIST;  COMMENT THE SET OF THE NODES OF GRAPH;
   SET VERTEXSETS;  COMMENT SET OF DISJOINT SETS OF NODES;
   SET TREESET;  COMMENT SET OF EDGES MAKING UP MINIMAL SPANNING TREE;
   LIST ITEMVAR EDGETEMP; COMMENT WILL REFER TO AN EDGE ITEM;
   LIST ITEMVAR V,W,VERTEX; COMMENT WILL REFER TO VERTEX ITEMS;
   INTEGER ITEMVAR EDGECOST; COMMENT WILL REFER TO COST OF AN EDGE;
   INTEGER COSTS;  COMMENT COST SO FAR OF SPANNING TREE;
   STRING FILENAME; INTEGER FLAG, INCHAN,FIRSTEND,NODECOUNT,I,
       COUNT,BRCHAR;

BOOLEAN PROCEDURE DISJOINTUNION(ITEMVAR E1,E2);
BEGIN
 WHILE (DAD XOR E1 EQV BIND E1) DO CONTINUE;
 WHILE (DAD XOR E2 EQV BIND E2) DO CONTINUE;
 IF E1=E2 THEN RETURN(FALSE);
 MAKE DAD XOR E1 EQV E2;
 RETURN(TRUE);
END;
COMMENT START EXECUTION HERE;
    COUNT← 80;
COMMENT READIN THE GRAPH FROM AN INPUT FILE;
    OUTSTR('15&'12&"TYPE IN THE INPUT FILE NAME - ");
    FILENAME ← INCHWL;
    OPEN(INCHAN←GETCHAN,"DSK",0,2,0,COUNT,BRCHAR,FLAG);
    LOOKUP(INCHAN,FILENAME,FLAG);
    
COMMENT FIND OUT HOW MANY NODES IN THE GRAPH;

    NODECOUNT ← INTIN(INCHAN);
    
    FOR I ← 1 STEP 1 UNTIL NODECOUNT DO
           VERTEXLIST[I] ← NEW(I);

    FOR I ← 1 STEP 1 UNTIL 100 DO
           INTLIST[I] ← NEW(I);
COMMENT NOW READ IN THE EDGES OF THE GRAPH;
    EDGES ← NIL;
    FIRSTEND ← INTIN(INCHAN);
    WHILE FIRSTEND NEQ 0 DO
      BEGIN "FIRSTEND"
         EDGETEMP← NEW({{VERTEXLIST[FIRSTEND],
                         VERTEXLIST[INTIN(INCHAN)],
                         INTLIST[INTIN(INCHAN)] ⎇⎇ );
         EDGECOST ← DATUM(EDGETEMP)[3];
       COMMENT INSERT EDGE INTO APPROPRIATE PLACE IN PRIORITY QUEUE;

         FOR I ← 1 STEP 1 UNTIL LENGTH(EDGES) DO
           BEGIN
              INTEGER ITEMVAR EDGECOST2;
              LIST ITEMVAR EDGETEMP2;
              EDGETEMP2 ← EDGES[I];
              EDGECOST2 ← DATUM(EDGETEMP2)[3];
              IF DATUM(EDGECOST2) < DATUM (EDGECOST) THEN
                  CONTINUE;
              PUT EDGETEMP IN EDGES BEFORE I;
              FIRSTEND ← INTIN(INCHAN);
              CONTINUE "FIRSTEND";
           END;
         PUT EDGETEMP IN EDGES AFTER LENGTH(EDGES);
         FIRSTEND←INTIN(INCHAN);
     END "FIRSTEND";

   COSTS ← 0;
   TREESET ← PHI;
   VERTEXSETS ← PHI;

COMMENT INITIALIZE SET OF DISJOINT SETS AND THE MAPPING
   BETWEEN A NODE AND THE DISJOINT SET IN WHICH IT APPEARS ;

   FOREACH VERTEX SUCH THAT VERTEX IN VERTEXLIST DO
	 MAKE DAD XOR VERTEX EQV NEW;
   NVERTEXSETS←LENGTH(VERTEXLIST);

COMMENT NOW CONSTRUCT THE SPANNING TREE;

   WHILE NVERTEXSETS > 1 DO
      BEGIN
         EDGETEMP ← LOP(EDGES);
         V ← DATUM(EDGETEMP)[1];
         W ← DATUM(EDGETEMP)[2];
         EDGECOST ← DATUM(EDGETEMP)[3];
	IF DISJOINTUNION(V,W) THEN
            BEGIN
               COSTS ← COSTS + DATUM(EDGECOST);
               PUT EDGETEMP IN TREESET;
               NVERTEXSETS←NVERTEXSETS-1;
            END;
      END;


COMMENT PRINT OUT THE RESULT;

   OUTSTR('15&'12 &"TOTAL COST OF SPANNING TREE =" &
	CVS(COSTS));
END "SPNTRE"