Common Lisp Package: COM.INFORMATIMAGO.COMMON-LISP.CESARUM.CONSTRAINTS

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 - 2012 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/>

README:

FUNCTION

Public

SOLVE-CONSTRAINTS (EDGES PROPAGATE)

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.

Private

BREADTH-FIRST-SEARCH-IF (GRAPH ROOT PREDICATE &KEY KEY)

DO: Implement the Breadth First Search algorithm on the given GRAPH, starting from the ROOT node, until the PREDICATE applied on the value of the KEY function applied to the node returns true. (Default for KEY is IDENTITY). RETURN: The goal node. COMPLEXITY: Time: O(|V|+|E|), Space: O(|V|)

CONDENSATE (GRAPH)

DO: Given a GRAPH, find the strongly connected components in the graph, and replace them with single nodes to obtain a DAG. RETURN: The DAG, and an a-list mapping new names (uninterned symbols) to strongly connected subgraphs.

DEPTH-FIRST-SEARCH-IF (GRAPH ROOT PREDICATE &KEY KEY)

DO: Implement the Depth First Search algorithm on the given GRAPH, starting from the ROOT node, until the PREDICATE applied on the value of the KEY function applied to the node returns true. (Default for KEY is IDENTITY). RETURN: The goal node. COMPLEXITY: Time: O(|V|+|E|), Space: O(|V|+|E|)

GRAPH-ADJACENCY-LIST (GRAPH NODE)

RETURN: The list of successors of NODE in the GRAPH.

GRAPH-NODES (GRAPH)

RETURN: The list of nodes in the GRAPH

NODE-INDEX (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-LABEL (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

TARJAN-STRONGLY-CONNECTED-COMPONENTS (GRAPH)

DO: Implement Tarjan's Strongly Connected Components Algorithm. RETURN: A set of strongly connected components = sets of nodes.

Undocumented

COPY-NODE (INSTANCE)

MAKE-GRAPH (EDGES)

MAKE-NODE (&KEY ((LABEL DUM154) NIL) ((INDEX DUM155) NIL) ((LOWLINK DUM156) NIL))

SETFNODE-INDEX (NEW-VALUE INSTANCE)

SETFNODE-LABEL (NEW-VALUE INSTANCE)

NODE-P (OBJECT)

VARIABLE

Private

Undocumented

*GERMANY*

CLASS

Private

Undocumented

NODE