partial class UGRAPH_INCL{NTP} < $UGRAPH{NTP}
Partial class used to define useful routines in undirected graphs that are based on a core set of (undefined) routines The core routines must be defined by a particular implementation upon inclusion

Flattened version is here




stub add_node(n: NTP);
stub add_node(n: NTP):NTP;
stub add_node: NTP;
adjacent(n: NTP): SET{NTP}
are_connected(n1,n2: NTP): BOOL
**** Return true if there exists a path from n1 to n2
stub connect(n1,n2: NTP);
connect(e: UEDGE{NTP})
stub copy: SAME;
stub create: SAME;
**** Some of the routines need to create a "fresh" graph.
stub delete_node(n: NTP);
**** Delete all reflexive edges from the graph
dfs_apply(n: NTP,wk:ROUT{NTP})
**** Apply the pre visit work "wk" to nodes in df order. Non recursive
dfs_apply(n: NTP,prewk:ROUT{NTP},postwk:ROUT{UEDGE{NTP}})
**** Perform pre work before visiting a node and perform postwk on the way back up each edge Recursive version of dfs (much simpler to code) Here postwork is applied to *all* edges, including back edges
difference(g:$UGRAPH{NTP}): $UGRAPH{NTP}
stub disconnect(n1,n2: NTP);
disconnect(e: UEDGE{NTP})
edges: SET{UEDGE{NTP}}
equals(g: $RO_UGRAPH{NTP}): BOOL
**** Check that nodes and edges are the same Very inefficient n^2 version - sort for nlogn version
has(n: NTP): BOOL
has_edge(first,second: NTP): BOOL
has_edge(e: UEDGE{NTP}):BOOL
has_node(n: NTP): BOOL
has_same_nodes(g: $RO_UGRAPH{NTP}): BOOL
induced_subgraph(v: $SET{NTP}): $UGRAPH{NTP}
**** Generate a subgraph which is induced by the edges "v".
is_empty: BOOL
n_adjacent(n: NTP): INT
n_edges: INT
n_nodes: INT
n_reachable_from(n: NTP): INT
node_depths(n: NTP,map:$MAP{NTP,INT})
**** map should be inout, but this will work for now Do a bfs and return depths of each node
nodes: SET{NTP}
reachable_from(n: NTP): SET{NTP}
**** Returns the set of nodes reachable from "n"
roots: SET{NTP}
**** Returns a list of "representative" nodes from which the whole graph is reachable. With inout args, also return a mapping from nodes to the appropriate representative nodes (i.e. seen)
size: INT
str(f: ROUT{NTP}:STR): STR
**** Print out the graph using the bound routine "f" for the nodes
str: STR
to_difference(g: $UGRAPH{NTP})
**** Convert the graph to it's transitive closure For a non-destructive version, first make a copy
to_union(g: $UGRAPH{NTP})
union(g: $UGRAPH{NTP}): $UGRAPH{NTP}

stub adjacent!(once n: NTP): NTP;
bfs!(once n: NTP): NTP
**** Return all nodes reachable from "n" in bf order
dfs!(once n: NTP): NTP
**** Return all nodes reachable from "n" in df order
edge!: UEDGE{NTP}
elt!: NTP
**** Return a set of edge tuples that are true for test "et"
**** Return the set of all nodes in g that satisfy the node test "nt"
stub node!: NTP;
reachable_from!(once n: NTP): NTP
**** Returns successive nodes reachable from "n" using dfs


**** Recursive depth first search, when both pre and postwork must be done. Seen holds the list of nodes already seen
node_str(n: NTP): STR

The Sather Home Page