## oop-digraph.api # "digraph" == "directed graph".
#
# Here we define the "object oriented" interface to directed graphs
# which is used throughout the Mythryl compiler backend lowhalf.
# Here "object oriented" means that interaction with a graph is via
# calls to functions in its state record -- graph.this(), graph.that().
#
# The digraph actually used is typically
#
# src/lib/graph/digraph-by-adjacency-list.pkg#
# In particular, in the compiler backend lowhalf we specialize this to:
#
# src/lib/compiler/back/low/mcg/machcode-controlflow-graph-g.pkg# Compiled by:
# src/lib/graph/graphs.lib# Compare to:
# src/lib/graph/bigraph.api# src/lib/src/tuplebase.api# src/lib/std/graphtree/graphtree.api### "When spider webs unite,
### they can tie up a lion."
###
### -- Ethiopian proverb
# This api is "implemented" (actually just echoed) in:
#
# src/lib/graph/oop-digraph.pkg#
# The most commonly used underlying actual implementation is:
#
# src/lib/graph/digraph-by-adjacency-list.pkg#
api Oop_Digraph {
#
exception BAD_GRAPH String; # Bug
exception SUBGRAPH; # subgraph constraint failure
exception NOT_FOUND; # element not located
exception UNIMPLEMENTED; # method is not implemented
exception READ_ONLY; # modification fails
exception NOT_SINGLE_ENTRY; # should be single entry
exception NOT_SINGLE_EXIT; # should be single exit
Node_Id = Int;
Node(N) = (Node_Id, N);
Edge(E) = (Node_Id, Node_Id, E);
# "Digraph" == "Directed_Graph".
Digraph (N,E,G) # "N,E,G" == node, edge, graph types -- client package info associated with those graph components.
=
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,
# Collect deleted node ids:
#
garbage_collect: Void -> Void,
# Selectors:
#
nodes: Void -> List( Node(N) ),
edges: Void -> List( Edge(E) ),
#
order: Void -> Int, # # nodes
size: Void -> Int, # # edges
capacity: Void -> Int, # max. node_id < capacity
#
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
};
unimplemented: X -> Y;
# Remove one edge i->j from graph:
#
remove_edge: Digraph(N,E,G) -> (Node_Id, Node_Id ) -> Void; # Remove one edge between given nodes. No-op if none found.
remove_edge': Digraph(N,E,G) -> (Node_Id, Node_Id, (E -> Bool)) -> Void; # Remove one edge between given nodes, satisfying given predicate fn. No-op if none found.
# Remove all edges i->j from graph:
#
remove_all_edges: Digraph(N,E,G) -> (Node_Id, Node_Id ) -> Void; # Remove all edges between given nodes. No-op if none found.
remove_all_edges': Digraph(N,E,G) -> (Node_Id, Node_Id, (E -> Bool)) -> Void; # Remove all edges between given nodes, satisfying given predicate fn. No-op if none found.
};
## COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.