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

( add-edge self newedge) |
generic-function |

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) |
generic-function |

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) |
generic-function |

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) |
generic-function |

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

( add-node self newnode) |
generic-function |

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

( add-nodes self newnodelist) |
generic-function |

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

( adjacent-nodes self node) |
generic-function |

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) |
generic-function |

RETURN: The number of elements in this set.

( contains-element self anelement) |
generic-function |

RETURN: Whether this set contains anElement.

( copy self &key &allow-other-keys) |
generic-function |

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) |
generic-function |

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

( description self) |
generic-function |

RETURN: A string describing this element.

directed-edge-class |
class |

An directed edge.

Class precedence list:DIRECTED-EDGE-CLASS EDGE-CLASS ELEMENT-CLASS STANDARD-OBJECT T

Class init args:PROPERTIES TAG FROM TO

( directed-edges-between-nodes self fromnode tonode) |
generic-function |

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

( directed-edges-from-node self fromnode) |
generic-function |

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

edge-class |
class |

An abstract edge.

Class precedence list:EDGE-CLASS ELEMENT-CLASS STANDARD-OBJECT T

Class init args:PROPERTIES TAG

( edge-class graph) |
generic-function |

The class of edges of the graph.

( edges graph) |
generic-function |

The edges of the graph.

( edges-between-nodes self nodea nodeb) |
generic-function |

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-class |
class |

An element of a SET-CLASS.

Class precedence list:ELEMENT-CLASS STANDARD-OBJECT T

Class init args:PROPERTIES

( element-list self) |
generic-function |

RETURN: A new list of the elements in self.

( elements set) |
generic-function |

The elements in the set.

( find-elements-with-property self property value) |
generic-function |

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

( find-nodes-with-property self property value) |
generic-function |

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

( flow-distance-from-node self startnode prop-name) |
generic-function |

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.

( from edge) |
generic-function |

The `from' node of this edge.

( get-property self prop-name) |
generic-function |

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

graph-class |
class |

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

Class precedence list:GRAPH-CLASS ELEMENT-CLASS STANDARD-OBJECT T

Class init args:PROPERTIES NODES EDGES EDGE-CLASS

hashed-set-class |
class |

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

Class precedence list:HASHED-SET-CLASS SET-CLASS ELEMENT-CLASS STANDARD-OBJECT T

Class init args:PROPERTIES ELEMENTS INDEX

( ident element) |
generic-function |

A unique symbol identifying this element.

( identical-nodes nodes-cons-a nodes-cons-b) |
function |

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

( index set) |
generic-function |

A hashtable used to index the elements in this set.

( is-between-nodes self nodea nodeb) |
generic-function |

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 result-type self lambda-body) |
generic-function |

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

( nodes self) |
generic-function |

RETURN: A list of NODES. For a GRAPH, it would be the nodes of the graph. For an edge, it would be the two nodes of the edge in no specific order. (Subclasses implementing directed edges should add specific methods to get the `from' and the `to' NODES).

( perform-with-elements self lambda-body) |
generic-function |

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

( properties element) |
generic-function |

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

( property-names self) |
generic-function |

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

( remove-edge self oldedge) |
generic-function |

DO: Remove the `oldEdge' from this graph.

( remove-edges self edge-list) |
generic-function |

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

( remove-edges-between-nodes self nodea nodeb) |
generic-function |

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

( remove-element self oldelement) |
generic-function |

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) |
generic-function |

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

( remove-nodes self oldnodelist) |
generic-function |

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

( select-elements self select-lambda) |
generic-function |

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

set-class |
class |

A set of elements.

Class precedence list:SET-CLASS ELEMENT-CLASS STANDARD-OBJECT T

Class init args:PROPERTIES ELEMENTS

( set-nodes self newfrom newto) |
generic-function |

DO: set the NODES of this edge.

( set-property self prop-name prop-value) |
generic-function |

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

( set-weight self newweight) |
generic-function |

POST: (equal (weight self) newWeight)

( show-graph self) |
generic-function |

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

( subclass-of-edge-p item) |
function |

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

( successor-nodes self node) |
generic-function |

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) |
generic-function |

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))) )

( to edge) |
generic-function |

The `to' node of this edge.

undirected-edge-class |
class |

An undirected edge.

Class precedence list:UNDIRECTED-EDGE-CLASS EDGE-CLASS ELEMENT-CLASS STANDARD-OBJECT T

Class init args:PROPERTIES TAG NODES

( walk-edges-from-node self startnode lambda-body) |
generic-function |

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) |
generic-function |

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

( weight edge) |
generic-function |

The weight of the edge.

weight-mixin-class |
class |

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

Class precedence list:WEIGHT-MIXIN-CLASS STANDARD-OBJECT T

Class init args:WEIGHT

weighted-directed-edge-class |
class |

A weighted, directed edge.

Class precedence list:WEIGHTED-DIRECTED-EDGE-CLASS DIRECTED-EDGE-CLASS EDGE-CLASS ELEMENT-CLASS WEIGHT-MIXIN-CLASS STANDARD-OBJECT T

Class init args:WEIGHT PROPERTIES TAG FROM TO

weighted-undirected-edge-class |
class |

A weighted, undirected edge.

Class precedence list:WEIGHTED-UNDIRECTED-EDGE-CLASS UNDIRECTED-EDGE-CLASS EDGE-CLASS ELEMENT-CLASS WEIGHT-MIXIN-CLASS STANDARD-OBJECT T

Class init args:WEIGHT PROPERTIES TAG NODES