/** * A generic algorithm for mapping a graph to a collection of nodes reachable * from a given root node. * * Basic idea: configuration of the form (todo, done, files), * keep adding files corresponding to the names in \verb|todo| until empty */ module strategy/pack/graph imports term/string collection/list/- rules GnInit : (root, graph, nodes) -> ([root], [root], graph, nodes, []) GnInitRoots : (roots, graph, nodes) -> (roots, roots, graph, nodes, []) GnNext(get-node, out-edges, add-node) : ([name | todo], done, graph, nodes, undef) -> (<conc> (todo', todo), <conc> (todo', done), graph, <add-node> (name, node, nodes), undef) where <get-node> (name, graph) => node; <out-edges> node => names; <diff> (names, done) => todo' GnNextChangeGraph(get-node, out-edges, add-node) : ([name | todo], done, graph, nodes, undef) -> (<conc> (todo', todo), <conc> (todo', done), graph', <add-node> (name, node, nodes), undef) where <get-node> (name, graph) => (node,graph'); <out-edges> node => names; <diff> (names, done) => todo' GnUndefined : ([name | todo], done, graph, nodes, undef) -> (todo, done, graph, nodes, [name | undef]) GnExit : ([], done, graph, nodes, undef) -> (nodes, undef) strategies graph-nodes-undef-roots(get-node, out-edges, add-node) = for(GnInitRoots, GnExit, GnNext(get-node, out-edges, add-node) <+ GnUndefined) graph-nodes-undef(get-node, out-edges, add-node) = for(GnInit, GnExit, GnNext(get-node, out-edges, add-node) <+ GnUndefined) graph-nodes-undef-roots-chgr(get-node, out-edges, add-node) = for(GnInitRoots, GnExit, GnNextChangeGraph(get-node, out-edges, add-node) <+ GnUndefined) graph-nodes-undef-chgr(get-node, out-edges, add-node) = for(GnInit, GnExit, GnNextChangeGraph(get-node, out-edges, add-node) <+ GnUndefined) /** * The strategy 'graph-nodes' is a generic * algorithm for mapping a graph to a collection of nodes reachable * from a given root node. The algorithm is parameterized with the * following notions: 'get-node' maps a node name and a graph to the * node itself, 'out-edges' maps a node to the names of its out * edges, 'add-node' that adds a name and its corresponding node to a * collection of nodes. * * get-node :: name * graph -> node * out-edges :: node -> List(name) * add-node :: name * node * nodes -> nodes */ graph-nodes(get-node, out-edges, add-node) = graph-nodes-undef(get-node, out-edges, add-node); \ (nodes, undef) -> nodes \ graph-nodes-roots(get-node, out-edges, add-node) = graph-nodes-undef-roots(get-node, out-edges, add-node); \ (nodes, undef) -> nodes \