NTP is the node index type and GTP is the graph type
A collection of some very simple graph traversal algorithms
All the following routines assume that the graph is acyclic. They may go into an infinite loop or fail in some other way if the graph contains cycles. Usage:


Flattened version is here



is_topo_order(g: GTP,nodes: $ARR{NTP}): BOOL
**** Verify that the nodes in "node_order" are in topological order, that each node's order is greater than the order of any of its parents. Better methods probably exist...

bf!(once g: GTP,once n: NTP): NTP
**** Return all nodes reachable from "n" in breadth first order With inout arguments, also return the depth of the node
df!(once g: GTP,once n: NTP): NTP
**** Return all nodes reachable from "n" in depth first order
layer!(once g: GTP): SET{NTP}
**** Return the "layers" of the graph, i.e. peel off successive root sets Current indegree holds the current number of incoming per node When the number of incoming goes to zero, the node is visited and the current indegree values of all its outgoing are decremented. All nodes/edges start out live. Loop, at each iteration:
Until no more nodes are left alive
sink!(once g: GTP): NTP
**** Yield all sink nodes in the graph "g"
source!(once g: GTP): NTP
**** Yield all source nodes in the graph "g"
topo_order!(once g: GTP): NTP
**** Yield nodes in topological order

The Sather Home Page