## graphtree.api
#
# This defines the base-level graph interface for show-graph.
#
# The primary functionality supported consists
# of nodes and directed edges between them.
#
# Also supported are subgraphs, intended to
# be used essentially as a region-of-interest
# mechanism to distinguish particular parts of
# a graph. Consequently the full structure
# comprises a tree of subgraphs in which each
# graph contains all the nodes and edges of all
# its subgraphs.
#
# We build on this to define traitful_graphtree in
#
# src/lib/std/graphtree/traitful-graphtree-g.pkg#
# which is in turn used to define our two concrete graph types in
#
# src/lib/std/dot/dot-graphtree.pkg# src/lib/std/dot/planar-graphtree.pkg# Compiled by:
# src/lib/std/standard.lib# Compare to:
# src/lib/graph/oop-digraph.api# src/lib/graph/bigraph.api# src/lib/src/tuplebase.api# src/lib/std/graphtree/graphtree.api# This api is implemented by:
# src/lib/std/graphtree/graphtree-g.pkgapi Graphtree {
Graph;
Edge;
Node;
Graph_Info; # Arbitrary per-graph user information. (Supplied as arg to graphtree_g generic.)
Edge_Info; # Arbitrary per-edge user information. (Supplied as arg to graphtree_g generic.)
Node_Info; # Arbitrary per-node user information. (Supplied as arg to graphtree_g generic.)
exception GRAPHTREE_ERROR String;
make_graph: Graph_Info -> Graph;
make_subgraph: (Graph, Graph_Info) -> Graph;
node_count: Graph -> Int; # Number of nodes in graph. (O(1) op.)
edge_count: Graph -> Int; # Number of edges in graph. (O(N) op.)
make_node: (Graph, Node_Info) -> Node; # Create node, add to graph and its ancestor graphs.
put_node: (Graph, Node) -> Void; # Add existing node to graph. Used to populate subgraphs.
drop_node: (Graph, Node) -> Void;
#
nodes: Graph -> List(Node); # Return list of all Nodes in graph.
nodes_apply: (Node -> Void) -> Graph -> Void; # Apply a function to all Nodes in graph.
nodes_fold: ((Node, X) -> X) -> Graph -> X -> X; # Fold a function over all Nodes in graph.
make_edge: { # Create a new edge and add to graph.
graph: Graph, # Must be root of its graphtree.
head: Node, # Must belong to graph.
tail: Node, # Must belong to graph.
info: Edge_Info
}
->
Edge;
drop_edge: (Graph, Edge) -> Void;
edges: Graph -> List( Edge ); # Return all edges in graph. (O(N) op.)
in_edges: (Graph, Node) -> List(Edge); # Return the list of edges entering given node. (O(1) op.)
out_edges: (Graph, Node) -> List(Edge); # Return the list of edges leaving given node. (O(1) op.)
in_edges_apply: (Edge -> Void) -> (Graph, Node) -> Void; # Apply fn to all edges entering node.
out_edges_apply: (Edge -> Void) -> (Graph, Node) -> Void; # Apply fn to all edges leaving node.
head: Edge -> Node;
tail: Edge -> Node;
nodes_of: Edge -> { head: Node,
tail: Node
};
is_root: Graph -> Bool; # TRUE iff this graph is the root of its graphtree. (No supergraph.)
root_of_node: Node -> Graph; # Root graph of node's graphtree.
root_of_edge: Edge -> Graph; # Root graph of edge's graphtree.
root_of_graph: Graph -> Graph; # Root graph of graph's graphtree.
has_node: (Graph, Node) -> Bool;
has_edge: (Graph, Edge) -> Bool;
eq_graph: (Graph, Graph) -> Bool;
eq_node: (Node, Node) -> Bool;
eq_edge: (Edge, Edge) -> Bool;
edge_info_of: Edge -> Edge_Info;
graph_info_of: Graph -> Graph_Info;
node_info_of: Node -> Node_Info;
}; # api Graphtree
## COPYRIGHT (c) 1994 AT&T Bell Laboratories.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.