Graph traversal

The higher-order function tclose traverses a graphs of nodes using a functional neighbors(n) that returns the neighbor of a node n. Similarly the function traverse walks over a tree based on a functional ´children(n)´ applied on nodes n in the tree.

Transitive closures

The function tclose(Function fno,Object n)- Bag of Object computes the transitive closure of a graph starting at node n. It traverses the grapph and returns the set of visited nodes until all nodes reachable from n have been visited. During the traversal, it uses the transition function fno to obtain neighbors of nodes in the graph. A graph may contain loops and therefore tclose() will remember what nodes it has visited earlier and stop further traversals for nodes already visited.

The result type of a transition function fno(Object n)->Bag of Object is a bag of the neighbors of node n. The result must be a bag of argument types. Such a function that has the same argument and bag of result types is called a closed function.

Example: Assume the following definition of a circular graph defined by the transition function arcsto():

create function arcsto(Integer node)-> Bag of Integer
  as stored

Let's build a small circular graph:

set arcsto(1) = (values 2,3);
set arcsto(2) = (values 4,5);
set arcsto(5) = 1

The following computes the transitive closure of the graph starting in node 1:

tclose(#'arcsto', 1)

You can also query the inverse of tclose(), i.e. from which nodes f can be reached.

Example:

select f
  from Integer f
 where 1 in tclose(#'arcsto',f)

A transition function may also have one or two extra arguments and results, as long as the function is closed. This allows to pass extra parameters to a transitive closure computation.

Eexample: To compute not only the transitive closure, but also the distance from the start node of each visited graph node, use the following closed transition function:

create function arcstod(Integer node, Integer d) -> Bag of (Integer,Integer)
  as select arcsto(node),1+d

tclose(#'arcstod',1,0)

note

Only the first argument and result in the transition function define graph nodes, while the remaining arguments and results are extra parameters for passing information through the traversal, as with arcstod(). There may be no more than two such extra parameters in a transition function.

Traversing trees

If you know that the graph to traverse is a tree or a directed acyclic graph (DAG) you can instead use function traverse(Function fno, Object n) -> Bag of Object.

As for tclose(), the children in the tree to traverse is defined by the transition function fno. The tree is traversed in pre-order depth first starting at node n. Leaf nodes in the tree are nodes for which fno return no result. The function traverse() will not terminate if the graph is circular. Nodes are visited more than once for acyclic graphs having common subtrees.

Iterated traversal

The function iterate() applies a function fn() repeatedly.

Signature:

   iterate(Function fn, Number maxdepth, Object x) -> Object r

The iteration is initialized by setting x₀=x. Then

x_i+1= fn(x_i) is repeatedly computed until one of the following conditions hold: 1. there is no change (x_i = x_i+1), or 2. `fn()` returns nil (x_i+1 =nil), or 3. an upper limit `maxdepth` of the number of iterations is reached forx_i.

The function iterate() is overloaded and accepts an extra parameter p passed into $fn(x_i,p)$ or in the iterations.

Signature:

iterate(Function fn, Number maxdepth, Object x, Object p) -> Object r

This enables termination of the iteration since fn(x,p) can return nil based on both x and p.

Functions

Transitive closure functions

High-order functions