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

This package exports classes for elements, sets and graphs. Graph class. This is a CLOS based implementation of graphs. It comes from an emacs/eieio implementation used to analyze CVS versioning graph. Subclasses exist to generate dot files, and Diagram! files. See also: License: AGPL3 Copyright Pascal J. Bourguignon 2003 - 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

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.