digraph.sa
Generated by gen_html_sa_files from ICSI. Contact gomes@icsi.berkeley.edu for details
---------------------------> Sather 1.1 source file <--------------------------
-- Author: Benedict A. Gomes <gomes@icsi.berkeley.edu>
-- 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.
class DIGRAPH < $DIGRAPH{INT}
class DIGRAPH < $DIGRAPH{INT} is
-- A default digraph implementation which uses integer nodes
include DIGRAPH{INT};
create: SAME is
return create(#INT_STREAM(0));
end;
end;
class DIGRAPH{NTP} < $DIGRAPH{NTP},$SUPPORTS_REHASH
class DIGRAPH{NTP} < $DIGRAPH{NTP},$SUPPORTS_REHASH 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;
rehash is
res:SAME;
if ~void(node_generator) then res := #SAME(node_generator);
else res := #SAME; end;
loop discard ::= res.add_node(node!) end;
loop e ::= edge!;
res.connect(#DIEDGE{NTP}(e.first,e.second));
end;
node_list := res.node_list;
incoming_map := res.incoming_map;
outgoing_map := res.outgoing_map;
end;
-- Adaptors
-- reverse_graph: DIGRAPH_REVERSE_VIEW{NTP} is
-- return(#DIGRAPH_REVERSE_VIEW{NTP}(self));
-- end;
-- subgraph: DIGRAPH_SUBGRAPH_VIEW{NTP} is
-- return(#DIGRAPH_SUBGRAPH_VIEW{NTP}(self));
-- end;
-- undirected: DIGRAPH_UNDIRECTED_VIEW{NTP} is
-- return(#DIGRAPH_UNDIRECTED_VIEW{NTP}(self));
-- end;
end; -- class DIGRAPH{NTP}