------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 1995 by International Computer Science Institute            --
-- This file is part of the GNU Sather package. It is free software; you may --
-- redistribute  and/or modify it under the terms of the  GNU General Public --
-- License (GPL)  as  published  by the  Free  Software  Foundation;  either --
-- version 2 of the license, or (at your option) any later version.          --
-- This  program  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/GPL 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>  <--------------

-- abs_graph.sa: Abstract graph classes
-- Author: Benedict A. Gomes <gomes@icsi.berkeley.edu>

class NULL is end;
   -- Used as a parametrization for graphs with no edge type
   -- e.g. $GRAPH{N,NULL,N} indicates a graph that is
   -- indexed by the node type N and has no edge values
-------------------------------------------------------------------   
abstract class $GRAPH{
	 N,			-- Node type
	 E,			-- Edge type
	 I			-- Node Index type
   } is
      -- The most general graph type.  No directions
      -- on edges are assumed.  Multiple edges between nodes
      -- are not permitted.
   
   node_index(n: N): I;
   -- pre has_node(n);
   -- Conversion from nodes to indices
   -- An error if the node is not in the graph
   
   node(i: I): N;
   -- An error  if the node index is not in the graph
   -- And vice versa
   
   nodes: FLIST{N};
   -- Return the set of node indices
   
   node_indices: FLIST{I};
   -- Return a list of node indices
   
   has_node(n: N): BOOL;
   -- Return true if the node exists in the graph
   
   has_index(i: I): BOOL;
   -- Return true if the node exists in the graph
   
   has_edge(n1,n2: I): BOOL;
   
   n_nodes: INT;
   
-- In all these routines the node index must be in the graph
-- i.e. pre test_index(n);
   
   add_node(n: N): I;
   -- Return the node index

   connect(n1,n2: I);
   
   connect(src,dest: I, edge: E);   
   
   edge(n1,n2: I): E;   
   -- Return the edge connecting n1  and n2   
   
   is_empty: BOOL;
   -- Returns true if no nodes in the graph
   
   subgraph(node_test: ROUT{N}: BOOL): $GRAPH{N,E,I};
   -- Return a subgraph whose nodes pass the test "node_test"
   
   degree(n: I): INT;
   -- Number of adjacent nodes to "n"
   
   connections(n: I): FLIST{I};
   -- Return set of connections from node "n"

end;
------------------------------------------------------------------- 
abstract class $DIGRAPH{
	 N,			-- Node type
	 E,			-- Edge type
	 I			-- Node index type
   } < $GRAPH{N,E,I} is
      -- A graph with information about the direction of edges
      -- Connections represent the union of incoming and outgoing edges
   
   n_parents(n: I): INT;
   -- Number of parents. degree = n_parents+n_children
   
   parents(n: I):FLIST{I};
   -- Parents of node "n"
   
   n_children(n: I): INT;
   -- Number of children. degree = n_parents+n_children
   
   children(n: I):FLIST{I};
   -- Children of node "n"
   
end;
-------------------------------------------------------------------      

