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;