## oop-digraph.pkg
#
# A generic directed graph data package.
# Implemented in an ``object oriented style''
#
# All Mythryl compiler backend lowhalf graphs
# are based on this interface.
#
# -- Allen Leung
#
# For a production instantiation of this framework see:
#
# src/lib/compiler/back/low/mcg/machcode-controlflow-graph-g.pkg# Compiled by:
# src/lib/graph/graphs.lib# Here we define only an api and a few convenience functions.
# For a full implementation see:
#
# src/lib/graph/digraph-by-adjacency-list.pkg#
package oop_digraph
: (weak) Oop_Digraph # Oop_Digraph is from src/lib/graph/oop-digraph.api{
exception BAD_GRAPH String;
exception SUBGRAPH;
exception NOT_FOUND;
exception UNIMPLEMENTED;
exception READ_ONLY;
exception NOT_SINGLE_ENTRY;
exception NOT_SINGLE_EXIT;
fun unimplemented _ = raise exception UNIMPLEMENTED;
Node_Id = Int;
Node(N) = (Node_Id, N);
Edge(E) = (Node_Id, Node_Id, E);
# "Digraph" == "Directed_Graph".
Digraph (N,E,G) # Here N,E,G stand stead for the types of client-package-supplied records associated with (respectively) nodes, edges and graphs.
=
DIGRAPH Graph_Methods(N,E,G)
withtype
Graph_Methods (N,E,G)
=
{ name: String,
graph_info: G,
# Inserting/removing nodes and edges:
#
allot_node_id: Void -> Node_Id,
add_node: Node(N) -> Void,
add_edge: Edge(E) -> Void,
remove_node: Node_Id -> Void,
#
set_out_edges: (Node_Id, List(Edge(E))) -> Void,
set_in_edges: (Node_Id, List(Edge(E))) -> Void,
#
set_entries: List(Node_Id) -> Void,
set_exits: List(Node_Id) -> Void,
garbage_collect: Void -> Void,
nodes: Void -> List(Node(N)),
edges: Void -> List(Edge(E)),
#
order: Void -> Int,
size: Void -> Int,
capacity: Void -> Int,
#
next: Node_Id -> List( Node_Id ),
prior: Node_Id -> List( Node_Id ),
#
out_edges: Node_Id -> List( Edge(E) ),
in_edges: Node_Id -> List( Edge(E) ),
#
has_edge: (Node_Id, Node_Id) -> Bool,
has_node: Node_Id -> Bool,
#
node_info: Node_Id -> N,
#
entries: Void -> List(Node_Id),
exits: Void -> List(Node_Id),
#
entry_edges: Node_Id -> List(Edge(E)),
exit_edges: Node_Id -> List(Edge(E)),
# Iterators:
#
forall_nodes: (Node(N) -> Void) -> Void,
forall_edges: (Edge(E) -> Void) -> Void
};
fun remove_all_edges (DIGRAPH graph) (i, j)
=
graph.set_out_edges (i, list::filter (\\ (_, k, _) = k == j) (graph.out_edges i));
fun remove_all_edges' (DIGRAPH graph) (i, j, p)
=
graph.set_out_edges (i, list::filter (\\ (_, k, e) = k == j and p e)
(graph.out_edges i));
fun remove_edge (DIGRAPH graph) (i, j)
=
graph.set_out_edges (i, filter (graph.out_edges i))
where
fun filter [] => [];
filter ((e as (_, k, _)) ! es)
=>
j == k ?? es
:: e ! filter es;
end;
end;
fun remove_edge' (DIGRAPH graph) (i, j, p)
=
graph.set_out_edges (i, filter (graph.out_edges i))
where
fun filter [] => [];
filter((e as (_, k, e')) ! es)
=>
if (j == k and p e') es;
else e ! filter es;
fi;
end;
end;
};