------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 1995 by International Computer Science Institute            --
-- This file is part of the GNU Sather library. It is free software; you may --
-- redistribute  and/or modify it under the terms of the GNU Library General --
-- Public  License (LGPL)  as published  by the  Free  Software  Foundation; --
-- either version 2 of the license, or (at your option) any later version.   --
-- This  library  is distributed  in the  hope that it will  be  useful, but --
-- WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE. See Doc/LGPL for more details.       --
-- The license text is also available from:  Free Software Foundation, Inc., --
-- 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA                     --
-------------->  Please email comments to <bug-sather@gnu.org>  <--------------

-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>

abstract class $GRAPH{NTP<$HASH,ETP< $EDGE{NTP}} < $ELT{NTP}, $STR is
   -- A generic graph, consisting of a bunch of nodes and edges.
   -- There is no committment as to the meaning of the edges
   -- Every node has some edges which associate it with a set of 
   -- neighbors
   -- This generic graph does not have the modification operations
   -- Design note:
   --   The reason for not having the modification operations is that
   --   it is hard to work on a general graph without knowing whether it
   --   has directed or undirected edges
   -- Acknowledgement:
   --   Discussions with the Karla folk, particularly Wolf, helped
   --   elucidate some of the confusion between directed and undirected 
   --   graphs
   
   is_empty: BOOL;
   -- Return true if there are no nodes in the graph
   
   copy: $GRAPH{NTP,ETP};
   -- Return a copy of the graph
   
   n_nodes: INT;
   -- Return the number of nodes in the graph
   
   n_edges: INT;
   -- Return the number of edges in the graph
   
   has_node(n: NTP): BOOL;
   -- Return  true if this graph has the node "n"
   
   has_edge(e: ETP): BOOL;
   -- Return true if this graph has the edge "e"
   
   n_adjacent(n: NTP): INT;
   -- Return the number of nodes that are adjacent to "n".
   -- See the note at "adjacent!"
   
   node!: NTP;
   -- Yield all the nodes in the graph
   
   edge!: ETP;
   -- Yield all the edges in the graph
   
   adjacent!(once n: NTP): NTP;
   -- This corresponds more closely to the notion of neighbors in an
   -- undirected graph. In the case of a directed graph, the neighbors
   -- will be the set of outgoing nodes.
   -- In other words, by going through all nodes and their adjacent
   -- nodes we can construct all the edges in the graph without
   -- duplication.
   
end; -- class $GRAPH{NTP,ETP}
-------------------------------------------------------------------

