ugraph.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@tiramisu.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 UGRAPH{NTP} < $UGRAPH{NTP}
class UGRAPH{NTP} < $UGRAPH{NTP} is
-- For now, call this UGRAPH since we have no other graph
-- implementations.
-- A basic undirected graph implemented with a hash table from
-- nodes to neighbors. This implementation
-- mainly specifies the access routines.
include UGRAPH_INCL{NTP};
private attr node_list: FLIST{NTP};
private attr neighbor_map: FMAP{NTP,FLIST{NTP}};
-- holds mappings from each node to all it's neighbors
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.
-- ------------------- Initialization ------------------
create: SAME is
-- All the data structures can be initialized with void
res ::= new;
res.neighbor_map := #FMAP{NTP,FLIST{NTP}};
res.node_list := #;
return(res)
end;
create(node_gen: $SUCC_STREAM{NTP}): SAME pre ~void(node_gen) is
-- Create a new ugraph. 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;
copy: SAME is
res ::= #SAME;
loop res.add_node(node!) end;
loop res.connect(edge!) end;
return res;
end;
-- ------------------- Insertion -----------------------
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);
add_node(n);
return n;
end;
end;
add_node(n: NTP):NTP pre ~test_node(n) is
-- Replaces an existing node that is the same as "n"
-- This function is guaranteed to return the same node, "n"
-- though this is not true of graph implementations in general
node_list := node_list.push(n);
neighbor_map := neighbor_map.insert(n,#FLIST{NTP});
return n;
end;
add_node(n: NTP) is
-- Add a node "n".
--
-- Technical detail: Since the node index for "n" is the
-- same as the node for this particular implementation,
-- there is no need to return a value. Note that this function
-- is not in the graph abstraction
discard ::= add_node(n);
end;
connect(n1,n2: NTP) is
-- Connect n1 and n2. Add the nodes if they do not exist
if test_edge(n1,n2) then return; end;
if ~test_node(n1) then add_node(n1) end;
if ~test_node(n2) then add_node(n2) end;
add_neighbor(n1,n2);
end;
-- ------------------- Removal -------------------------
delete_node(n: NTP) is
-- Delete a node from the graph, and all its accompanying edges
node_list.delete(node_list.index_of(n));
neighbor_map := neighbor_map.delete(n);
end;
disconnect(n1,n2: NTP) pre test_node(n1) and test_node(n2) is
-- Deletes the edge between n1 and n2 if it exists
n1list ::= neighbor_list(n1);
n2list ::= neighbor_list(n2);
neighbor_map := neighbor_map.insert(n1,n1list.delete_elt(n2));
neighbor_map := neighbor_map.insert(n2,n2list.delete_elt(n1));
end;
-- ------------------- Comparison ----------------------
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 ~elt_eq(node!,g.node!) then return false end end;
loop n::= node!;
if ~neighbor_map.get(n).equals(g.neighbor_map.get(n)) then
return false
end;
end;
return true
end;
-- ------------------- Transformation ------------------
permute_nodes(new_positions: $MAP{NTP,INT}) is
-- Permute the nodes of the graph so that they will
-- be yielded in the order expressed by "new_positions"
perm_arr: ARRAY{INT} := #(node_list.size);
loop perm_arr.set!(new_positions[node_list.elt!]) end;
new_src: FLIST{NTP} := #(node_list.size);
loop new_src := new_src.push(node_list.elt!) end;
permute_alg: A_PERMUTE{NTP,FLIST{NTP}};
permute_alg.permute_into(new_src,perm_arr,node_list);
-- node_list.permute(perm_arr);
end;
sort is
-- Reduce the graph to a canonical form based on the
-- sorting order of nodes and edges
sorter:A_SORT{NTP,FLIST{NTP}};
sorter.sort(node_list);
loop n ::= node_list.elt!; -- Sort edges
neighbors ::= neighbor_map.get(n);
sorter.sort(neighbors);
end;
end;
-- ------------------- Implementation ------------------
test_node(n: NTP): BOOL is return neighbor_map.test(n) end;
n_nodes: INT is return node_list.size end;
node!: NTP is loop yield node_list.elt! end; end;
test_edge(s,t: NTP): BOOL is
if ~test_node(s) or ~test_node(t) then return false
else return neighbor_map.get(t).contains(s); end;
end;
n_adjacent(n: NTP): INT pre test_node(n) is
return(neighbor_map.get(n).size);
end;
adjacent!(once n: NTP): NTP pre check_node(n,"adjacent!") is
neighbors ::= neighbor_map.get(n);
loop yield neighbors.elt! end;
end;
new_edge(n1,n2: NTP): UEDGE{NTP} is return #UEDGE{NTP}(n1,n2) end;
edge!: UEDGE{NTP} is
-- Return all edges in the graph. A problem, since we represent
-- edges in both directions. We might want to either maintain
-- a hash table of edges already seen or generate a matching
-- or something of the sort.
-- Or can use some arbitrary test to choose one or the other.
-- such as lt
-- For now, use a set which holds all nodes for which all edges
-- have been yielded
seen: FSET{NTP} := #; -- Holds all nodes that have had their
-- edges yielded
loop n1 ::= node_list.elt!;
n1_neighbors ::= neighbor_map.get(n1);
loop n2 ::= n1_neighbors.elt!;
if ~seen.test(n2) then yield new_edge(n2,n1); end;
end;
seen := seen.insert(n1);
end;
end;
-- ----------------------- Private accessing functions ---------------
private check_node(n: NTP,routine_name: STR): BOOL is
if test_node(n) then return true
else
#ERR+routine_name+" received a node not in the graph\n";
return false;
end;
end;
private add_neighbor(n1,n2: NTP) is
neighbor_map:=neighbor_map.insert(n1,neighbor_map.get(n1).push(n2));
neighbor_map:=neighbor_map.insert(n2,neighbor_map.get(n2).push(n1));
end;
private neighbor_list(n1:NTP):FLIST{NTP} is
return neighbor_map.get(n1)
end;
-- sort_by(lt: ROUT{NTP,NTP}:BOOL) is
-- Reduce the graph to a cannoical form using the predicate "lt"
-- to determine the less than relation between two nodes
-- ARR_ALG{NTP,FLIST{NTP}}::sort_by(node_list,lt);
-- Sort edges
-- loop n ::= node_list.elt!;
-- neighbors ::= neighbor_map.get(n);
-- ARR_ALG{NTP,FLIST{NTP}}::sort_by(neighbors,lt);
-- end;
-- end;
-- create_from(g: $GRAPH{NTP}): SAME is
-- -- Return a graph created from "g"
-- res ::= #;
-- loop res.add_node(g.node!) end;
-- loop res.add_edge(g.edge!) end;
-- return(res);
-- end;
end;