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 - 2018
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 set) |
generic-function |
RETURN: The number of elements in the SET. NOTE: We only consider finite sets.
|
(contains-element self anelement) |
generic-function |
RETURN: Whether this set contains anElement.
|
(copy set &key &allow-other-keys) |
generic-function |
RETURN: A new set of same class as SET, containing the same
elements as SET.
|
(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 mapper set) |
generic-function |
DO: Calls MAPPER on each element of the SET in turn (no
specified order), collecting the results in a set of
type RESULT-TYPE.
RESULT-TYPE: A symbol denoting a set class, or LIST or VECTOR.
MAPPER: A function taking an element of SET as argument, and
returning an element for the set of type RESULT-TYPE.
SET: A set.
RETURN: A set of type RESULT-TYPE containing the elements
returned by MAPPER.
|
(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