digraph_incl.sa

 
---------------------------> Sather 1.1 source file <--------------------------
-- Author: Benedict A. Gomes <gomes@tiramisu.ICSI.Berkeley.EDU>
-- Copyright (C) 1995, International Computer Science Institute
-- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
-- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
-- LICENSE contained in the file: Sather/Doc/License of the
-- Sather distribution. The license is also available from ICSI,
-- 1947 Center St., Suite 600, Berkeley CA 94704, USA.


partial class RO_DIGRAPH_INCL{NTP} < $RO_DIGRAPH{NTP} 
partial class RO_DIGRAPH_INCL{NTP} < $RO_DIGRAPH{NTP} is
   -- Partial class used to define other routines in digraphs
   -- Usage:
   --     g: DIGRAPH{INT} := #;
   --     g.add_node(1).add_node(2).add_node(3).connect(1,2).connect(1,3);
   --     Constructs:
   --      1
   --      /\
   --     2  3
   --
   --    Getting the nodes in depth first order:
   --       l:LIST{INT} := #;
   --       loop n: INT := DAG_ALG{INT, DIGRAPH{INT}}::dfs!(g);
   --           l := l.append(n);
   --        end;

   --           --------- CORE FEATURES (must define) ---------
   stub has_node(n: NTP): BOOL;
   stub has_edge(e: DIEDGE{NTP}): BOOL; 
   stub n_nodes: INT; 
   stub n_edges: INT;
   stub n_incoming(n: NTP): INT;
   stub n_outgoing(n: NTP): INT; 
   stub node!: NTP; 
   stub edge!: DIEDGE{NTP}; 
   stub incoming!(once n: NTP): NTP; 
   stub outgoing!(once n: NTP): NTP; 

   --              ------ Initialization/Duplication ------
   copy: $DIGRAPH{NTP} is
      res ::= #DIGRAPH{NTP};
      loop res.add_node(node!) end;
      loop res.connect(edge!) end;
      return res;
   end;
   
   --              ------ Queries/Comparison --------------
   size: INT is return n_nodes end;

   has(n: NTP): BOOL is return has_node(n) end;
   
   is_empty: BOOL is return n_nodes = 0 end;
   
   n_adjacent(n:NTP): INT is return n_outgoing(n) end;
   
   equals(g: $RO_DIGRAPH{NTP}):BOOL is
      -- True if both have the same set of nodes and edges
      if g.n_nodes /= n_nodes then return false end;
      if g.n_edges /= n_edges then return false end;
      loop n ::= node!; if ~g.has_node(n) then return false end; end;
      loop e ::= edge!; if ~g.has_edge(e) then return false end; end;
      return true;
   end;

   --              ------ Cursor --------------------------
   elt!: NTP is loop yield node! end; end;
   -- Returns the nodes of the graph
   
   adjacent!(once n: NTP): NTP is loop yield outgoing!(n) end; end;
   -- Adjacent is aliased to "outgoing"
   
   --              ------ Conversion ----------------------
   str: STR is
      -- Print out the graph using the bound routine "f"
      -- for the nodes   
      res ::= #FSTR("");
      loop n ::= node!;
	 -- if void(n) then res := res + "void  : ";
	 -- Should never have "void" nodes in the graph.
	 -- If they are value types, then void might be 0 or something useful
	 res := res + "["+node_str(n)+"] "; 
	 res := res + "<-";
	 loop res := res + ",".separate!(node_str(incoming!(n))); end;
	 res := res + "  ->";
	 loop res := res + ",".separate!(node_str(outgoing!(n))); end;
	 res := res+"\n";		-- End of another row of edges
      end; -- All graph nodes
      return(res.str);
   end;   

   private node_str(n: NTP): STR is
      -- There should not be void nodes in the graph!
      typecase n
      when $STR then  return(n.str); 
      else return("") end;
   end;
   
end;


partial class DIGRAPH_INCL{NTP} < $DIGRAPH{NTP} 
partial class DIGRAPH_INCL{NTP} < $DIGRAPH{NTP} is
   include RO_DIGRAPH_INCL{NTP};

   --           --------- CORE FEATURES (must define) ---------
   stub add_node: NTP;
   stub add_node(n: NTP): NTP;
   stub connect(e: DIEDGE{NTP});
   stub delete_node(n: NTP);
   stub disconnect(e: DIEDGE{NTP});
   
   -- Auxilliary versions of core features
   connect(f,s: NTP) is connect(#DIEDGE{NTP}(f,s)) end;   
   disconnect(f,s: NTP) is disconnect(#DIEDGE{NTP}(f,s)) end;   
   connect(f,s: NTP): SAME is connect(f,s); return self end;
      
end; -- class DIGRAPH_INCL