## traitful-graphtree.api
#
# In
#
# src/lib/std/graphtree/graphtree.api#
# we define the base Graphtree interface, supporting
# directed graphs with application-specific information
# assocated with each graph, edge and node, plus a facility
# for constructing subgraphs, intended as a way to (for example)
# indicate particular regions of interest of the main graph.
#
# Here we extend that interface to support a dynamic string-driven
# approach to graphtrees in which graphs and nodes have string names
# and arbitrary string-named, string-valued "traits" may be attached
# to any graph, node or edge. We also maintain a dictionary of all
# sub/graphs in the graphtree, indexed by name.
#
# Our goal here is to support applications such as processing of
# .dot graph-description files, in which arbitrary property names
# and values unknown at compiletime may appear.
#
# The downside, of course, is that we give up much typesafety
# and become more like an interpreted than compiled system,
# gaining runtime flexibility at the cost of compiletime checking.
# For example we allow the functions
#
# get_trait
# set_trait
# drop_trait
# trait_apply
# count_trait
#
# to operate indifferently on graphs, edges, nodes, prototype edges
# and prototype nodes. (Edge and node prototypes hold the default
# traits to be attached to newly created edges and nodes.) Obviously,
# this buys brevity, convenience and generality at increased risk of
# coding errors not being caught at compiletime. No free lunch!
# Compiled by:
# src/lib/std/standard.lib# This api is implemented in:
# src/lib/std/graphtree/traitful-graphtree-g.pkg# This api gets 'include'-ed by:
# src/lib/std/dot/dot-graphtree.apiapi Traitful_Graphtree {
#
Traitful_Graph;
Node;
Edge;
Graph_Info;
Node_Info;
Edge_Info;
exception GRAPHTREE_ERROR String;
# Fold graphs, edges and nodes into a single type,
# so that our trait functions get_trait/set_trait/...
# can operate on any of them:
#
Graph_Part
#
= GRAPH_PART Traitful_Graph
| EDGE_PART Edge
| NODE_PART Node
| PROTONODE_PART Traitful_Graph # Holds default traits for newly created nodes.
| PROTOEDGE_PART Traitful_Graph # Holds default traits for newly created edges.
;
make_graph
:
{ name: String,
#
info: Null_Or( Graph_Info ),
#
make_default_graph_info: Void -> Graph_Info, # Function to initialize per-graph application-specific info.
make_default_node_info: Void -> Node_Info, # Function to initialize per-edge application-specific info.
make_default_edge_info: Void -> Edge_Info # Function to initialize per-node application-specific info.
}
->
Traitful_Graph;
graph_name: Traitful_Graph -> String;
node_name: Node -> String;
node_count: Traitful_Graph -> Int; # Number of nodes in graph. (O(1) op.)
edge_count: Traitful_Graph -> Int; # Number of edges in graph. (O(N) op.)
has_node: (Traitful_Graph, Node) -> Bool;
has_edge: (Traitful_Graph, Edge) -> Bool;
drop_node: (Traitful_Graph, Node) -> Void;
drop_edge: (Traitful_Graph, Edge) -> Void;
make_node: (Traitful_Graph, String, Null_Or(Node_Info) ) -> Node;
get_or_make_node: (Traitful_Graph, String, Null_Or(Node_Info) ) -> Node; # Return it if it exists, else call make_node.
find_node: (Traitful_Graph, String) -> Null_Or( Node );
nodes: Traitful_Graph -> List(Node);
nodes_apply: (Node -> Void) -> Traitful_Graph -> Void;
nodes_fold: ((Node, X) -> X) -> Traitful_Graph -> X -> X;
make_edge
:
{ graph: Traitful_Graph,
head: Node,
tail: Node,
info: Null_Or( Edge_Info )
}
->
Edge;
edges: Traitful_Graph -> List( Edge );
in_edges: (Traitful_Graph, Node) -> List(Edge);
out_edges: (Traitful_Graph, Node) -> List(Edge);
in_edges_apply: (Edge -> Void) -> (Traitful_Graph, Node) -> Void;
out_edges_apply: (Edge -> Void) -> (Traitful_Graph, Node) -> Void;
head: Edge -> Node;
tail: Edge -> Node;
nodes_of: Edge -> { head: Node,
tail: Node
};
make_subgraph: (Traitful_Graph, String, Null_Or(Graph_Info) ) -> Traitful_Graph ;
find_subgraph: (Traitful_Graph, String ) -> Null_Or(Traitful_Graph);
get_trait: Graph_Part -> String -> Null_Or(String);
set_trait: Graph_Part -> (String, String) -> Void;
drop_trait: Graph_Part -> String -> Void;
trait_apply: Graph_Part -> ((String, String) -> Void) -> Void;
count_trait: Graph_Part -> Int;
graph_info_of: Traitful_Graph -> Graph_Info;
edge_info_of: Edge -> Edge_Info;
node_info_of: Node -> Node_Info;
eq_graph: (Traitful_Graph, Traitful_Graph) -> Bool;
eq_node: (Node, Node ) -> Bool;
eq_edge: (Edge, Edge ) -> Bool;
}; # Traitful_Graphtree
## COPYRIGHT (c) 1994 AT&T Bell Laboratories.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.