------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 199x 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>  <--------------

class DIGRAPH{NTP}  < $DIGRAPH{NTP} is
   -- This is a directed graph which permits arbitrary nodes of type
   -- NTP.  This is the default graph implementation. NTP is the node
   -- type i.e the unique node index The actual nodes of the graph may
   -- be supplied by the user of this class, during the add_node.  The
   -- digraph is implemented by two hash mappings from nodes to
   -- parents and nodes to outgoing. There is also a separate list of
   -- nodes.

   private include COMPARE{NTP} elt_eq->node_equal;
   include DIGRAPH_INCL{NTP};
   
   private attr node_generator: $SUCC_STREAM{NTP}; -- Generator of nodes
   -- which is used by add_node. If a node generator is not provided
   -- at creation time, then add_node cannot be used, since the graph
   -- does not know how to create new unique nodes.
   
   private attr node_list: FLIST{NTP}; -- List of nodes in the graph
   private attr incoming_map: FMULTIMAP{NTP,NTP};
   private attr outgoing_map: FMULTIMAP{NTP,NTP};
   -- Keep both around since it is quite expensive to derive one
   -- from the other.
   
   create: SAME is 
      -- Create a new digraph and return it. Since a node 
      -- generator is not specified, it will not be possible
      -- to call the "add_node:NTP" function, since the graph
      -- will not know how to create new unique nodes.
      -- All the data structures can be initialized with void
      res ::= new;
      res.incoming_map := #FMULTIMAP{NTP,NTP};
      res.outgoing_map := #FMULTIMAP{NTP,NTP};
      res.node_list := #;
      return(res) 
   end;

   create(node_gen: $SUCC_STREAM{NTP}): SAME pre ~void(node_gen) is
      -- Create a new digraph. Store "node_gen" as a generator
      -- of nodes, so that when "add_node: NTP" is called it
      -- can generate unique new nodes. 
      res: SAME := create;
      res.node_generator := node_gen;
      return res;
   end;
   
   -- ------------------- Initialization ------------------
   add_node: NTP is
      -- Add a new node and return the index
      if void(node_generator) then
	 raise #GRAPH_EXC(self,"add_node",self,
			  "Cannot call add_node: NTP on this graph."
			  " No node generator was provided");
      else
	 -- Get the next unique node
	 n: NTP := node_generator.next; 
	 -- If it is really unique, add it to the list
	 assert ~has_node(n);
	 node_list := node_list.push(n);  
	 return n;
      end;
   end;
   
   add_node(n: NTP): NTP is
      -- Add the node "n". In this kind of hash digraph, the node
      -- index returned is guaranteed to be the same as the node
      -- "n". Note that this is not generally true for graphs
      if ~has_node(n) then node_list := node_list.push(n); end;
      return n;
   end;
   
   
   add_node(n: NTP) is
      -- Short hand for "add_node(n:NTP): NTP" that is only valid
      -- for this sort of graph, where the user specifies the node
      -- type. 
      if ~has_node(n) then node_list := node_list.push(n); end;
   end;

   connect(e: DIEDGE{NTP}) is
      -- Connect source to target. No change if the edge already exists
      -- Add the nodes if they do not exist
      s ::= e.first; t ::= e.second;
      if has_edge(#DIEDGE{NTP}(s,t)) then return; end;
      if ~has_node(s) then add_node(s) end;
      if ~has_node(t) then add_node(t) end;
      outgoing_map := outgoing_map.insert(s,t);
      incoming_map := incoming_map.insert(t,s);
   end;
   
   -- ------------------- Removal -------------------------
   delete_node(n: NTP) is
      -- Delete a node from the graph, and all its accompanying edges
      node_list := node_list.delete_elt(n);
      incoming_map := incoming_map.delete_all(n);
      outgoing_map := outgoing_map.delete_all(n);
   end;
   
   disconnect(e: DIEDGE{NTP}) is
      -- Deletes the edge "e". 
      dest ::= e.second; src ::= e.first;
      incoming_map := incoming_map.delete(dest,src);
      outgoing_map := outgoing_map.delete(src,dest);
   end;

   -- ------------------- Query --------------------------
   has_node(n: NTP): BOOL is return node_list.has(n) end;
   
   has_edge(e: DIEDGE{NTP}): BOOL is
      s ::= e.first; t ::= e.second;
      if ~has_node(s) or ~has_node(t) then return false
      else return incoming_map.has_pair(t,s);   end;
   end;
   
   -- ------------------- Measurement ---------------------
   n_nodes: INT is return node_list.size end;

   n_neighbors(n: NTP): INT pre has_node(n) is 
      -- Returns the number of neighbors of "n"
      -- (nodes are only counted once)
      i: FLIST{NTP} := incoming_map.danger_multi_get(n);
      o: FLIST{NTP} := incoming_map.danger_multi_get(n);
      if i.size = 0 then return o.size 
      elsif o.size = 0 then return i.size
      else return i.union(o).size end;
   end;
   
   n_incoming(n: NTP): INT pre has_node(n) is
      -- Number of incoming edges from node "n"
      return(incoming_map.n_targets(n));
   end;

   n_outgoing(n: NTP): INT pre has_node(n) is
      -- Number of outgoing edges from node "n"
      return(outgoing_map.n_targets(n));
   end;

   n_edges: INT is
      -- Returns the number of edges in the graph, making sure
      -- each edge is only counted once
      res ::= 0;
      loop n ::= node!; res := res+n_incoming(n); end;
      return res;
   end;

   -- ------------------- Cursor --------------------------
   node!: NTP is loop yield node_list.elt! end; end;

   incoming!(once n: NTP): NTP pre has_node(n) is  
      loop yield incoming_map.target!(n) end;
   end;
   
   outgoing!(once n: NTP): NTP pre has_node(n) is  
      loop yield outgoing_map.target!(n) end;
   end;
   
   edge!: DIEDGE{NTP} is 
      -- Return all edges in the graph
      loop n ::= node!;
	 loop inc ::= incoming!(n); yield #DIEDGE{NTP}(inc,n); end;
	 -- loop outg ::= outgoing!(n); yield #DIEDGE{NTP}(n,outg); end;
      end;
   end;

   -- ------------------  COMPARING ---------------------------------
   is_identical(g: SAME): BOOL is
      -- Check whether the two graphs have the same nodes, edges in
      -- the same order
      if g.n_nodes /= n_nodes then return false end;
      loop  if ~node_equal(node!,g.node!) then return false end end;
      loop n::= node!;
	 if ~incoming_map.get_all(n).equals(g.incoming_map.get_all(n)) then 
	    return false 
	 elsif ~outgoing_map.get_all(n).equals(g.outgoing_map.get_all(n)) then 
	    return false 
	 end;
      end;
      return true
   end;

   -- Some convenient calls into algorithm classes that are not required 
   -- by the abstraction
   source!: NTP is
      -- Yield all the source nodes with n_incoming = 0 in self
      loop yield DIGRAPH_ALG{NTP,SAME}::source!(self) end;
   end;
      
   sink!: NTP is
      -- Yield all the sink nodes (with n_outgoing = 0) in self
      loop yield DIGRAPH_ALG{NTP,SAME}::sink!(self) end;
   end;
   
   bf!(once n: NTP): NTP is 
      -- Yield all nodes in breadth first order
      loop yield DIGRAPH_ALG{NTP,SAME}::bf!(self,n) end; 
   end;
   
   df!(once n: NTP): NTP is 
      -- Yield all nodes in depth first order
      loop yield DIGRAPH_ALG{NTP,SAME}::df!(self,n) end; 
   end;
   
   topo_order!: NTP is 
      -- Yield the nodes of self in some topologically sorted orer
      loop yield DIGRAPH_ALG{NTP,SAME}::topo_order!(self) end; 
   end;
   
   layer!: SET{NTP} is 
      -- Peel off successive layers from the graph, starting with the
      -- root set. Stop when no more roots (nodes with no incoming edges)
      -- can be found.
      loop yield DIGRAPH_ALG{NTP,SAME}::layer!(self) end; 
   end;

   is_topo_order(n: $ARR{NTP}):BOOL is 
      -- Return true if the nodes in "n" do not violate the precedence
      -- relations expressed by the graph "self"
      return DIGRAPH_ALG{NTP,SAME}::is_topo_order(self,n) 
   end;


   private check_node(n: NTP,routine_name: STR): BOOL is
      if has_node(n) then return true 
      else 
	 #ERR+routine_name+" received a node not in the graph\n";
	 return false;
      end;
   end;

end; -- class DIGRAPH{NTP}
-------------------------------------------------------------------
