Here is an example to illustrate how the GenSet language and processor can be used to perform simple graph manipulations. Suppose we have a rather cluttered graph (e.g., of method or procedure calls in a software system), and wish to clean it up by removing edges that can be inferred from transitivity. We'll use a very simple graph to illustrate.
In this example, there is an edge from a to b, an edge from b to e, and an edge from a to e. We wish to remove the edge from a to e because a path from a to e through b already exists. The edge from a to j should likewise be removed. We write the following GenSet program for this purpose:
/* Convert the "Calls" edges to a set-valued attribute */
edges->attrib Calls;
/* Calculate the transitive closure, excluding direct calls */
attribute { n| Calls[n->this] } TransitiveCalls =
/union { m| Calls[this->m] } .
Calls(m) union TransitiveCalls(m);
/* Remove the transitive calls */
attribute { n | Calls[n->this] } NonTransitive =
Calls(this) exclude TransitiveCalls(this);
/* Convert the resulting attribute back into graph edges */
attrib->edges NonTransitive;
The result* is:
*The result actually contains both the original "Calls" edges and the newly computed "NonTransitive" edges; we used a separate utility to remove the former.
[Up to "Exchanging Attributed Graphs] [Up to "Perpetual Testing at U. Oregon"]
Contact: Michal Young
