# 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 (GRAPH ROOT GOAL &KEY (TEST 'EQL) KEY)

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

# 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 (GRAPH ROOT GOAL &KEY (TEST 'EQL) KEY)

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

# 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.

# NODE-LOWLINK (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.