# FUNCTION

# Public

# IDENTICAL-NODES (NODES-CONS-A NODES-CONS-B)

RETURN: Whether NODES-cons-a and NODES-cons-b contain the same NODES.

# NODE-CONS-P (ITEM)

RETURN: Whether `item' is a cons of two objects kind of ELEMENT-CLASS.

# SUBCLASS-OF-EDGE-P (ITEM)

RETURN: Whether `item' is a subclass of EDGE-CLASS (not EDGE-CLASS itself).

# MACRO

# Private

# WHILE (CONDITION &BODY BODY)

While loop.

# GENERIC-FUNCTION

# Public

# ADD-EDGE (SELF NEWEDGE)

PRE: (and (CONTAINS-ELEMENT (NODES self) (nth 0 (NODES newEdge)))
(CONTAINS-ELEMENT (NODES self) (nth 1 (NODES newEdge))))
DO: Add a new edge to this graph.

# ADD-EDGE-BETWEEN-NODES (SELF NODEA NODEB)

DO: Create a new edge (of class edge-class) between `nodeA' and `nodeB'.
and add it to this graph.
If the edge is directed,
then `nodeA' is the `from' node and `nodeB' the `to' node.

# ADD-ELEMENT (SELF NEWELEMENT)

PRE: already_in = (CONTAINS-ELEMENT self newElement),
old_CARDINAL = (CARDINAL self)
POST: already_in ==> (CARDINAL self) == old_CARDINAL
(not already_in) ==> (CARDINAL self) == (1+ old_CARDINAL)
(CONTAINS-ELEMENT self newElement)

# ADD-ELEMENTS (SELF NEWELEMENTLIST)

DO: Add each element of the newElementList to this set.

# ADD-NODE (SELF NEWNODE)

DO: Add newNode to the set of NODES of this graph.

# ADD-NODES (SELF NEWNODELIST)

DO: Add a list of new NODES to the set of NODES of this graph.

# ADJACENT-NODES (SELF NODE)

RETURN: The list of NODES adjacent to the given node in this graph.
NOTE: For directed graphs, an adjacent node is either a predecessor
or a successors of the node.

# CARDINAL (SELF)

RETURN: The number of elements in this set.

# CONTAINS-ELEMENT (SELF ANELEMENT)

RETURN: Whether this set contains anElement.

# COPY (SELF &KEY (COPY-EDGES T) (COPY-NODES NIL) &ALLOW-OTHER-KEYS)

RETURN: A COPY of this edge.
The COPY has the same NODES than this edge.
Other attributes are normally copied.

# DELETE-PROPERTY (SELF PROP-NAME)

DO: Remove the property named `prop-name' from the property list of
this element.

# DESCRIPTION (SELF)

RETURN: A string describing this element.

# DIRECTED-EDGES-BETWEEN-NODES (SELF FROMNODE TONODE)

RETURN: A list of edges existing from the `fromNode' and to the `toNode'.

# DIRECTED-EDGES-FROM-NODE (SELF FROMNODE)

PRE: edge-class is-subclass-of DIRECTED-EDGE-CLASS
or edge-class eq DIRECTED-EDGE-CLASS.
RETURN: A list of edges existing from the `fromNode'.

# EDGES-BETWEEN-NODES (SELF NODEA NODEB)

RETURN: A list of edges existing between the `nodeA' and `nodeB'.
If the graph is directed then `nodeA' corresponds to the from node
and `nodeB' corresponds to the to node.

# ELEMENT-LIST (SELF)

RETURN: A new list of the elements in self.

# FIND-ELEMENTS-WITH-PROPERTY (SELF PROPERTY VALUE)

RETURN: A list of elements that have as property PROPERTY the value VALUE.

# FIND-NODES-WITH-PROPERTY (SELF PROPERTY VALUE)

RETURN: A list of NODES that have as property PROPERTY the value VALUE.

# FLOW-DISTANCE-FROM-NODE (SELF STARTNODE PROP-NAME)

DO: Compute for each node in this graph the distance from the startNode,
and store it as a property named prop-name.
NOTE: If the graph is not connex, then some distances will be nil,
meaning infinity.

# GET-PROPERTY (SELF PROP-NAME)

RETURN: the property `prop-name' of this element.

# IS-BETWEEN-NODES (SELF NODEA NODEB)

RETURN: Whether this edge is between `nodeA' and `nodeB'.
If this edge is directed then `nodeA' is compared to the from node
and `nodeB' is compared to the to node,
otherwise, the node order is not important.

# MAP-ELEMENTS (SELF LAMBDA-BODY)

RETURN: the list of results returned by lambda-body called with each element.
NOTE: lambda-body must not change this set.

# PERFORM-WITH-ELEMENTS (SELF LAMBDA-BODY)

DO: calls lambda-body with each element in the set.
NOTE: lambda-body must not change this set.

# PROPERTY-NAMES (SELF)

RETURN: The list of property names (keys) of properties of this element.

# REMOVE-EDGE (SELF OLDEDGE)

DO: Remove the `oldEdge' from this graph.

# REMOVE-EDGES (SELF EDGE-LIST)

DO: Remove all the edges in edge-list from this graph.

# REMOVE-EDGES-BETWEEN-NODES (SELF NODEA NODEB)

DO: Remove all edges between `nodeA' and `nodeB'.

# REMOVE-ELEMENT (SELF OLDELEMENT)

PRE: already_in = (CONTAINS-ELEMENT self newElement),
old_CARDINAL = (CARDINAL self)
POST: already_in ==> (CARDINAL self) == (1- old_CARDINAL),
(not (CONTAINS-ELEMENT self oldElement))
(not already_in) ==> (CARDINAL self) == old_CARDINAL

# REMOVE-NODE (SELF OLDNODE)

DO: Remove the oldNode from the graph.
This implies removing all the edges adjacent to the node too.

# REMOVE-NODES (SELF OLDNODELIST)

DO: Remove all the NODES of the oldNodeList from this graph.

# SELECT-ELEMENTS (SELF SELECT-LAMBDA)

RETURN: A list of elements for which select-lambda returned true.

# SET-NODES (SELF NEWFROM NEWTO)

DO: set the NODES of this edge.

# SET-PROPERTY (SELF PROP-NAME PROP-VALUE)

POST: (eql (GET-PROPERTY self prop-name) prop-value)

# SET-WEIGHT (SELF NEWWEIGHT)

POST: (equal (weight self) newWeight)

# SHOW-GRAPH (SELF)

DO: Prints a description of the graph on the *STANDARD-OUTPUT*.

# SUCCESSOR-NODES (SELF NODE)

RETURN: The list of successors NODES of the given node in this graph.
NOTE: For undirected graphs, it's the same as ADJACENT-NODES.

# SUCCESSOR-OF (SELF NODE)

RETURN: If node is a node of the edge, then return its successor or nil.
That is, for an undirected edge e,
(and (eq (SUCCESSOR-OF e (car (NODES e))) (cdr (NODES e)))
(eq (SUCCESSOR-OF e (cdr (NODES e))) (car (NODES e))) )
while for a directed edge d:
(xor (eq (SUCCESSOR-OF e (car (NODES e))) (cdr (NODES e)))
(eq (SUCCESSOR-OF e (cdr (NODES e))) (car (NODES e))) )

# WALK-EDGES-FROM-NODE (SELF STARTNODE LAMBDA-BODY)

DO: Walk the graph starting form startNode, calling lambda-body
with each edges as argument. Since it's the edges that are passed
to lambda-body, one node can be "walked" several times either as
`from' or `to' node or different edges.

# WALK-FROM-NODE (SELF STARTNODE LAMBDA-BODY)

DO: Walk the graph starting form startNode, calling lambda-body
with each node as argument.

# SLOT-ACCESSOR

# Public

# EDGE-CLASS (GRAPH)

The The class of edges of the graph.

# SETFEDGE-CLASS (NEW-VALUE OBJECT)

Set the The class of edges of the graph.

# EDGES (GRAPH)

The The edges of the graph.

# SETFEDGES (NEW-VALUE OBJECT)

Set the The edges of the graph.

# ELEMENTS (SET)

The The elements in the set.

# SETFELEMENTS (NEW-VALUE OBJECT)

Set the The elements in the set.

# FROM (EDGE)

The The `from' node of this edge.

# SETFFROM (NEW-VALUE OBJECT)

Set the The `from' node of this edge.

# IDENT (ELEMENT)

The A unique symbol identifying this element.

# INDEX (SET)

The A hashtable used to index the elements in this set.

# SETFINDEX (NEW-VALUE OBJECT)

Set the A hashtable used to index the elements in this set.

# NODES (GRAPH)

The The nodes of the graph.

# SETFNODES (NEW-VALUE OBJECT)

Set the The nodes of the graph.

# PROPERTIES (ELEMENT)

The A plist of properties for this elements.
It can be used to store markers while walking sets or graphs containing them.

# SETFPROPERTIES (NEW-VALUE OBJECT)

Set the A plist of properties for this elements.
It can be used to store markers while walking sets or graphs containing them.

# TO (EDGE)

The The `to' node of this edge.

# SETFTO (NEW-VALUE OBJECT)

Set the The `to' node of this edge.

# WEIGHT (EDGE)

The The weight of the edge.

# SETFWEIGHT (NEW-VALUE OBJECT)

Set the The weight of the edge.

# CLASS

# Public

# DIRECTED-EDGE-CLASS

An directed edge.

# EDGE-CLASS (GRAPH)

An abstract edge.

# ELEMENT-CLASS

An element of a SET-CLASS.

# GRAPH-CLASS

A graph of elements. By default, it's a undirected graph.

# HASHED-SET-CLASS

This is a specialized kind of set that maintains a hashtable
index of its elements to be able to retrieve them rapidly.

# SET-CLASS

A set of elements.

# UNDIRECTED-EDGE-CLASS

An undirected edge.

# WEIGHT-MIXIN-CLASS

This is a mixin for the subclasses of EDGE-CLASS
to add a weight to the edge.

# WEIGHTED-DIRECTED-EDGE-CLASS

A weighted, directed edge.

# WEIGHTED-UNDIRECTED-EDGE-CLASS

A weighted, undirected edge.