with Queue;
generic
   type Vertex_Type is private;
   type Key_Type    is private;
   type Weight_Type is private;
   with function Key_Of (Vertex : in Vertex_Type) return Key_Type;
   with function "=" (Left : in Key_Type; Right : in Key_Type) return Boolean;
package Graph is

-- A graph consists of a set of vertices and a set of weighted 
-- edges that connect some or all of the vertices one to another.

   type Graph_Type (Max_Vertices : Positive) is tagged limited private;

   -- Additional types for graph operation parameters

   -- An edge is described by a pair of vertex keys
   type Edge_Type is 
      record
         From : Key_Type;
         To   : Key_Type;
      end Record;

   -- A queue class whose elements are Keys
   package Key_Queue is new Queue (Element_Type => Key_Type);

   -- Exceptions
   VERTEX_ERROR  : exception;
   EDGE_ERROR    : exception;
   OVERFLOW      : exception;

   ----------------------------------------------------------------------------
   procedure Clear (Graph : in out Graph_Type);
   -- Purpose        : Makes a graph empty.
   -- Preconditions  : None
   -- Postconditions : V(Graph) = empty
   --                  E(Graph) = empty

   ----------------------------------------------------------------------------
   procedure Add_Vertex (Graph  : in out Graph_Type;
                         Vertex : in     Vertex_Type);
   -- Purpose         : Add Vertex to the Graph
   -- Preconditions   : None
   -- Postconditions  : V(Graph) = V(Graph) + Vertex  
   -- Exceptions      : VERTEX_ERROR is raised if a vertex already exists
   --                      Graph with the same key of Vertex
   --                   OVERFLOW is raised if Graph has no more room 
   --                      for an additional vertex

   ----------------------------------------------------------------------------
   procedure Add_Edge (Graph  : in out Graph_Type;
                       Edge   : in     Edge_Type;
                       Weight : in     Weight_Type);
   -- Purpose        : Add Edge with specified Weight to Graph
   -- Preconditions  : None
   -- Postconditions : E(Graph) = E(Graph) + Edge
   -- Exceptions     : VERTEX_ERROR is raised if one or both of the vertices 
   --                     defining Edge do not exist in the Graph

   ----------------------------------------------------------------------------
   procedure Retrieve (Graph  : in  Graph_Type;
                       Key    : in  Key_Type;
                       Vertex : out Vertex_Type);
   -- Purpose        : Gets a copy of the Vertex with the given Key
   -- Preconditions  : None
   -- Postconditions : Vertex is a copy of the Graph vertex with the given Key
   -- Exceptions     : VERTEX_ERROR is raised if there is no vertex with the
   --                    given Key in Graph

   ----------------------------------------------------------------------------
   function Weight_Of (Graph  : in Graph_Type;
                       Edge   : in Edge_Type) return Weight_Type;
   -- Purpose        : Gets the weight associated with Edge
   -- Preconditions  : None
   -- Postconditions : Weight = weight associated with Edge
   -- Exceptions     : VERTEX_ERROR is raised if one or both of the vertices 
   --                     defining Edge do not exist Graph
   --                  EDGE_ERROR is raised if Edge does not exist in the Graph

   ----------------------------------------------------------------------------
   procedure Get_Adjacent_Vertices (Graph    : in  Graph_Type;
                                    Key      : in  Key_Type;
                                    Adj_Keys : out Key_Queue.Queue_Type);
   -- Purpose        : Returns a queue of the keys of all the vertices adjacent 
   --                  to the node with the given Key
   -- Preconditions  : None
   -- Postconditions : Adj_Keys contains the keys of all the vertices that are 
   --                  adjacent to the vertex with the given Key
   -- Exceptions:      VERTEX_ERROR is raised if there is no vertex with the
   --                     given Key in the Graph
   --                  Key_Queue.OVERFLOW if there are more adjacent nodes
   --                     than Adj_Keys.Max_Size

   ----------------------------------------------------------------------------
   procedure Clear_All_Marks (Graph : in out Graph_Type);
   -- Purpose        : Clears the marks from all all vertices in Graph
   -- Preconditions  : None

   -- Postconditions: All vertices in Graph are marked as not visited

   ----------------------------------------------------------------------------
   procedure Mark_Vertex (Graph : in out Graph_Type;
                          Key   : in     Key_Type);
   -- Purpose        : Marks the vertex with the given Key
   -- Preconditions  : None
   -- Postconditions :The vertex with the given Key is marked
   -- Exceptions:     VERTEX_ERROR is raised if there is no vertex with the
   --                    given Key in the Graph

   ----------------------------------------------------------------------------
   function Marked (Graph : in Graph_Type;
                    Key   : in Key_Type)    return Boolean;
   -- Purpose        : Determines whether the vertex with 
   --                  the given key is marked
   -- Preconditions  : None
   -- Postconditions : Marked = (Vertex with Key is marked)
   -- Exceptions     : VERTEX_ERROR is raised if there is no vertex with the
   --                    given Key in the Graph

private

   type Vertex_Rec is
      record
         Info   : Vertex_Type;       -- Information declared by user
         Marked : Boolean := False;  -- Has the Vertex been visited?
      end record;

   type Edge_Rec is
      record
         Weight  : Weight_Type;       -- Weight assigned to the edge
         Defined : Boolean := False;  -- Is this edge in the graph?
      end record;

   type Vertex_Array is array (Positive range <>) of Vertex_Rec;
   type Matrix_Type  is array (Positive range <>, 
                               Positive range <>) of Edge_Rec;

   type Graph_Type (Max_Vertices : Positive) is tagged limited
      record
         Num_Vertices : Natural := 0;
         Vertices     : Vertex_Array (1..Max_Vertices);
         Edges        : Matrix_Type  (1..Max_Vertices, 1..Max_Vertices);
      end record;

end Graph;