package body Graph is

   ----------------------------------------------------------------------------
   function Index_Of (Graph : in Graph_Type;
                      Key   : in Key_Type) return Positive is
   -- Purpose        : Returns the index of the vertex in Graph.Vertices 
   --                  with the given Key
   -- Preconditions  : None
   -- Postconditions : if there is an element in Graph with the given Key 
   --                     The index of it in Graph.Vertices is returned
   --                  else
   --                     Graph.Num_Vertices + 1 is returned
      Index : Positive;
   begin
      Index := 1;
      loop
         exit when Index > Graph.Num_Vertices or else 
                   Key = Key_Of (Graph.Vertices(Index).Info);
         Index := Index + 1;
      end loop;
      return Index;
   end Index_Of;

   ----------------------------------------------------------------------------
   procedure Clear (Graph : in out Graph_Type) is
   begin
      Graph.Num_Vertices := 0;
   end Clear;

   ----------------------------------------------------------------------------
   procedure Add_Vertex (Graph  : in out Graph_Type;
                         Vertex : in     Vertex_Type) is
      Index : Positive;  -- Location for new Vertex
   begin
      Index := Index_Of (Graph, Key_Of (Vertex));  -- Find if its key is already
      if Index <= Graph.Num_Vertices then          -- in the Graph
         raise VERTEX_ERROR;
      elsif Index > Graph.Max_Vertices then        -- Any more room?
         raise OVERFLOW;
      else
         Graph.Vertices(Index).Info    := Vertex;  -- Add the new vertex to the
         Graph.Vertices(Index).Marked  := False;   -- end of the array
         Graph.Num_Vertices := Index;
         -- Initialize the adjacency matrix to indicate no edges
         for Row in 1..Graph.Num_Vertices loop     -- The row
            Graph.Edges(Row, Index).Defined := False;
         end loop;
         for Col in 1..Graph.Num_Vertices loop     -- The column
            Graph.Edges(Index, Col).Defined := False;
         end loop;
      end if;
   end Add_Vertex;

   ----------------------------------------------------------------------------
   procedure Add_Edge (Graph  : in out Graph_Type;
                       Edge   : in     Edge_Type;
                       Weight : in     Weight_Type) is
      From_Index : Positive;
      To_Index   : Positive;
   begin
      From_Index := Index_Of (Graph, Edge.From);   -- Location of From vertex
      To_Index   := Index_Of (Graph, Edge.To);     -- Location of To vertex
      -- Do both vertices exist?
      if From_Index > Graph.Num_Vertices  or  To_Index > Graph.Num_Vertices  then
         raise VERTEX_ERROR;  
      else
         -- Update the adjacency matrix with the new edge
         Graph.Edges(From_Index, To_Index).Weight  := Weight;
         Graph.Edges(From_Index, To_Index).Defined := True;
      end if;
   end Add_Edge;

   ----------------------------------------------------------------------------
   procedure Retrieve (Graph  : in  Graph_Type;
                       Key    : in  Key_Type;
                       Vertex : out Vertex_Type) is
      Index : Positive;
   begin
      Index := Index_Of (Graph, Key);           -- Find the vertex's location
      if Index > Graph.Num_Vertices then
         raise VERTEX_ERROR;                    -- Vertex does not exist
      else
         Vertex := Graph.Vertices(Index).Info;  -- Return information
      end if;
   end Retrieve;

   ----------------------------------------------------------------------------
   function Weight_Of (Graph  : in Graph_Type;
                       Edge   : in Edge_Type) return Weight_Type is
      From_Index : Positive;
      To_Index   : Positive;
   begin
      From_Index := Index_Of (Graph, Edge.From);  -- Find the location of
      To_Index   := Index_Of (Graph, Edge.To);    -- the two vertices in Edge
      -- Check to make sure that both vertices exist in Graph
      if From_Index > Graph.Num_Vertices  or  
         To_Index   > Graph.Num_Vertices  then
         raise VERTEX_ERROR;
      elsif Graph.Edges(From_Index, To_Index).Defined then
         return Graph.Edges(From_Index, To_Index).Weight;
      else
         raise EDGE_ERROR;
      end if;
   end Weight_Of;

   ----------------------------------------------------------------------------
   procedure Get_Adjacent_Vertices (Graph    : in  Graph_Type;
                                    Key      : in  Key_Type;
                                    Adj_Keys : out Key_Queue.Queue_Type) is
      From_Index : Positive;
   begin
      From_Index := Index_Of (Graph, Key);  -- Locate the vertex with the given Key
      if From_Index > Graph.Num_Vertices then
         raise VERTEX_ERROR;                -- Vertex does not exist
      else
         Adj_Keys.Clear;  -- Initialize queue of adjacent vertex keys
         -- Go through the From_Index row of the matrix
         for To_Index in 1..Graph.Num_Vertices loop
            -- Is there an edge from From_Index to To_Index?
            if Graph.Edges(From_Index, To_Index).Defined then
               -- Add the key of the To end of the edge to the list
               Adj_Keys.Enqueue(Item => Key_Of (Graph.Vertices(To_Index).Info));
            end if;
         end loop;
      end if;
   end Get_Adjacent_Vertices;

   ----------------------------------------------------------------------------
   procedure Clear_All_Marks (Graph : in out Graph_Type) is
   begin
      for Index in 1..Graph.Num_Vertices loop
         Graph.Vertices(Index).Marked := False;
      end loop;
   end Clear_All_Marks;

   ----------------------------------------------------------------------------
   procedure Mark_Vertex (Graph : in out Graph_Type;
                          Key   : in     Key_Type) is
      Index : Positive;
   begin
      Index := Index_Of (Graph, Key);  -- Find location of vertex with Key
      if Index > Graph.Num_Vertices then
         raise VERTEX_ERROR;
      else
         Graph.Vertices(Index).Marked := True;
      end if;
   end Mark_Vertex;

   ----------------------------------------------------------------------------
   function Marked (Graph : in Graph_Type;
                    Key   : in Key_Type)    return Boolean is
      Index : Positive;
   begin
      Index := Index_Of (Graph, Key);  -- Find location of vertex with Key
      if Index > Graph.Num_Vertices then
         raise VERTEX_ERROR;
      else
         return Graph.Vertices(Index).Marked;
      end if;
   end Marked;

end Graph;