generic

  type Vertices is (<>);

package Digraphs_Generic is
------------------------------------------------------------------------
--| Specification for unweighted digraphs with discrete vertex sets
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: January 1996                                     
------------------------------------------------------------------------

  type Digraph is limited private;

  -- constructors

  procedure InitializeGraph (G: in out Digraph);
  -- Pre:  none
  -- Post: G has no edges

  procedure AddEdge (G: in out Digraph; Source, Destination: in Vertices);
  procedure DeleteEdge (G: in out Digraph; Source, Destination: in Vertices);
  -- Pre:  G, Source, and Destination are defined
  -- Post: returns G with the edge <Source, Destination> added or 
  --       deleted respectively; AddEdge has no effect if the edge is 
  --       already in G; DeleteEdge has no effect if the edge is not in G

  function IsEmpty (G: Digraph) return Boolean;
  -- Pre:  G is defined
  -- Post: returns True if and only if G has no edges

  function NumberOfEdges (G: Digraph) return Natural;
  -- Pre:  G is defined
  -- Post: returns the number of edges in G

  function IsAdjacent (G: Digraph; Source, Destination: Vertices) 
    return Boolean;
  -- Pre:  G, Source, and Destination are defined
  -- Post: returns True if and only if G has an edge <Source, Destination>

  procedure DisplayGraph(G: Digraph);
  -- Pre:  G is defined
  -- Post: performs G in matrix form using T or F 
  --       for presence or absence of edge

  generic
    with procedure Visit(V: Vertices);
  procedure Traverse_BFS (G: in Digraph; Start: Vertices);
  -- Pre:  G and V are defined
  -- Post: performs breadth-first traversal of G starting at vertex V

  generic
    with procedure Visit(V: Vertices);
  procedure Traverse_DFS (G: in Digraph; Start: Vertices);
  -- Pre:  G and V are defined
  -- Post: performs depth-first traversal of G starting at vertex V

private

  type AdjacencyMatrix is array (Vertices, Vertices) of Boolean;
  type Digraph is record
    Store: AdjacencyMatrix := (others => (others => False));
  end record;
  
end Digraphs_Generic;