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

-- Directed graph class implementation using an adjacency matrix
-- Author: Oliver Quigley <osquigle@midway.uchicago.edu>
-- Date: 6/18/97

class DIGRAPH_MAT{NTP} < $DIGRAPH{NTP} is
   include DIGRAPH_INCL{NTP};
   private attr adjmat:         MAT; -- the adjacency matrix.  It
   -- would probably be cleverer to use BOOLs instead of INTs in the
   -- matrix, but ordinary MATs are easier to deal with at first.
   private attr size:           INT; -- the number of nodes we've
   -- allocated space for.  The adjacency matrix grows by amortized
   -- doubling; this attribute keeps track of how much space is
   -- allocated.
   private attr num_nodes:      INT; -- the number of nodes actually
   -- in the adjacency matrix.
   private attr node_list:      FLIST{NTP}; -- the nodes
   private attr node_generator: $SUCC_STREAM{NTP}; -- Generator
   -- of nodes which is used by add_node.  If a 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.
   
   create: SAME 
   -- Create a new directed graph and return it.  This version
   -- of the constructor does not take a node generator as a
   -- parameter; digraphs created using this constructor will
   -- not be able to use add_node:NTP.  See the note after
   -- node_generator.
   is
      res ::= new;
      -- adjmat will remain void until an element is added.
      res.size := #(0);
      res.num_nodes := #(0);
      res.node_list := #;
      return(res);
   end;

   create(node_gen: $SUCC_STREAM{NTP}): SAME
      pre ~void(node_gen)
   -- Create a new directed graph and return it.  This constructor
   -- takes a node generator as a parameter: this generator will be
   -- used to create new unique nodes in add_node:NTP.  See the note
   -- in create: SAME and after node_generator.
   is
      res ::= new;
      -- adjmat will remain void until an element is added
      res.size := #(0);
      res.num_nodes := #(0);
      res.node_list := #;
      res.node_generator := node_gen;
      return res;
   end;
    
   add_node(n: NTP)
   -- Add a node to the graph
   is
      if void(adjmat) then	-- first node in matrix
	 #ERR + "add_node called for the first time: creating adjmat\n";
	 adjmat := #MAT(1,1);
	 num_nodes := 1;
	 size := 1;
	 node_list := node_list.push(n);
      elsif  ~has_node(n) then
	 node_list := node_list.push(n);
	 add_to_adjmat;
      end;
   end;   
   
   private add_to_adjmat
   -- Adds a new row and column to the adjacency matrix.  If the
   -- matrix would be bigger than the space allocated, allocate
   -- a new matrix with twice the dimensions and copy the old
   -- matrix into it.
   is
      num_nodes := num_nodes + 1;
      if num_nodes > size then
	 #ERR + "Increasing matrix size from " + size + " to " + 
	       (2 * size) + "\n";
	 tmp ::= #MAT(2*size, 2*size);
	 loop
	    r ::= adjmat.ind1!;
	    loop
	       c ::= adjmat.ind2!;
	       tmp[r,c]  := adjmat[r,c];
	    end;
	 end;
	 adjmat := tmp;
	 size := 2*size;
      end;
      loop
	 adjmat.set_row!(num_nodes - 1, #FLT(0));
      end;
      loop
	 adjmat.set_col!(num_nodes - 1, #FLT(0));
      end;
   end;

   add_node(n: NTP): NTP
   -- Add a node to the graph and return the index.
   is
      add_node(n);
      return n;
   end;

   add_node: NTP
   -- Create a new node, add it to the graph, and return the index.
   is
      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
	 n: NTP := node_generator.next; -- Create a new node.
	 assert ~has_node(n);	-- It ought to be unique.
	 return add_node(n);
      end;
   end;
   
   connect(e: DIEDGE{NTP})
   -- Add edge e to the graph.  If the nodes do not exist in the graph,
   -- add them.
   is
      if ~has_node(e.first) then 
	 add_node(e.first);
      end;
      if ~has_node(e.second) then
	 add_node(e.second);
      end;
      
      adjmat[node_list.index_of(e.first), node_list.index_of(e.second)] 
	    := #FLT(1);
   end;
   
   delete_node(n: NTP)
   -- Delete a node n from the graph. -- TEST ME!
   is
      assert has_node(n);
      ind ::= node_list.index_of(n);
      loop
	 c:INT := adjmat.nc.downto!(ind+1);
	 v ::= adjmat.col(c);
	 adjmat.inplace_swapped_col(c-1,v); -- put v into prev. col., and
	 -- put prev col into v.  In this manner, we swap the current row
	 -- with the previous one until we get to the col. we're deleting.
      end;
      num_nodes := num_nodes - 1;
      if num_nodes < (size / 3) then -- if the matrix uses < 1/3 of the
	 -- space allocated for it, allocate a new, smaller matrix.
	 tmp ::= #MAT(size/3, size/3);
	 loop
	    r ::= tmp.ind1!;
	    loop
	       c ::= tmp.ind2!;
	       tmp[r,c]  := adjmat[r,c];
	    end;
	 end;
      end;
   end;

   disconnect(e: DIEDGE{NTP})
   -- Remove edge e from the graph.
   is
      assert has_edge(e);

      adjmat[node_list.index_of(e.first), node_list.index_of(e.second)] 
	    := #FLT(0);
   end;
   
   has_edge(e: DIEDGE{NTP}): BOOL
   -- Returns true if edge e is in the graph.
   is
      if ~has_node(e.first) or ~has_node(e.second) then
	 return false;
      else
	 return adjmat[node_list.index_of(e.first), 
		       node_list.index_of(e.second)] = 1;
      end;
   end;
   
   has_node(n: NTP): BOOL
   -- Returns true if node n is in the graph.
   is
      return node_list.has(n);
   end;
   
   is_identical(g: SAME): BOOL
   -- Returns true if graph g has the same nodes and edges as this graph
   is
      if ~node_list.difference(g.node_list).is_empty then
	 return false;
      elsif adjmat.submatrix(0,0,num_nodes, num_nodes) /= 
	 g.adjmat.submatrix(0,0,num_nodes,num_nodes) then
	 return false;
      else
	 return true;
      end;
   end;
   
   is_topo_order(n: $ARR{NTP}): BOOL
   -- Returns true if the nodes in n do not violate the precedence
   -- relations expressed by the graph "self"
   is
      return DIGRAPH_ALG{NTP, SAME}::is_topo_order(self,n);
   end;
   
   n_edges: INT
   -- Return the number of unique edges in the graph
   is
      count:INT := 0;
      loop
	 r ::= 0 .upto!(num_nodes);
	 loop
	    c ::= 0.upto!(num_nodes);
	    if adjmat[r,c] = 1 then 
	       count := count + 1;
	    end;
	 end;
      end;
      return count;
   end;
   
   n_incoming(n: NTP): INT
   -- Returns number of incoming edges for node n
   is
      assert has_node(n);

      sum ::= #INT(0);
      i ::= adjmat.col(node_list.index_of(n)); -- incoming edge vector
      
      loop
	 sum := sum + i.aelt!.int;
      end;
      return sum;
   end;
   
   n_neighbors(n: NTP): INT
   -- Returns the number of neighbors of node "n" (nodes are counted once)
   is
      assert has_node(n);

      ind ::= node_list.index_of(n);
      count:INT := 0;
      
      i ::= adjmat.col(ind);	-- vector of incoming edges
      o ::= adjmat.row(ind);	-- vector of outgoing edges
      s ::= i + o;		-- total connections to each other node
 
      loop
	 if s.aelt! /= 0 then 
	    count := count + 1;
	 end;
      end;
      return count;
   end;
   
   n_nodes: INT
   -- Returns the number of nodes in the graph.
   is
      return num_nodes;
   end;
   
   n_outgoing(n: NTP): INT
   -- Returns number of outgoing edges from node n
   is
      assert has_node(n);
      
      sum:INT := 0;
      o ::= adjmat.row(node_list.index_of(n)); -- outgoing edge vector
      
      loop
	 sum := sum + o.aelt!.int;
      end;
      return sum;
   end;

   bf!(once n: NTP): NTP
   -- Yield all nodes in breadth-first order
   is
      loop yield DIGRAPH_ALG{NTP, SAME}::bf!(self, n) end;
   end;
   
   df!(once n: NTP): NTP
   -- Yield all nodes in depth-first order
   is
      loop yield DIGRAPH_ALG{NTP, SAME}::df!(self, n) end;
   end;
   
   topo_order!: NTP
   -- Yield the nodes of self in some topologically sorted order
   is
      loop yield DIGRAPH_ALG{NTP, SAME}::topo_order!(self) end;
   end;
   
   layer!: SET{NTP}
   -- 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.
   is
      loop yield DIGRAPH_ALG{NTP, SAME}::layer!(self) end;
   end;

   node!: NTP
   -- Yield the various nodes in the graph
   is
      loop yield node_list.elt! end;
   end;
   
   edge!: DIEDGE{NTP}
   -- Yield the edges of the graph
   is
      loop
	 r ::= 0.upto!(num_nodes);
	 loop
	    c ::= 0.upto!(num_nodes);
	    if adjmat[r,c] /= 0 then
	       yield #DIEDGE{NTP}(node_list[r], node_list[c]);
	    end;
	 end;
      end;
   end;
   
   incoming!(once n: NTP): NTP
   -- Yield the nodes with connections to n
   is
      assert has_node(n);
      
      i ::= adjmat.col(node_list.index_of(n)); -- incoming edge vector
      
      loop
	 ind: INT := 0.upto!(i.dim);
	 if i[ind] /= 0 then
	    yield node_list[ind];
	 end;
      end;
   end;
   
   outgoing!(once n: NTP): NTP
   -- Yield nodes n connects to
   is
      assert has_node(n);
      
      o ::= adjmat.row(node_list.index_of(n)); -- outgoing edge vector
      
      loop
	 ind: INT := 0.upto!(o.dim);
	 if o[ind] /= 0 then
	    yield node_list[ind];
	 end;
      end;
   end;
   
   sink!: NTP
   -- Yield all the sink nodes (n_outgoing = 0) in graph
   is
      loop yield DIGRAPH_ALG{NTP, SAME}::sink!(self) end;
   end;
   
   source!: NTP
   -- Yield all source nodes (n_incoming = 0) in graph
   is
      loop yield DIGRAPH_ALG{NTP, SAME}::source!(self) end;
   end;
   
end; -- class DIGRAPH_MAT{NTP}
