digraph_views.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 (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.
-- Design Note:
-- It might be useful to have versions of these views which are
-- pre-parametrized over $RO_DIGRAPH or $DIGRAPH for convenience
-- These have been written and could be added, but it is not
-- clear whether they help just confuse matters
class DIGRAPH_NODE_SET_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_SET{NTP}
class DIGRAPH_NODE_SET_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_SET{NTP} is
-- A view of the nodes of a digraph as a set. This is useful for
-- looking at set properties of the nodes in the graph, for instance,
-- finding the union or intersection of the nodes in two graphs
-- Please see the notes in the module file
include RO_SET_INCL{NTP};
private attr graph: GTP;
create(g: GTP): SAME is res::=new; res.graph:=g; return res; end;
-- Create a new view of the nodes of "g"
copy: SAME is
-- Return a copy of the nodes in this set
return #SAME(graph);
end;
has(n: NTP): BOOL is return graph.has_node(n) end;
-- Return true if the original graph has the node "n"
size: INT is return graph.n_nodes end;
-- Return the number of nodes in the orignal graph
elt!: NTP is loop yield graph.node! end; end;
-- Return the nodes of the original graph
end;
class DIGRAPH_EDGE_SET_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_SET{DIEDGE{NTP}}
class DIGRAPH_EDGE_SET_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_SET{DIEDGE{NTP}} is
-- View of the edges of a graph as a read-only set.
-- Design Note:
-- Letting this set be writable is interesting, but can lead to
-- very confusing results due to aliasing.
include RO_SET_INCL{DIEDGE{NTP}};
private attr graph: GTP;
-- Holds a pointer to the actual graph being viewed
create(g: GTP): SAME is res::=new;res.graph:=g;return res; end;
-- Create a view of the set of edges of the digraph "g"
has(e: DIEDGE{NTP}): BOOL is return graph.has_edge(e) end;
-- Return true if the digraph contains the edge "e"
size: INT is return graph.n_edges end;
-- Returns the number of edges in the digraph
elt!: DIEDGE{NTP} is loop yield graph.edge! end; end;
-- Yields the edges of the digraph
copy: SAME is return #(graph) end;
-- Returns a copy of the original digraph
end;
class DIGRAPH_INC_SET_VIEW{NTP,GTP<$DIGRAPH{NTP}} < $RO_SET{NTP}
class DIGRAPH_INC_SET_VIEW{NTP,GTP<$DIGRAPH{NTP}} < $RO_SET{NTP} is
-- View of the incoming edges into the node of a digraph.
include RO_SET_INCL{NTP} has->, elt!->;
private attr graph: GTP;
-- A pointer to the original graph being viewed
private attr dest: NTP;
-- The node whose incoming edges are being viewed
create(g: GTP,dest: NTP): SAME is
-- Create a view of the set of incoming nodes to "dest" in the
-- graph "g"
res ::= new; res.graph := g; res.dest := dest; return res;
end;
has(n: NTP): BOOL is return graph.has_edge(#DIEDGE{NTP}(n,dest)) end;
-- Return true if node "dest" has an incoming edge from "n"
size: INT is return graph.n_incoming(dest) end;
-- Return the number of incoming edges into "dest"
elt!: NTP is loop yield graph.incoming!(dest) end; end;
-- Yield the nodes which have edges to "dest"
copy: SAME is return #(graph,dest) end;
-- Return a copy of self
end;
class DIGRAPH_OUTG_SET_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_SET{NTP}
class DIGRAPH_OUTG_SET_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_SET{NTP} is
-- View of the outgoing edges into the node of a digraph.
include RO_SET_INCL{NTP};
private attr graph: GTP;
-- The graph being viewed
private attr src: NTP;
-- The node whose outgoing edges are being viewed
create(g:GTP, src: NTP): SAME is return new.init(g,src); end;
private init(g: GTP,s: NTP): SAME is
graph := g; src:=s; return self
end;
has(n: NTP): BOOL is return graph.has_edge(#DIEDGE{NTP}(src,n)) end;
size: INT is return graph.n_outgoing(src) end;
elt!: NTP is loop yield graph.outgoing!(src) end; end;
copy: SAME is return #(graph,src) end;
-- Return a copy of self
end;
class DIGRAPH_REV_DIGRAPH_VIEW{NTP,GTP<$DIGRAPH{NTP}} < $DIGRAPH{NTP}
class DIGRAPH_REV_DIGRAPH_VIEW{NTP,GTP<$DIGRAPH{NTP}} < $DIGRAPH{NTP} is
-- A view of a digraph with all edges reversed. Unlike most other
-- views, this view of the graph permits modification operations,
-- which are translated into operations on the original graph.
-- Care should be taken in operations that involved both the
-- original graph and this view
include DIGRAPH_INCL{NTP};
private attr source:GTP;
create(m:GTP): SAME is
-- Create a subgraph of "m"
res ::= new;
res.source := m;
return(res);
end;
add_node: NTP is return source.add_node end;
add_node(n: NTP): NTP is return source.add_node(n); end;
connect(e: DIEDGE{NTP}) is source.connect(e.reverse); end;
delete_node(n: NTP) is source.delete_node(n) end;
disconnect(e: DIEDGE{NTP}) is source.disconnect(e.reverse) end;
has_node(n: NTP): BOOL is return source.has_node(n) end;
has_edge(e: DIEDGE{NTP}): BOOL is return source.has_edge(e.reverse) end;
n_edges: INT is
i ::= 0; loop n ::= node!; i := i + n_incoming(n); end;
return i;
end;
n_nodes: INT is return(source.n_nodes) end;
n_incoming(n: NTP): INT is return source.n_outgoing(n) end;
n_outgoing(n: NTP): INT is return source.n_incoming(n) end;
node!: NTP is loop yield source.node! end; end;
edge!: DIEDGE{NTP} is
loop n ::= node!;
loop inc::= incoming!(n); yield #DIEDGE{NTP}(inc,n); end;
end;
end;
incoming!(once n: NTP): NTP is loop yield source.outgoing!(n) end; end;
outgoing!(once n: NTP): NTP is loop yield source.incoming!(n) end; end;
end;
class FILTERGRAPH_DIGRAPH_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_DIGRAPH{NTP}
class FILTERGRAPH_DIGRAPH_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_DIGRAPH{NTP} is
-- View a graph through a node/edge filter predicate
-- Only the nodes and edges that satisfy the predicates are visible
-- as nodes and edges in this view.
-- If the node predicate is "np" and the edge predicate is "ep",
-- Nodes which satisfy "np" are in the graph
-- Edges which satisfy "ep" and whose nodes are both satisfied by
-- "np" are in the graph.
include RO_DIGRAPH_INCL{NTP};
private attr source:GTP;
private attr np: ROUT{NTP}: BOOL;
private attr ep: ROUT{DIEDGE{NTP}}: BOOL;
create(m:GTP,np:ROUT{NTP}:BOOL,ep:ROUT{DIEDGE{NTP}}:BOOL): SAME
-- Create a subgraph of "m". It consists of nodes that pass the
-- node filter "np" and edges that pass the edge filter,
-- whose ends pass the node filter.
-- Nodes n that belong to "m" and np.call(n) = true
-- Edges e (1) m.has_edge(e)
-- (2) np.call(e.first) and np.call(e.second)
-- (3) ep.call(e)
is
res ::= new;
res.source := m;
res.np := np;
res.ep := ep;
return(res);
end;
create(m:GTP,np:ROUT{NTP}:BOOL): SAME is
-- Create a subgraph of "m", which includes all nodes that pass
-- the node filter "np"
res ::= new;
res.source := m;
res.np := np;
res.ep := void;
return(res);
end;
has_node(n: NTP): BOOL is return source.has_node(n) and np.call(n) end;
has_edge(e: DIEDGE{NTP}): BOOL is
-- An edge exists here if and only if it exists in the source,
-- both its end points pass the node filter and the edge itself
-- passes the edge filter
ef ::= e.first; es ::= e.second;
if void(ep) then
return source.has_edge(e) and np.call(ef) and np.call(es);
else
return source.has_edge(e) and np.call(ef) and np.call(es) and
ep.call(e)
end;
end;
n_nodes: INT is
i ::= 0; loop n ::= node!; i := i + 1; end; return i;
end;
n_edges: INT is
i ::= 0; loop n ::= node!; i := i + n_incoming(n); end;
return i;
end;
n_incoming(n: NTP): INT is
-- Compute the number of edges by actually iterating over the
-- edges and returning the resulting number found
i ::= 0; loop discard ::= incoming!(n); i := i + 1; end;
return i;
end;
n_outgoing(n: NTP): INT is
-- Compute the number of outgoing edges by actually iterating over them
i ::= 0; loop discard ::= outgoing!(n); i := i + 1; end;
return i;
end;
node!: NTP is
-- Yield all the nodes in the source that pass the filter node predicate
loop n ::= source.node!; if np.call(n) then yield n end; end;
end;
edge!: DIEDGE{NTP} is
loop n ::= node!;
loop inc::= incoming!(n); yield #DIEDGE{NTP}(inc,n); end;
end;
end;
incoming!(once n: NTP): NTP
pre has_node(n)
post has_edge(#DIEDGE{NTP}(n,result))
-- Yield all the incoming nodes from node "n". Yield only nodes
-- which pass the filter and are connected by an edge that passes the filter
is
loop inc ::= source.incoming!(n);
if np.call(inc) and ep.call(#DIEDGE{NTP}(inc,n)) then yield inc end;
end;
end;
outgoing!(once n: NTP): NTP
-- Yield all the outgoing nodes from node "n". Yield only nodes
-- which pass the filter and are connected by an edge that passes the filter
pre has_node(n)
post has_edge(#DIEDGE{NTP}(n,result))
is
loop og ::= source.outgoing!(n);
if np.call(og) and ep.call(#DIEDGE{NTP}(n,og)) then yield og end;
end;
end;
end;
-- Note:
-- Simplifications of corresponding class with the graph argument
-- where the graph is assumed to be a generic $RO_DIGRAPH
-- This version is convenient to use but may be considerably less
-- efficient than the version with 2 parameters.
-- If the type of the graph is known, the parametrized version
-- has a strongly typed pointer to the actual graph, allowing
-- many optimizations such as inlining, in addition to avoiding
-- dispatching
class DIGRAPH_NODE_SET_VIEW{NTP} < $RO_SET{NTP}
class DIGRAPH_NODE_SET_VIEW{NTP} < $RO_SET{NTP} is
-- Simplification of DIGRAPH_NODE_SET_VIEW which has a pointer
-- to a generic $DIGRAPH{NTP}. Less efficient
include DIGRAPH_NODE_SET_VIEW{NTP,$RO_DIGRAPH{NTP}};
end;
class DIGRAPH_EDGE_SET_VIEW{NTP} < $RO_SET{DIEDGE{NTP}}
class DIGRAPH_EDGE_SET_VIEW{NTP} < $RO_SET{DIEDGE{NTP}} is
-- Simplification of DIGRAPH_EDGE_SET_VIEW with 2 parameters
include DIGRAPH_EDGE_SET_VIEW{NTP,$RO_DIGRAPH{NTP}};
end;
class DIGRAPH_INC_SET_VIEW{NTP} < $RO_SET{NTP}
class DIGRAPH_INC_SET_VIEW{NTP} < $RO_SET{NTP} is
-- Simplification of DIGRAPH_INC_SET_VIEW with 2 parameters
include DIGRAPH_INC_SET_VIEW{NTP,$RO_DIGRAPH{NTP}};
end;
class DIGRAPH_OUTG_SET_VIEW{NTP} < $RO_SET{NTP}
class DIGRAPH_OUTG_SET_VIEW{NTP} < $RO_SET{NTP} is
-- Simplification of DIGRAPH_OUTG_SET_VIEW with 2 parameters
include DIGRAPH_OUTG_SET_VIEW{NTP,$RO_DIGRAPH{NTP}};
end;
class FILTERGRAPH_DIGRAPH_VIEW{NTP} < $RO_DIGRAPH{NTP}
class FILTERGRAPH_DIGRAPH_VIEW{NTP} < $RO_DIGRAPH{NTP} is
-- Simplification of FILTERGRAPH_DIGRAPH_VIEW
include FILTERGRAPH_DIGRAPH_VIEW{NTP,$RO_DIGRAPH{NTP}};
end;
class DIGRAPH_REV_DIGRAPH_VIEW{NTP} < $DIGRAPH{NTP}
class DIGRAPH_REV_DIGRAPH_VIEW{NTP} < $DIGRAPH{NTP} is
-- Simplification of DIGRAPH_REV_DIGRAPH_VIEW
include DIGRAPH_REV_DIGRAPH_VIEW{NTP,$DIGRAPH{NTP}};
end;