A little constraint solver.
Given a graph of nodes, and a propagate function that propagates
constraints from node to nodes, the solver propagates the constraints
until no change occurs.
It computes the strongly connected components, and performs a
topological sort of the condensed graph to minimalize the number of
calls to propagate.
License:
AGPL3
Copyright Pascal J. Bourguignon 2011 - 2015
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program.
If not, see <http://www.gnu.org/licenses/>
|
(solve-constraints edges propagate) |
function |
DO: Calls PROPAGATE on each edge until PROPAGATE returns NIL
for all arcs.
EDGES: A list of edges (from to).
The nodes FROM and EDGE must be comparable with EQL.
PROPAGATE: A function taking the nodes FROM and TO of an edge as argument,
and returning whether changes occured.