/*
 * File:              acyclicTest.rex
 * Author:            Robert Keller
 * Purpose:           Describe acyclic-graph test
 * Secondary purpose: Show how to document rex code
 *
 * How to document rex code
 * Robert Keller
 * 30 January 2002
 * 
 * Because of the potency of typical functions in rex, it is easy to
 * under-document the code, by giving cryptic definitions of key functions.
 * Thus it is important to include two types of documentation with each 
 * function:
 *
 *    "what" documentation tells what the function does in the clearest
 *    possible terms.
 *
 *    "how" documentation tells how the particular implementation of the
 *    function does what it does, again as clearly as possible.
 *
 * Below we use the style of putting the "what" documentation before each
 * function definition and the "how" afterward.  This enables a casual user,
 * who is interested in the "what" but not the "how" to only read that portion.
 *
 * We also try to use identifiers for arguments that suggest that type of data
 * item being passed.
 *
 * In general (including outside this class) you should always have "what" 
 * documentation, even if you were to slight the "how".  This helps prevent
 * someone who reads your code from having to be a mind-reader as well.
 *
 * Also, remember that your code lines should no exceed 80 lines, so you
 * may have to make stylistic considerations so that your code looks good
 * even under this constraint.  It is a good idea to use plenty of whitespace
 * to prevent your code from looking crowded.
 *
 * Below we show some code documented in the preferred style.  This is 
 * for the acyclic graph test example that is discussed in the book and
 * which may be discussed in class.
 */

// isAcyclic(Graph) tells whether a graph, represented as a list of arcs,
// with each arc being a pair of nodes, is acyclic or not.  
// (Note that representation as a list of arcs assumes that every node is at
// one end or the other of some arc.  It does not provide for inclusion of 
// single nodes that are completely disconnected from the rest of the graph.)

isAcyclic(Graph) = null(iterate(removeLeaves, hasLeaf, Graph));

// if, and only if, the leafless graph is the empty list of arcs.


// hasLeaf(Graph) tells whether or not Graph has a leaf.

hasLeaf(Graph) = hasLeaf2(Graph, map(first, Graph));

hasLeaf2(Graph, Firsts) = some((Node)=>isLeaf(Node, Firsts), nodes(Graph));

// hasLeaf applies the function isLeaf to all nodes of the graph,
// determining whether it is true for some node.


// isLeaf(Node, Firsts) determines whether or not Node is a leaf of Graph
// having First as the list of all first nodes

isLeaf(Node, Firsts) = !member(Node, Firsts);

// A node is a leaf if it is not the first element of any arc of the graph.


// removeLeaves(Graph) returns a new graph with any leaves of the original
// graph, and the arcs leading to those leaves, removed.

removeLeaves(Graph) = removeLeaves2(Graph, map(first, Graph));

removeLeaves2(Graph, Firsts) = 
    drop(((Arc)=>isLeaf(second(Arc), Firsts)), Graph);

// removeLeaves drops arcs that are determined to lead to a leaf, by
// using isLeaf as the predicate argument to 'drop'.


// nodes(Graph) returns the list of nodes of a graph (without duplicates).

nodes(Graph) = 
    remove_duplicates(append(map(first, Graph), map(second, Graph)));

// Since it assumed that every node appears in some arc, this function
// simply collects all nodes that either begin or end an arc, then
// removes any duplicates.


// Note: Efficiency improvements are possible, to reduce the recomputation
// of some items, such as the list of nodes.  Introducing these optimizations
// may make the functions less clear, so for now they are left as is.


// Iterate(action, continue, State) returns action(action(...action(State)))
// where the number of actions is the least number such that continue is false.

iterate(action, continue, State) = 
    continue(State) ? iterate(action, continue, action(State)) : State;

// iterate uses recursion.  If continue(State) is true, it continues by
// iterating starting from action(State).  If not, it returns State.


// Below are test cases.

graph1 = [ [3, 4], [2, 3], [1, 2] ];                                 // acyclic

graph2 = [ [3, 4], [2, 3], [4, 2] ];                                 // cyclic

graph3 = [ [1, 2], [2, 3], [2, 4], [4, 5], [6, 3], [4, 6], [5, 6] ]; // acyclic

graph4 = [ [1, 2], [2, 3], [2, 4], [4, 5], [6, 3], [6, 4], [5, 6] ]; // cyclic

graph5 = [ [1, 1] ];                                                 // cyclic

graph6 = [ [1, 2], [1, 3], [1, 4], [4, 5], [3, 5], [2, 5], [1, 5] ]; // acyclic


// The built-in test function will check the actual outcomes against the
// desired ones and report whether or not there is a discrepancy.

test(isAcyclic(graph1), 1);
test(isAcyclic(graph2), 0);
test(isAcyclic(graph3), 1);
test(isAcyclic(graph4), 0);
test(isAcyclic(graph5), 0);
test(isAcyclic(graph6), 1);


/* test output:
ok: isAcyclic([[3, 4], [2, 3], [1, 2]]) ==> 1
ok: isAcyclic([[3, 4], [2, 3], [4, 2]]) ==> 0
ok: isAcyclic([[1, 2], [2, 3], [2, 4], [4, 5], [6, 3], [4, 6], [5, 6]]) ==> 1
ok: isAcyclic([[1, 2], [2, 3], [2, 4], [4, 5], [6, 3], [6, 4], [5, 6]]) ==> 0
ok: isAcyclic([[1, 1]]) ==> 0
ok: isAcyclic([[1, 2], [1, 3], [1, 4], [4, 5], [3, 5], [2, 5], [1, 5]]) ==> 1
*/