------------------------------------------------------------------------------
--                                                                          --
--                               GRAPH ADT                                  --
--                                                                          --
--                          AUTHOR: Robert Walsh                            --
--                          DATE:   November 14, 1995                       --
--                          CLASS:  CSCI 375                                --
--                                                                          --
------------------------------------------------------------------------------
with U_ADT;
use U_ADT;
with Q_Queue;
with Priority_Q;
with LList;

generic
  type EdgeData is private;
  type NodeData is private;
  with function LessThan(x, y : EdgeData) return BOOLEAN;
  with function Equal(x, y : EdgeData) return BOOLEAN;
  with procedure PEdge(x : EdgeData);
  with procedure Extract(Data : in EdgeData; From, To, Weight : out INTEGER);
  with procedure Insert(Data : out EdgeData; To, Weight : in INTEGER);
  with procedure Print(Data :in NodeData);
  
package Graph is

package NewQ is new Q_Queue(INTEGER);
package NewPq is new Priority_Q(EdgeData, LessThan);
package NewList is new LList(EdgeData, LessThan, Equal, PEdge);

use NewList;
use NewPq;
use NewQ;

  type GraphNode is record
	Data : NodeData;
	Next : LIST;
	end record;
  type Graph is array (1..50) of GraphNode;
  type AdjPtr is access Graph;
  type GraphADT is record
	Size : INTEGER;
 	Matrix : AdjPtr;
	end record; 
  type Edge;
  type EdgePtr is access Edge;
  type Edge is record
	Data : EdgeData;
 	Next : EdgePtr;
	end record;

  procedure Create(G : in out GraphADT);
	--WHAT:	Creates a graph which is implemented by an adjacency matrix. 
	--This is done by linking an array of 50 records to the head node [G]. 
	--Therefore, the graph may have a maximum of 50 nodes.
	--IN: G [GraphADT] : Not actually a graph but a head node to one which
	--will be created.
	--OUT: G [GraphADT] : A head node with a new graph linked to it.

  procedure AddNode(G : in out GraphADT; Data : in NodeData; 
		    Success : out BOOLEAN);
	--WHAT: Adds a node to a graph.
	--IN:	G [GraphADT] : A graph that requires a new node.
	--	Data [CHARACTER] : The data that will be stored in that node.
	--OUT:	G [GraphADT] : The graph with the node added.
	--	Success [BOOLEAN] : The success of the operation.

  procedure AddEdge(G : in out GraphADT; From, To : in INTEGER;
 		    Data : in EdgeData; Success : out BOOLEAN);
	--WHAT:	Adds an edge to a graph.
	--IN:	G [GraphADT] : a graph which needs a edge added to it.
	--	From [INTEGER] : The exiting endpoint [node] of the edge.
	--	To [INTEGER] : The entering endpoint [node] of the edge.
	--	Data [EdgeData] : The record which holds the data for this edge.
	--OUT:	G [Graph] : The graph with the edge added.
	--	Success [BOOLEAN] : The success of the operation.

  procedure RemEdge(G : in out GraphADT; From, To : in INTEGER;
		    Data : in EdgeData; Success : out BOOLEAN);
	--WHAT: Removes an edge from a graph.
	--IN:	G [GraphADT] :
	--  	From [INTEGER] :
	--	To [INTEGER] :
	--	Data [EdgeData] :
	--OUT:	G [GraphADT] :
	--	Success [BOOLEAN] :

  procedure BFS(G : in GraphADT);
	--WHAT: Performs a breadth first search on a graph.  The BFS performs a
	--print function as it traverses the graph.  Therefore, the data stored
	--in each node is printed to the screen in a BFS order.  
	--IN:	G [GraphADT] : a graph that the BFS operation is to be 
	--performed on.
	--OUT:  None

  procedure MST(G : in GraphADT; G_out : in out GraphADT);  
	--WHAT: Creates a minimum spanning tree of graph G.    
	--IN:	G [GraphADT] : The original graph.   
	--	G_out [GraphADT] : an empty graph (will be made into a MST).
	--OUT:  G_out [GrpahADT] : a MST of graph G.

end Graph;

package body Graph is

  procedure Create(G : in out GraphADT) is
  AdjMtx : Adjptr;
  begin
    G.Size := 0;
    AdjMtx := new Graph;
    G.Matrix := AdjMtx;
  end Create;

  procedure AddNode(G : in out GraphADT; Data : in NodeData;
		    Success : out BOOLEAN) is
  begin
    if (G.Size<50) then 
      G.Size := G.Size+1;
      INITIALIZE(G.Matrix(G.Size).Next);
      G.Matrix(G.Size).Data := Data;
      Success := TRUE;
    else
      Success := False;
    end if;
  end AddNode;

  procedure AddEdge(G : in out GraphADT; From, To : in INTEGER;
		    Data : in EdgeData; Success : out BOOLEAN) is
  begin
    Success := FALSE;
    if (From>0) and (To>0) then
      if (From<=G.Size) and (To<=G.Size) then 
        INSERT(G.Matrix(From).Next, Data, Success);
      end if;
    end if;
  end AddEdge;

  procedure RemEdge(G : in out GraphADT; From, To : in INTEGER;
		    Data : in EdgeData; Success : out BOOLEAN) is
  begin
    Success := FALSE;
    if (From>0) and (To>0) then
      if (From<=G.Size) and (To<=G.Size) then
        DELETE(G.Matrix(From).Next, Data, Success);
      end if;
    end if;  
  end RemEdge;

  procedure BFS(G:in GraphADT)is
  k:integer;
  current : INTEGER;
  NodesLeft:qqueue;
  inqueue:array(1..G.Size)of boolean;
   
    function Edge(G : in GraphADT; ANode, LNode : in INTEGER)
		  return BOOLEAN is
    Temp : LIST := G.Matrix(ANode).Next;
    Stat : BOOLEAN := FALSE;
    Rec : EdgeData;
    From, To, Dumb : INTEGER;
    begin
      while not empty(Temp) loop
        GetRec(Temp, Rec);
	Extract(Rec, From, To, Dumb);
        if (LNode=To) then Stat:=TRUE; end if;
  	INC(Temp);
      end loop;	
    return Stat;
    end Edge;

  begin
     for k in 1..G.Size loop
       inqueue(k):=false;
     end loop;

     clear(NodesLeft);
     enqueue(NodesLeft,1);
     inqueue(1):=TRUE;
     while not Empty(NodesLeft) loop
       Dequeue(NodesLeft, current);
       Print(G.Matrix(Current).Data);
     for k in 1..G.Size loop
       if not inqueue(k) and Edge(G,current,k) then
         Enqueue(NodesLeft, k);
         inqueue(k):=TRUE;
       end if;
     end loop;
   end loop;
   Destroy(NodesLeft);
   end BFS;

procedure MST(G:in GraphADT; G_out: in out GraphADT) is 
   
 Temp : LIST;
 From, To, Weight : Integer;
 Data: EdgeData;
 maxV: Integer := G.Size;
 maxE: Integer:= maxV ** 2;
 subtype new_pq is pq(maxE);
 subtype new_set is set(maxV);
 S: new_set;
 PQ: new_pq;
 ok: Boolean;
 type Ea is array(0..maxE) of EdgeData;
 E : Ea;

 begin
  create(PQ);  --initialize the priority queue.
  for i in 1..G.Size loop
   Temp := G.Matrix(i).Next;
   while not empty(Temp) loop
    GetRec(Temp, Data);
    on_q(PQ, Data, ok); --Put an edge on the priority queue.
    INC(Temp);
   end loop;
  end loop;

   G_out.size := G.Size;
   for T in 1..G.Size loop
     G_out.Matrix(T).Data := G.Matrix(T).Data;
     INITIALIZE(G_out.Matrix(T).Next); 
   end loop;
   UFcreate(S);  --Initialize union set.

   for k in 1..maxV-1 loop
    off_q(PQ, Data, ok); --Take a record off the priority queue.
    if ok then
     Extract(Data, From, To, Weight);
     UFfind(S, From, To, ok);  --If the edge is not in the 
     if not(ok) then                  --union,  
      UFunion(S, From, To, ok);    --add it to the set.
      AddEdge(G_out, From, To, Data, ok);
     end if;
    end if;
   end loop;    
  end mst;

begin
  null;
end Graph;