This is the cl-graph Reference Manual, version 0.10.2, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Dec 15 05:00:05 2024 GMT+0.
cl-graph/cl-graph.asdcl-graph/dev/package.lispcl-graph/dev/api.lispcl-graph/dev/macros.lispcl-graph/dev/graph.lispcl-graph/dev/graph-container.lispcl-graph/dev/graph-matrix.lispcl-graph/dev/graph-algorithms.lispcl-graph/dev/graphviz/graphviz-support.lispThe main system appears first, followed by any subsystem dependency.
cl-graphGraph manipulation utilities for Common Lisp
Gary Warren King <gwking@metabang.com>
Gary Warren King <gwking@metabang.com>
MIT Style License
0.10.2
metatilities-base (system)., at least version "0.6.0"
cl-containers (system)., at least version "0.12.0"
metabang-bind (system).
Modules are listed depth-first from the system components tree.
cl-graph/devcl-graph (system).
package.lisp (file).
api.lisp (file).
macros.lisp (file).
graph.lisp (file).
graph-container.lisp (file).
graph-matrix.lisp (file).
graph-algorithms.lisp (file).
notes.text (file).
graphviz (module).
cl-graph/dev/graphvizgraph.lisp (file).
dev (module).
graphviz-support.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
cl-graph/cl-graph.asdcl-graph/dev/package.lispcl-graph/dev/api.lispcl-graph/dev/macros.lispcl-graph/dev/graph.lispcl-graph/dev/graph-container.lispcl-graph/dev/graph-matrix.lispcl-graph/dev/graph-algorithms.lispcl-graph/dev/graphviz/graphviz-support.lispcl-graph/dev/api.lisppackage.lisp (file).
dev (module).
add-edge (generic function).
add-edge-between-vertexes (generic function).
add-vertex (generic function).
adjacentp (generic function).
any-undirected-cycle-p (generic function).
assortativity-coefficient (generic function).
child-vertexes (generic function).
connected-component-count (generic function).
connected-components (generic function).
connected-graph-p (generic function).
delete-all-edges (generic function).
delete-edge (generic function).
delete-edge-between-vertexes (generic function).
delete-vertex (generic function).
depth (generic function).
dfs (generic function).
dfs-back-edge-p (generic function).
dfs-edge-type (generic function).
dfs-tree-edge-p (generic function).
directed-edge-p (generic function).
dot-attribute-value (generic function).
(setf dot-attribute-value) (generic function).
edge->dot (generic function).
edge-count (generic function).
edge-lessp-by-direction (generic function).
edge-lessp-by-weight (generic function).
edges (generic function).
find-connected-components (generic function).
find-edge (generic function).
find-edge-between-vertexes (generic function).
find-edge-between-vertexes-if (generic function).
find-edge-if (generic function).
find-edges-if (generic function).
find-vertex (generic function).
find-vertex-if (generic function).
find-vertexes-if (generic function).
force-undirected (generic function).
generate-directed-free-tree (generic function).
graph->dot (generic function).
graph->dot-external (generic function).
graph->dot-properties (generic function).
graph-edge-mixture-matrix (generic function).
graph-mixing-matrix (generic function).
graph-roots (generic function).
has-children-p (generic function).
has-parent-p (generic function).
in-cycle-p (generic function).
in-undirected-cycle-p (generic function).
iterate-edges (generic function).
iterate-neighbors (generic function).
iterate-parents (generic function).
iterate-source-edges (generic function).
iterate-target-edges (generic function).
iterate-vertexes (generic function).
make-filtered-graph (generic function).
make-graph (generic function).
make-graph-from-vertexes (generic function).
make-vertex-edges-container (generic function).
make-vertex-for-graph (generic function).
minimum-spanning-tree (generic function).
neighbor-vertexes (generic function).
number-of-neighbors (generic function).
other-vertex (generic function).
out-edge-for-vertex-p (generic function).
parent-vertexes (generic function).
project-bipartite-graph (generic function).
renumber-edges (generic function).
renumber-vertexes (generic function).
replace-vertex (generic function).
rootp (generic function).
search-for-vertex (generic function).
source-edge-count (generic function).
source-edges (generic function).
source-vertex (generic function).
subgraph-containing (generic function).
tag-all-edges (generic function).
tagged-edge-p (generic function).
target-edge-count (generic function).
target-edges (generic function).
target-vertex (generic function).
topological-sort (generic function).
undirected-edge-p (generic function).
untag-all-edges (generic function).
untagged-edge-p (generic function).
vertex->dot (generic function).
vertex-count (generic function).
vertexes (generic function).
vertices-share-edge-p (generic function).
add-edge-to-vertex (generic function).
add-edges-to-graph (generic function).
assign-level (generic function).
breadth-first-search-graph (generic function).
breadth-first-visitor (generic function).
complete-links (generic function).
dfs-cross-edge-p (generic function).
dfs-forward-edge-p (generic function).
dfs-visit (generic function).
ensure-valid-dot-attribute (generic function).
generate-assortative-graph-with-degree-distributions (generic function).
generate-gnm (generic function).
generate-gnp (generic function).
generate-preferential-attachment-graph (generic function).
generate-scale-free-graph (generic function).
generate-simple-preferential-attachment-graph (generic function).
generate-undirected-graph-via-assortativity-matrix (generic function).
generate-undirected-graph-via-vertex-probabilities (generic function).
initialize-vertex-data (generic function).
make-edge-container (generic function).
make-edge-for-graph (generic function).
make-vertex-container (generic function).
map-over-all-combinations-of-k-edges (generic function).
map-over-all-combinations-of-k-vertexes (generic function).
mst-find-set (generic function).
mst-link (generic function).
mst-make-set (generic function).
mst-tree-union (generic function).
tag-edges (generic function).
traverse-elements (generic function).
traverse-elements-helper (generic function).
untag-edges (generic function).
write-name-for-dot (generic function).
cl-graph/dev/macros.lisppackage.lisp (file).
dev (module).
with-changing-vertex (macro).
cl-graph/dev/graph.lispapi.lisp (file).
macros.lisp (file).
dev (module).
add-edge (method).
add-edge-between-vertexes (method).
add-edge-between-vertexes (method).
add-vertex (method).
add-vertex (method).
add-vertex (method).
adjacentp (method).
adjacentp (method).
any-undirected-cycle-p (method).
basic-edge (class).
basic-graph (class).
basic-vertex (class).
child-vertexes (method).
color (reader method).
color (reader method).
(setf color) (writer method).
(setf color) (writer method).
container->list (method).
contains-directed-edge-p (reader method).
(setf contains-directed-edge-p) (writer method).
contains-undirected-edge-p (reader method).
(setf contains-undirected-edge-p) (writer method).
default-edge-class (reader method).
default-edge-type (reader method).
delete-all-edges (method).
delete-edge (method).
delete-edge-between-vertexes (method).
delete-vertex (method).
delete-vertex (method).
delete-vertex (method).
depth (method).
depth-level (reader method).
(setf depth-level) (writer method).
directed-edge-class (reader method).
directed-edge-mixin (class).
directed-edge-p (method).
discovery-time (reader method).
(setf discovery-time) (writer method).
edge (reader method).
edge-count (method).
edge-count (method).
edge-error (condition).
edge-id (reader method).
(setf edge-id) (writer method).
edges (method).
edges (method).
(setf element) (writer method).
element (reader method).
(setf element) (writer method).
(setf element) (method).
element (reader method).
empty! (method).
find-edge-between-vertexes (method).
find-edge-if (method).
find-edges-if (method).
find-vertex (method).
find-vertex (method).
find-vertex (method).
find-vertex-if (method).
find-vertex-if (method).
find-vertexes-if (method).
finish-time (reader method).
(setf finish-time) (writer method).
force-undirected (method).
generate-directed-free-tree (method).
get-transitive-closure (function).
graph (reader method).
graph (reader method).
graph (reader method).
(setf graph) (writer method).
graph-edge-not-found-error (condition).
graph-edges (reader method).
graph-error (condition).
graph-roots (method).
graph-vertex-not-found-error (condition).
graph-vertex-not-found-in-edge-error (condition).
graph-vertexes (reader method).
in-cycle-p (method).
in-cycle-p (method).
in-undirected-cycle-p (method).
initialize-instance (method).
initialize-instance (method).
initialize-instance (method).
insert-item (method).
iterate-elements (method).
iterate-nodes (method).
iterate-vertexes (method).
iterate-vertexes (method).
make-graph (method).
make-load-form (method).
make-load-form (method).
make-load-form (method).
make-vertex-for-graph (method).
map-paths (function).
map-shortest-paths (function).
neighbor-vertexes (method).
next-node (reader method).
(setf next-node) (writer method).
number-of-neighbors (method).
parent-vertexes (method).
previous-node (reader method).
(setf previous-node) (writer method).
print-object (method).
print-object (method).
print-object (method).
project-bipartite-graph (method).
project-bipartite-graph (method).
rank (reader method).
(setf rank) (writer method).
renumber-edges (method).
renumber-vertexes (method).
replace-vertex (method).
rootp (method).
search-for-vertex (method).
search-for-vertex (method).
size (method).
source-edge-count (method).
source-edges (method).
(setf tag) (writer method).
tag (reader method).
(setf tag) (writer method).
tag (reader method).
tag-all-edges (method).
tag-all-edges (method).
tagged-edge-p (method).
target-edge-count (method).
target-edges (method).
topological-sort (method).
undirected-edge-class (reader method).
undirected-edge-mixin (class).
undirected-edge-p (method).
untag-all-edges (method).
untag-all-edges (method).
untagged-edge-p (method).
vertex (reader method).
vertex (reader method).
vertex-1 (reader method).
vertex-2 (reader method).
vertex-class (reader method).
vertex-count (compiler macro).
vertex-count (method).
vertex-id (reader method).
vertexes (method).
weight (method).
(setf weight) (writer method).
weight (reader method).
weighted-edge-mixin (class).
add-edge-to-vertex (method).
append-unique (function).
assign-level (method).
assign-level (method).
edge-key (reader method).
edge-test (reader method).
get-nodelist-relatives (function).
graph-search-for-cl-graph (function).
largest-edge-id (reader method).
largest-vertex-id (reader method).
make-edge-for-graph (method).
neighbors-to-children (function).
remove-list (function).
tag-edges (method).
traverse-elements (method).
traverse-elements-helper (method).
traverse-elements-helper (method).
untag-edges (method).
value (reader method).
value (reader method).
(setf value) (writer method).
(setf value) (writer method).
vertex-key (reader method).
vertex-test (reader method).
cl-graph/dev/graph-container.lispgraph.lisp (file).
dev (module).
add-edge (method).
delete-all-edges (method).
delete-edge (method).
edge-count (method).
empty! (method).
find-edge (method).
find-edge-between-vertexes (method).
find-edge-between-vertexes-if (method).
find-edge-between-vertexes-if (method).
graph-container (class).
graph-container-directed-edge (class).
graph-container-edge (class).
graph-container-undirected-edge (class).
graph-container-vertex (class).
has-children-p (method).
has-parent-p (method).
initialize-instance (method).
initialize-instance (method).
iterate-children (method).
iterate-edges (method).
iterate-edges (method).
iterate-neighbors (method).
iterate-parents (method).
iterate-source-edges (method).
iterate-target-edges (method).
make-node-for-container (method).
make-vertex-edges-container (method).
other-vertex (method).
other-vertex (method).
print-object (method).
replace-vertex (method).
replace-vertex (method).
source-vertex (method).
target-vertex (method).
vertex-1 (reader method).
vertex-2 (reader method).
vertexes (method).
vertices-share-edge-p (method).
weighted-directed-edge (class).
weighted-edge (class).
weighted-undirected-edge (class).
add-edge-to-vertex (method).
associate-edge-with-pair (method).
associate-edge-with-pair (method).
dissoc-val-from-key-or-delete (function).
dissociate-edge-from-pair (method).
dissociate-edge-from-pair (method).
make-edge-container (method).
make-vertex-container (method).
vertex-edges (reader method).
vertex-pair->edge (reader method).
cl-graph/dev/graph-matrix.lispgraph.lisp (file).
dev (module).
graph-matrix (class).
graph-matrix-edge (class).
graph-matrix-vertex (class).
initialize-instance (method).
adjencency-matrix (reader method).
make-edge-container (method).
make-vertex-container (method).
cl-graph/dev/graph-algorithms.lispgraph.lisp (file).
dev (module).
connected-component-count (method).
connected-components (method).
connected-graph-p (method).
dfs (method).
dfs (method).
dfs-back-edge-p (method).
dfs-edge-type (method).
dfs-tree-edge-p (method).
edge-lessp-by-direction (method).
edge-lessp-by-weight (method).
find-connected-components (method).
minimum-spanning-tree (method).
out-edge-for-vertex-p (method).
rooted-dfs (generic function).
*depth-first-search-timer* (special variable).
add-edges-to-graph (method).
breadth-first-search-graph (method).
breadth-first-search-graph (method).
breadth-first-visitor (method).
breadth-first-visitor (method).
dfs-cross-edge-p (method).
dfs-forward-edge-p (method).
dfs-visit (method).
initialize-vertex-data (method).
make-vertex-datum (function).
map-over-all-combinations-of-k-edges (method).
map-over-all-combinations-of-k-edges (method).
map-over-all-combinations-of-k-vertexes (method).
mst-find-set (method).
mst-link (method).
mst-make-set (method).
mst-tree-union (method).
node-color (function).
(setf node-color) (function).
node-depth (function).
(setf node-depth) (function).
node-parent (function).
(setf node-parent) (function).
cl-graph/dev/graphviz/graphviz-support.lispgraphviz (module).
*dot-graph-attributes* (special variable).
dot-attribute-value (method).
(setf dot-attribute-value) (method).
(setf dot-attribute-value) (method).
dot-attributes (reader method).
(setf dot-attributes) (writer method).
dot-attributes-mixin (class).
dot-directed-edge (class).
dot-edge (class).
dot-edge-mixin (class).
dot-graph (class).
dot-graph-mixin (class).
dot-vertex (class).
dot-vertex-mixin (class).
edge->dot (method).
edge->dot (method).
graph->dot (method).
graph->dot (method).
graph->dot (method).
graph->dot (method).
graph->dot (method).
graph->dot-external (method).
graph->dot-properties (method).
graph->dot-properties (method).
height-in-pixels (method).
(setf height-in-pixels) (method).
print-dot-key-value (function).
vertex->dot (method).
vertex->dot (method).
width-in-pixels (method).
(setf width-in-pixels) (method).
*dot-edge-attributes* (special variable).
*dot-path* (special variable).
*dot-vertex-attributes* (special variable).
defpixel-inch-accessors (macro).
ensure-valid-dot-attribute (method).
ensure-valid-dot-attribute (method).
ensure-valid-dot-attribute (method).
format-dot-attributes (function).
textify (function).
write-name-for-dot (method).
write-name-for-dot (method).
Packages are listed by definition order.
cl-graphCL-Graph is a Common Lisp library for manipulating graphs and running graph algorithms.
metabang.graph
common-lisp.
metabang.bind.
metabang.cl-containers.
metabang.utilities.
*dot-graph-attributes* (special variable).
add-edge (generic function).
add-edge-between-vertexes (generic function).
add-vertex (generic function).
adjacentp (generic function).
any-undirected-cycle-p (generic function).
assortativity-coefficient (generic function).
basic-edge (class).
basic-graph (class).
basic-vertex (class).
child-vertexes (generic function).
color (generic reader).
(setf color) (generic writer).
connected-component-count (generic function).
connected-components (generic function).
connected-graph-p (generic function).
contains-directed-edge-p (generic reader).
(setf contains-directed-edge-p) (generic writer).
contains-undirected-edge-p (generic reader).
(setf contains-undirected-edge-p) (generic writer).
default-edge-class (generic reader).
default-edge-type (generic reader).
delete-all-edges (generic function).
delete-edge (generic function).
delete-edge-between-vertexes (generic function).
delete-vertex (generic function).
depth (generic function).
depth-level (generic reader).
(setf depth-level) (generic writer).
dfs (generic function).
dfs-back-edge-p (generic function).
dfs-edge-type (generic function).
dfs-tree-edge-p (generic function).
directed-edge-class (generic reader).
directed-edge-mixin (class).
directed-edge-p (generic function).
discovery-time (generic reader).
(setf discovery-time) (generic writer).
dot-attribute-value (generic function).
(setf dot-attribute-value) (generic function).
dot-attributes (generic reader).
(setf dot-attributes) (generic writer).
dot-attributes-mixin (class).
dot-directed-edge (class).
dot-edge (class).
dot-edge-mixin (class).
dot-graph (class).
dot-graph-mixin (class).
dot-vertex (class).
dot-vertex-mixin (class).
edge (generic reader).
edge->dot (generic function).
edge-count (generic function).
edge-error (condition).
edge-id (generic reader).
(setf edge-id) (generic writer).
edge-lessp-by-direction (generic function).
edge-lessp-by-weight (generic function).
edges (generic function).
find-connected-components (generic function).
find-edge (generic function).
find-edge-between-vertexes (generic function).
find-edge-between-vertexes-if (generic function).
find-edge-if (generic function).
find-edges-if (generic function).
find-vertex (generic function).
find-vertex-if (generic function).
find-vertexes-if (generic function).
finish-time (generic reader).
(setf finish-time) (generic writer).
force-undirected (generic function).
generate-directed-free-tree (generic function).
get-transitive-closure (function).
graph (generic reader).
(setf graph) (generic writer).
graph->dot (generic function).
graph->dot-external (generic function).
graph->dot-properties (generic function).
graph-container (class).
graph-container-directed-edge (class).
graph-container-edge (class).
graph-container-undirected-edge (class).
graph-container-vertex (class).
graph-edge-mixture-matrix (generic function).
graph-edge-not-found-error (condition).
graph-edges (generic reader).
graph-error (condition).
graph-matrix (class).
graph-matrix-edge (class).
graph-matrix-vertex (class).
graph-mixing-matrix (generic function).
graph-roots (generic function).
graph-vertex-not-found-error (condition).
graph-vertex-not-found-in-edge-error (condition).
graph-vertexes (generic reader).
has-children-p (generic function).
has-parent-p (generic function).
height-in-pixels (generic function).
(setf height-in-pixels) (generic function).
in-cycle-p (generic function).
in-undirected-cycle-p (generic function).
iterate-edges (generic function).
iterate-neighbors (generic function).
iterate-parents (generic function).
iterate-source-edges (generic function).
iterate-target-edges (generic function).
iterate-vertexes (generic function).
make-filtered-graph (generic function).
make-graph (generic function).
make-graph-from-vertexes (generic function).
make-vertex-edges-container (generic function).
make-vertex-for-graph (generic function).
map-paths (function).
map-shortest-paths (function).
minimum-spanning-tree (generic function).
neighbor-vertexes (generic function).
next-node (generic reader).
(setf next-node) (generic writer).
number-of-neighbors (generic function).
other-vertex (generic function).
out-edge-for-vertex-p (generic function).
parent-vertexes (generic function).
previous-node (generic reader).
(setf previous-node) (generic writer).
print-dot-key-value (function).
project-bipartite-graph (generic function).
rank (generic reader).
(setf rank) (generic writer).
renumber-edges (generic function).
renumber-vertexes (generic function).
replace-vertex (generic function).
rooted-dfs (generic function).
rootp (generic function).
search-for-vertex (generic function).
source-edge-count (generic function).
source-edges (generic function).
source-vertex (generic function).
subgraph-containing (generic function).
tag-all-edges (generic function).
tagged-edge-p (generic function).
target-edge-count (generic function).
target-edges (generic function).
target-vertex (generic function).
topological-sort (generic function).
undirected-edge-class (generic reader).
undirected-edge-mixin (class).
undirected-edge-p (generic function).
untag-all-edges (generic function).
untagged-edge-p (generic function).
vertex (generic reader).
vertex-1 (generic reader).
vertex-2 (generic reader).
vertex->dot (generic function).
vertex-class (generic reader).
vertex-count (compiler macro).
vertex-count (generic function).
vertex-id (generic reader).
vertexes (generic function).
vertices-share-edge-p (generic function).
weighted-directed-edge (class).
weighted-edge (class).
weighted-edge-mixin (class).
weighted-undirected-edge (class).
width-in-pixels (generic function).
(setf width-in-pixels) (generic function).
with-changing-vertex (macro).
*depth-first-search-timer* (special variable).
*dot-edge-attributes* (special variable).
*dot-path* (special variable).
*dot-vertex-attributes* (special variable).
add-edge-to-vertex (generic function).
add-edges-to-graph (generic function).
adjencency-matrix (generic reader).
append-unique (function).
assign-level (generic function).
associate-edge-with-pair (generic function).
breadth-first-search-graph (generic function).
breadth-first-visitor (generic function).
complete-links (generic function).
copy-vertex-datum (function).
defpixel-inch-accessors (macro).
dfs-cross-edge-p (generic function).
dfs-forward-edge-p (generic function).
dfs-visit (generic function).
dissoc-val-from-key-or-delete (function).
dissociate-edge-from-pair (generic function).
edge-key (generic reader).
edge-test (generic reader).
ensure-valid-dot-attribute (generic function).
format-dot-attributes (function).
generate-assortative-graph-with-degree-distributions (generic function).
generate-gnm (generic function).
generate-gnp (generic function).
generate-preferential-attachment-graph (generic function).
generate-scale-free-graph (generic function).
generate-simple-preferential-attachment-graph (generic function).
generate-undirected-graph-via-assortativity-matrix (generic function).
generate-undirected-graph-via-vertex-probabilities (generic function).
get-nodelist-relatives (function).
graph-search-for-cl-graph (function).
initialize-vertex-data (generic function).
largest-edge-id (generic reader).
largest-vertex-id (generic reader).
make-edge-container (generic function).
make-edge-for-graph (generic function).
make-vertex-container (generic function).
make-vertex-datum (function).
map-over-all-combinations-of-k-edges (generic function).
map-over-all-combinations-of-k-vertexes (generic function).
mst-find-set (generic function).
mst-link (generic function).
mst-make-set (generic function).
mst-tree-union (generic function).
neighbors-to-children (function).
node-color (function).
(setf node-color) (function).
node-depth (function).
(setf node-depth) (function).
node-parent (function).
(setf node-parent) (function).
remove-list (function).
tag-edges (generic function).
textify (function).
traverse-elements (generic function).
traverse-elements-helper (generic function).
untag-edges (generic function).
value (generic reader).
(setf value) (generic writer).
vertex-edges (generic reader).
vertex-key (generic reader).
vertex-pair->edge (generic reader).
vertex-test (generic reader).
write-name-for-dot (generic function).
Definitions are sorted by export status, category, package, and then by lexicographic order.
This is used to maintain consistency when changing the value of vertex elements while iterating over the vertexes...
Given a list of vertices, returns a combined list of all of the nodes in the transitive closure(s) of each of the vertices in the list (without duplicates). Optional DEPTH limits the depth (in _both_ the child and parent directions) to which the closure is gathered; default nil gathers the entire closure(s).
Apply fn to each path that starts at start-vertex and is of exactly length length
Apply fn to each shortest path starting at ‘start-vertex‘ of depth ‘depth‘. The ‘filter‘ predicate is used to remove vertexes from consideration.
Add-edge adds an existing edge to a graph. As add-edge-between-vertexes is generally more natural to use, this method is rarely called.
graph-container) (edge graph-container-edge) &key force-new?) ¶basic-graph) (edge basic-edge) &key force-new?) ¶Adds an edge between two vertexes and returns it.
If force-new? is true, the edge is added even if one already exists.
If the vertexes are not found in the graph, they will be added
(unless :error-if-not-found? is true). The class of the edge can be
specified using :edge-class or :edge-type. If :edge-type is used, it
can be either :directed or :undirected; the actual class of the edge
will be determined by using the edge-types of the graph. If
neither :edge-type nor :edge-class is specified, then a directed edge
will be created.
If-duplicate-do is used when the ’same’ edge is added more than
once. It can be either a function on one variable or :ignore
or :force. If it is :ignore, then the previously added edge is
returned; if it is :force, then another edge is added between the two
vertexes; if it is a function, then this function will be called with
the previous edge.
basic-graph) (v-1 basic-vertex) (v-2 basic-vertex) &rest args &key value if-duplicate-do edge-type edge-class &allow-other-keys) ¶basic-graph) value-1 value-2 &rest args &key if-duplicate-do &allow-other-keys) ¶Adds a vertex to a graph. If called with a vertex,
then this vertex is added. If called with a value, then a new vertex
is created to hold the value. If-duplicate-do can be one
of :ignore, :force, :replace, :replace-value, :error, or a function. The
default is :ignore.
basic-graph) (vertex basic-vertex) &key &allow-other-keys) ¶basic-graph) value &rest args &key if-duplicate-do &allow-other-keys) ¶basic-graph) (value basic-vertex) &key if-duplicate-do) ¶Return true if vertex-1 and vertex-2 are connected
by an edge. [?? compare with vertices-share-edge-p and remove one or
maybe call one directed-adjacentp]
basic-graph) (vertex-1 basic-vertex) (vertex-2 basic-vertex)) ¶basic-graph) vertex-1 vertex-2) ¶Returns true if there are any undirected cycles in ‘graph‘.
basic-graph)) ¶An assortative graph is one where vertexes of the
same type are more likely to have edges between them. The (discrete)
assortativity-coefficient measures how assortative a graph is based on
its mixing matrix. The definition we use is from Mixing Patterns in
Networks by Mark Newman. See the citation ’newman200-mixing’ in moab
or the URL ’http://arxiv.org/abs/cond-mat/0209450’.
Returns a list of the vertexes to which ‘vertex‘ is
connected by an edge and for which ‘vertex‘ is the source vertex. If
the connecting edge is undirected, then the vertex is always counted
as a source. [?? Could be a defun].
basic-edge)) ¶basic-edge)) ¶The ‘color‘ is used by some algorithms for bookkeeping. [?? Should probably be in a mixin]
basic-vertex)) ¶basic-vertex)) ¶The ‘color‘ slot is used by some algorithms for bookkeeping.
Returns the number of connected-components of graph.
basic-graph)) ¶Returns a union-find-container representing the connected-components of ‘graph‘.
basic-graph)) ¶Returns true if graph is a connected graph and nil otherwise.
basic-graph) &key edge-sorter) ¶basic-graph)) ¶basic-graph)) ¶Returns true if graph contains at least one directed edge. [?? Not sure if this is really kept up-to-date.]
basic-graph)) ¶basic-graph)) ¶Returns true if graph contains at least one undirected edge. [?? Not sure if this is really kept up-to-date.]
basic-graph)) ¶The default edge class for the graph.
basic-graph)) ¶The default edge type for the graph. This should be one of :undirected or :directed.
Delete all edges from ‘graph’. Returns the graph..
graph-container)) ¶basic-graph)) ¶Delete the ‘edge’ from the ‘graph’ and returns it.
graph-container) (edge graph-container-edge)) ¶basic-graph) (edge basic-edge)) ¶Finds an edge in the graph between the two
specified vertexes. If values (i.e., non-vertexes) are passed in,
then the graph will be searched for matching vertexes.
basic-graph) value-or-vertex-1 value-or-vertex-2 &rest args) ¶Remove a vertex from a graph. The ’vertex-or-value’
argument can be a vertex of the graph or a ’value’ that will find a
vertex via a call to find-vertex. A graph-vertex-not-found-error will
be raised if the vertex is not found or is not part of the graph.
basic-graph) (vertex basic-vertex)) ¶basic-graph) (vertex basic-vertex)) ¶basic-graph) value-or-vertex) ¶Returns the maximum depth of the vertexes in graph
assuming that the roots are of depth 0 and that each edge distance
from the roots increments the depth by one.
basic-graph)) ¶basic-vertex)) ¶basic-vertex)) ¶‘Depth-level‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
basic-graph) (root basic-vertex) fn &key out-edge-sorter) ¶basic-graph) root fn &key out-edge-sorter) ¶graph-container-edge)) ¶graph-container-edge)) ¶graph-container-edge)) ¶basic-graph)) ¶The class used to create directed edges in the graph. This must extend the base-class for edges of the graph type and directed-edge-mixin. E.g., the directed-edge-class of a graph-container must extend graph-container-edge and directed-edge-mixin.
Returns true if-and-only-if edge is directed
basic-edge)) ¶basic-vertex)) ¶basic-vertex)) ¶‘Discovery-time‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
symbol) (thing dot-attributes-mixin)) ¶symbol) (thing dot-attributes-mixin)) ¶symbol) (thing dot-attributes-mixin)) ¶dot-attributes-mixin)) ¶automatically generated reader method
dot-attributes-mixin)) ¶automatically generated writer method
edge-error)) ¶edge.
Used by graph->dot to output edge formatting for
‘edge‘ onto the ‘stream‘. The function can assume that openning and
closing square brackets and label have already been taken care
of.
dot-edge-mixin) stream) ¶basic-edge) (stream stream)) ¶Returns the number of edges attached to
‘vertex‘. Compare with the more flexible ‘vertex-degree‘.
graph-container)) ¶basic-vertex)) ¶basic-graph)) ¶basic-edge)) ¶basic-edge)) ¶The ‘edge-id‘ is used internally by CL-Graph for bookkeeping.
Returns true if and only if edge-1 is undirected and edge-2 is directed.
basic-edge) (e2 basic-edge)) ¶Returns true if the weight of edge-1 is strictly less than the weight of edge-2.
basic-edge) (e2 basic-edge)) ¶Returns a list of the edges of ‘thing‘.
basic-vertex)) ¶basic-graph)) ¶Returns a list of sub-graphs of ‘graph‘ where each
sub-graph is a different connected component of graph. Compare with
connected-components and connected-component-count.
basic-graph)) ¶Search ‘graph‘ for an edge whose vertexes match
‘edge‘. This means that ‘vertex-1‘ of the edge in the graph must
match ‘vertex-1‘ of ‘edge‘ and so forth. Wil signal an error of type
‘graph-edge-not-found-error‘ unless ‘error-if-not-found?‘ is
nil. [?? Unused. Remove?]
graph-container) (edge graph-container-edge) &optional error-if-not-found?) ¶Searches ‘graph‘ for an edge that connects vertex-1
and vertex-2. [?? Ignores error-if-not-found? Does directedness
matter? need test]
graph-container) (vertex-1 graph-container-vertex) (vertex-2 graph-container-vertex) &key error-if-not-found?) ¶basic-graph) value-1 value-2 &key error-if-not-found?) ¶Finds and returns an edge between value-or-vertex-1
and value-or-vertex-2 which returns true (as a generalized boolean) when
evaluated by ‘fn‘. Unless error-if-not-found? is nil, then a error will
be signaled. [?? IS error really signaled? need a test.]
graph-container) value-1 value-2 fn &key error-if-not-found?) ¶graph-container) (vertex-1 graph-container-vertex) (vertex-2 graph-container-vertex) fn &key error-if-not-found?) ¶Returns the first edge in ‘thing‘ for which the
‘predicate‘ function returns non-nil. If the ‘key‘ is supplied, then
it is applied to the edge before the predicate is.
basic-graph) fn &key key) ¶Returns a list of edges in ‘thing‘ for which the ‘predicate‘ returns non-nil. [?? why no key function?]
basic-graph) fn) ¶Search ’graph’ for a vertex with element
’value’. The search is fast but inflexible because it uses an
associative-container. If you need more flexibity, see
search-for-vertex.
basic-edge) value &optional error-if-not-found?) ¶basic-graph) (vertex basic-vertex) &optional error-if-not-found?) ¶basic-graph) value &optional error-if-not-found?) ¶Returns the first vertex in ‘thing‘ for which the
‘predicate‘ function returns non-nil. If the ‘key‘ is supplied, then
it is applied to the vertex before the predicate is.
basic-edge) fn &key key) ¶basic-graph) fn &key key) ¶Returns a list of vertexes in ‘thing‘ for which the ‘predicate‘ returns non-nil. [?? why no key function?]
basic-graph) fn) ¶basic-vertex)) ¶basic-vertex)) ¶‘Finish-time‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
Ensures that the graph is undirected (possibly by calling change-class on the edges).
basic-graph)) ¶Returns a version of graph which is a directed free tree rooted at root.
basic-graph) root) ¶basic-vertex)) ¶basic-vertex)) ¶The graph in which this vertex is contained.
basic-edge)) ¶The ‘graph‘ of which this edge is a part.
graph-error)) ¶Generates a description of ‘graph‘ in DOT file format. The
formatting can be altered using ‘graph->dot-properties,‘
‘vertex->dot,‘ and ‘edge->dot‘ as well as ‘edge-formatter,‘
‘vertex-formatter,‘ ‘vertex-labeler,‘ and ‘edge-labeler‘. These can
be specified directly in the call to ‘graph->dot‘ or by creating
subclasses of basic-graph, basic-vertex and basic-edge.
The output can be a stream or pathname or one of the values ‘nil‘ or
‘t‘. If output is ‘nil‘, then graph->dot returns a string containing
the DOT description. If it is ‘t‘, then the DOT description is written
to \*standard-output\*.
Here is an example;
(let ((g (make-container ’graph-container :default-edge-type :directed)))
(loop for (a b) in ’((a b) (b c) (b d) (d e) (e f) (d f)) do
(add-edge-between-vertexes g a b))
(graph->dot g nil))
"digraph G {
E []
C []
B []
A []
D []
F []
E->F []
B->C []
B->D []
A->B []
D->E []
D->F []
}"
For more information about DOT file format, search the web for ’DOTTY’ and ’GRAPHVIZ’.
basic-graph) (stream pathname) &rest args &key &allow-other-keys) ¶basic-graph) (stream string) &rest args &key &allow-other-keys) ¶basic-graph) (stream (eql t)) &rest args &key &allow-other-keys) ¶basic-graph) (stream (eql nil)) &rest args &key &allow-other-keys) ¶basic-graph) (stream stream) &key graph-formatter vertex-key vertex-labeler vertex-formatter edge-labeler edge-formatter &allow-other-keys) ¶basic-graph) file-name &rest args &key type &allow-other-keys) ¶Generate an external represenation of a graph to a file, by running the program in *dot-path*.
Unless a different graph-formatter is specified,
this method is called by graph->dot to output graph-properties onto
a stream. The function can assume that the openning and closing
brackets will be taken care of by the graph->dot.
dot-graph-mixin) stream) ¶Return the ‘mixing-matrix‘ of graph based on the
classifier and the edge-weight function. The mixing matrix is a
matrix whose runs and columns represent each class of vertex in the
graph. The entries of the matrix show the total number of edges
between vertexes of the two kinds. [?? Edge-weight is not used; also
compare with graph-mixture-matrix.]
basic-graph)) ¶automatically generated reader method
Return the ‘mixing-matrix‘ of graph based on the
classifier and the edge-weight function. The mixing matrix is a
matrix whose runs and columns represent each class of vertex in the
graph. The entries of the matrix show the total number of edges
between vertexes of the two kinds. [?? Edge-weight is not used; also
compare with graph-edge-mixture-matrix.]
Returns a list of the roots of graph. A root is
defined as a vertex with no source edges (i.e., all of the edges
are out-going). (cf. rootp) [?? could be a defun]
basic-graph)) ¶basic-graph)) ¶automatically generated reader method
In a directed graph, returns true if vertex has any
edges that point from vertex to some other
vertex (cf. iterate-source-edges). In an undirected graph,
‘has-children-p‘ is testing only whether or not the vertex has any
edges.
graph-container-vertex)) ¶In a directed graph, returns true if vertex has any
edges that point from some other vertex to this
vertex (cf. iterate-target-edges). In an undirected graph,
‘has-parent-p‘ is testing only whether or not the vertex has any
edges.
graph-container-vertex)) ¶dot-vertex-mixin)) ¶Return the attribute in pixels assuming 72 dpi
dot-vertex-mixin)) ¶Set the attribute in pixels assuming 72 dpi
Returns true if ‘start-vertex‘ is in some cycle in
‘graph‘. This uses child-vertexes to generate the vertexes adjacent
to a vertex.
basic-graph) (start-vertex basic-vertex)) ¶basic-graph) vertex) ¶Return true if-and-only-if an undirected cycle in graph is reachable from start-vertex.
basic-graph) (current basic-vertex) &optional marked previous) ¶Calls ‘fn‘ on each edge of graph or vertex.
graph-container-vertex) fn) ¶graph-container) fn) ¶Calls fn on every vertex adjecent to vertex See also iterate-children and iterate-parents.
graph-container-vertex) fn) ¶Calls fn on every vertex that is either connected
to vertex by an undirected edge or is at the source end of a
directed edge.
graph-container-vertex) fn) ¶In a directed graph, calls ‘fn‘ on each edge of a
vertex that begins at vertex. In an undirected graph, this is
equivalent to ‘iterate-edges‘.
graph-container-vertex) fn) ¶In a directed graph, calls ‘fn‘ on each edge of a
vertex that ends at vertex. In an undirected graph, this is
equivalent to ‘iterate-edges‘.
graph-container-vertex) fn) ¶Calls ‘fn‘ on each of the vertexes of ‘thing‘.
basic-edge) fn) ¶basic-graph) fn) ¶Takes a GRAPH and a TEST-FN (a single argument
function returning NIL or non-NIL), and filters the graph nodes
according to the test-fn (those that return non-NIL are accepted),
returning a new graph with only nodes corresponding to those in the
original graph that satisfy the test (the nodes in the new graph are
new, but their values and name point to the same contents of the
original graph). There are four options for how the new graph is
filled-out, depending on the following keywords passed to the optional
GRAPH-COMPLETION-METHOD argument:
* NIL (default)
New graph has only nodes that correspond to those in the original
graph that pass the test. NO LINKS are reproduced.
* :COMPLETE-LINKS
New graph has only nodes that pass, but reproduces corresponding
links between passing nodes in the original graph.
* :COMPLETE-CLOSURE-NODES-ONLY
New graph also includes nodes corresponding to the transitive
closure(s) that include the passign nodes in the original
graph. NO LINKS are reproduced.
* :COMPLETE-CLOSURE-WITH-LINKS
Same as above, except corresponding links are reproduced.
For both transitive closure options, an additional optional argument, DEPTH, specifies how many links away from a source vertex to travel in gathering vertexes of the closure. E.g., a depth of 1 returns the source vertex and the parents and children of that vertex (all vertexes one link away from the source). The default value is NIL, indicating that all vertexes are to be included, no matter their depth. This value is ignored in non closure options.
Create a new graph of type ‘graph-type’. Graph type
can be a symbol naming a sub-class of basic-graph or a list. If it is
a list of symbols naming different classes. If graph-type is a list,
then a class which has all of the listed classes as superclasses will
be found (or created). In either case, the new graph will be created
as if with a call to make-instance.
symbol) &rest args &key &allow-other-keys) ¶Create a new graph given a list of vertexes (which
are assumed to be from the same graph). The new graph contains all
of the vertexes in the list and all of the edges between any
vertexes on the list.
Called during the initialization of a vertex to
create the create the container used to store the edges incident to
the vertex. The initarg :vertex-edges-container-class can be used to
alter the default container class.
graph-container-vertex) container-class &rest args) ¶Creates a new vertex for graph ‘graph‘. The keyword
arguments include:
* vertex-class : specify the class of the vertex
* element : specify the ‘element‘ of the vertex
and any other initialization arguments that make sense for the vertex class.
basic-graph) &rest args &key vertex-class &allow-other-keys) ¶Returns a minimum spanning tree of graph if one exists and nil otherwise.
basic-graph) &key edge-sorter) ¶Returns a list of the vertexes to which ‘vertex‘ is
connected by an edge disregarding edge direction. In a directed
graph, neighbor-vertexes is the union of parent-vertexes and
child-vertexes. [?? Could be a defun].
basic-vertex)) ¶basic-vertex)) ¶‘Next-node‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
Returns the number of neighbors of
‘vertex‘ (cf. ‘neighbor-vertexes‘). [?? could be a defun]
Assuming that the value-or-vertex corresponds to
one of the vertexes for ‘edge‘, this method returns the other vertex
of ‘edge‘. If the value-or-vertex is not part of edge, then an error
is signaled. [?? Should create a new condition for this]
graph-container-edge) value) ¶graph-container-edge) (v graph-container-vertex)) ¶Returns true if the edge is connected to vertex and
is either an undirected edge or a directed edge for which vertex is
the source vertex of the edge.
basic-edge) (vertex basic-vertex)) ¶Returns a list of the vertexes to which ‘vertex‘ is
connected by an edge and for which ‘vertex‘ is the target vertex. If
the connecting edge is undirected, then the vertex is always counted
as a target. [?? Could be a defun].
basic-vertex)) ¶basic-vertex)) ¶‘Previous-node‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
Creates the unimodal bipartite projects of
existing-graph with vertexes for each vertex of existing graph whose
‘vertex-classifier‘ is eq to ‘vertex-class‘ and where an edge existing
between two vertexes of the graph if and only if they are connected to
a shared vertex in the existing-graph.
basic-graph) graph vertex-class vertex-classifier) ¶symbol) graph vertex-class vertex-classifier) ¶basic-vertex)) ¶basic-vertex)) ¶The ‘rank‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
rank.
Assign a number to each edge in a graph in some unspecified order. [?? internal]
basic-graph)) ¶Assign a number to each vertex in a graph in some unspecified order. [?? internal]
basic-graph)) ¶Replace vertex ‘old‘ in graph ‘graph‘ with vertex ‘new‘. The edge structure of the graph is maintained.
graph-container) (old basic-vertex) (new basic-vertex)) ¶graph-container) (old basic-vertex) (new basic-vertex)) ¶basic-graph) (old basic-vertex) (new basic-vertex)) ¶A variant of DFS that does not visit nodes that are unreachable from the ROOT.
basic-graph) root fn &key out-edge-sorter) ¶basic-graph) (root basic-vertex) fn &key out-edge-sorter) ¶Returns true if ‘vertex‘ is a root vertex (i.e., it has no incoming (source) edges).
basic-vertex)) ¶Search ’graph’ for a vertex with element
’value’. The ’key’ function is applied to each element before that
element is compared with the value. The comparison is done using the
function ’test’. If you don’t need to use key or test, then consider
using find-vertex instead.
basic-graph) vertex &key key test error-if-not-found?) ¶basic-graph) (vertex basic-vertex) &key key test error-if-not-found?) ¶Returns the number of source edges of
vertex (cf. source-edges). [?? could be a defun]
basic-vertex)) ¶Returns a list of the source edges of ‘vertex‘. I.e., the edges that begin at ‘vertex‘.
basic-vertex) &optional filter) ¶Returns the source-vertex of a directed edge. Compare with ‘vertex-1‘.
graph-container-edge)) ¶Returns a new graph that is a subset of ‘graph‘
that contains ‘vertex‘ and all of the other vertexes that can be
reached from vertex by paths of less than or equal of length ‘depth‘.
If depth is not specified, then the entire sub-graph reachable from
vertex will be returned. [?? Edge weights are always assumed to be
one.]
Sets the ‘tag‘ of all the edges of ‘thing‘ to true. [?? why does this exist?]
basic-vertex)) ¶basic-graph)) ¶Returns true if-and-only-if edge’s tag slot is t
basic-edge)) ¶Returns the number of target edges of
vertex (cf. target-edges). [?? could be a defun]
basic-vertex)) ¶Returns a list of the target edges of ‘vertex‘. I.e., the edges that end at ‘vertex‘.
basic-vertex) &optional filter) ¶Returns the target-vertex of a directed edge. Compare with ‘vertex-2‘.
graph-container-edge)) ¶Returns a list of vertexes sorted by the depth from
the roots of the graph. See also assign-level and graph-roots.
basic-graph)) ¶basic-graph)) ¶The class used to create undirected edges in the graph. This must extend the base-class for edges of the graph type and undirected-edge-mixin. E.g., all undirected edges of a graph-container must extend graph-container-edge and undirected-edge-mixin.
Returns true if-and-only-if edge is undirected
basic-edge)) ¶Sets the ‘tag‘ of all the edges of ‘thing‘ to nil. [?? why does this exist?]
basic-vertex)) ¶basic-graph)) ¶Returns true if-and-only-if edge’s tage slot is nil
basic-edge)) ¶graph-vertex-not-found-in-edge-error)) ¶graph-vertex-not-found-error)) ¶graph-container-edge)) ¶‘Vertex-1‘ is one of the two vertexes that an edge connects. In a directed-edge, ‘vertex-1‘ is also the ‘source-vertex‘.
graph-edge-not-found-error)) ¶graph-container-edge)) ¶‘Vertex-2‘ is one of the two vertexes that an edge connects. In a directed edge, ‘vertex-2‘ is also the ‘target-vertex‘.
graph-edge-not-found-error)) ¶Unless a different vertex-formatter is specified
with a keyword argument, this is used by graph->dot to output vertex
formatting for ‘vertex‘ onto the ‘stream‘. The function can assume
that openning and closing square brackets and label have already
been taken care of.
dot-vertex-mixin) stream) ¶basic-vertex) (stream stream)) ¶basic-graph)) ¶The class of the vertexes in the graph. This must extend the base-class for vertexes of the graph type. E.g., all vertexes of a graph-container must extend graph-container-vertex.
Returns the number of vertexes in ‘graph‘. [?? could be a defun]
basic-graph)) ¶basic-vertex)) ¶‘Vertex-id‘ is used internally to keep track of vertexes.
Returns a list of the vertexes of ‘thing‘.
graph-container-edge)) ¶basic-graph)) ¶Return true if vertex-1 and vertex-2 are connected by an edge. [?? Compare adjacentp]
dot-vertex-mixin)) ¶Return the attribute in pixels assuming 72 dpi
dot-vertex-mixin)) ¶Set the attribute in pixels assuming 72 dpi
basic-graph)) ¶metabang.cl-containers.
basic-edge)) ¶automatically generated writer method
metabang.utilities.
basic-edge)) ¶automatically generated reader method
metabang.utilities.
basic-vertex)) ¶metabang.utilities.
basic-vertex)) ¶The ‘element‘ is the value that this vertex represents.
metabang.utilities.
basic-vertex)) ¶The ‘element‘ is the value that this vertex represents.
metabang.utilities.
basic-graph)) ¶metabang.cl-containers.
graph-container)) ¶metabang.cl-containers.
basic-edge) &key graph edge-id) ¶basic-graph) &key initial-size &allow-other-keys) ¶graph-container-directed-edge) &key source-vertex target-vertex) ¶graph-container-vertex) &key vertex-edges-container-class) ¶graph-matrix) &key) ¶basic-vertex) &key graph vertex-id) ¶basic-graph) value) ¶metabang.cl-containers.
graph-container-vertex) fn) ¶metabang.cl-containers.
basic-graph) fn) ¶metabang.cl-containers.
basic-graph) fn) ¶metabang.cl-containers.
basic-edge) &optional environment) ¶basic-graph) &optional environment) ¶basic-vertex) &optional environment) ¶graph-container) node &key) ¶metabang.cl-containers.
basic-edge) stream) ¶basic-graph) stream) ¶basic-vertex) stream) ¶graph-container-edge) stream) ¶basic-graph)) ¶metabang.utilities.
basic-edge)) ¶The ‘tag‘ is used by some algorithms for bookkeeping. [?? Should probably be in a mixin]
metabang.utilities.
tag.
basic-edge)) ¶The ‘tag‘ is used by some algorithms for bookkeeping. [?? Should probably be in a mixin]
metabang.utilities.
tag.
basic-vertex)) ¶The ‘tag‘ slot is used by some algorithms to keep track of which vertexes have been visited.
metabang.utilities.
tag.
basic-vertex)) ¶The ‘tag‘ slot is used by some algorithms to keep track of which vertexes have been visited.
metabang.utilities.
tag.
basic-edge)) ¶metabang.cl-containers.
weighted-edge-mixin)) ¶The value of the weight of this edge. Defaults to 1.0d0
metabang.cl-containers.
weighted-edge-mixin)) ¶The value of the weight of this edge. Defaults to 1.0d0
metabang.cl-containers.
This is the root condition for graph errors that have to do with edges.
edge.
This condition is signaled when an edge cannot be found in a graph.
One of the vertexes for which no connecting edge could be found.
(quote nil)
:vertex-1
This slot is read-only.
This is the root condition for errors that occur while running code in CL-Graph.
error.
This condition is signaled when a vertex can not be found in a graph.
This condition is signaled when a vertex can not be found in an edge.
This is the root class for all edges in CL-Graph.
add-edge.
add-edge-to-vertex.
(setf color).
color.
delete-edge.
directed-edge-p.
edge->dot.
(setf edge-id).
edge-id.
edge-lessp-by-direction.
edge-lessp-by-weight.
(setf element).
element.
find-vertex.
find-vertex-if.
graph.
initialize-instance.
iterate-vertexes.
make-load-form.
out-edge-for-vertex-p.
print-object.
(setf tag).
tag.
tagged-edge-p.
undirected-edge-p.
untagged-edge-p.
(setf value).
value.
weight.
The ‘edge-id‘ is used internally by CL-Graph for bookkeeping.
0
:edge-id
metabang.utilities.
:element, :value
The ‘tag‘ is used by some algorithms for bookkeeping. [?? Should probably be in a mixin]
metabang.utilities.
:tag
tag.
The ‘graph‘ of which this edge is a part.
:graph
This slot is read-only.
The ‘color‘ is used by some algorithms for bookkeeping. [?? Should probably be in a mixin]
:color
This is the root class for all graphs in CL-Graph.
add-edge.
add-edge-between-vertexes.
add-edge-between-vertexes.
add-edges-to-graph.
add-vertex.
add-vertex.
add-vertex.
adjacentp.
adjacentp.
any-undirected-cycle-p.
assign-level.
breadth-first-search-graph.
breadth-first-search-graph.
breadth-first-visitor.
breadth-first-visitor.
connected-component-count.
connected-components.
connected-graph-p.
container->list.
(setf contains-directed-edge-p).
contains-directed-edge-p.
(setf contains-undirected-edge-p).
contains-undirected-edge-p.
default-edge-class.
default-edge-type.
delete-all-edges.
delete-edge.
delete-edge-between-vertexes.
delete-vertex.
delete-vertex.
delete-vertex.
depth.
dfs.
dfs.
directed-edge-class.
edge-count.
edge-key.
edge-test.
edges.
empty!.
find-connected-components.
find-edge-between-vertexes.
find-edge-if.
find-edges-if.
find-vertex.
find-vertex.
find-vertex-if.
find-vertexes-if.
force-undirected.
generate-directed-free-tree.
graph->dot.
graph->dot.
graph->dot.
graph->dot.
graph->dot.
graph->dot-external.
graph-edges.
graph-roots.
graph-vertexes.
in-cycle-p.
in-cycle-p.
in-undirected-cycle-p.
initialize-instance.
initialize-vertex-data.
insert-item.
iterate-elements.
iterate-nodes.
iterate-vertexes.
largest-edge-id.
largest-vertex-id.
make-edge-for-graph.
make-load-form.
make-vertex-for-graph.
map-over-all-combinations-of-k-edges.
map-over-all-combinations-of-k-vertexes.
minimum-spanning-tree.
print-object.
project-bipartite-graph.
renumber-edges.
renumber-vertexes.
replace-vertex.
rooted-dfs.
rooted-dfs.
search-for-vertex.
search-for-vertex.
size.
tag-all-edges.
topological-sort.
traverse-elements.
undirected-edge-class.
untag-all-edges.
vertex-class.
vertex-count.
vertex-key.
vertex-test.
vertexes.
| Initarg | Value |
|---|---|
:initial-size | 25 |
:graph-vertexes
This slot is read-only.
:graph-edges
This slot is read-only.
0
This slot is read-only.
0
This slot is read-only.
The class of the vertexes in the graph. This must extend the base-class for vertexes of the graph type. E.g., all vertexes of a graph-container must extend graph-container-vertex.
(quote cl-graph:basic-vertex)
:vertex-class
This slot is read-only.
The class used to create directed edges in the graph. This must extend the base-class for edges of the graph type and directed-edge-mixin. E.g., the directed-edge-class of a graph-container must extend graph-container-edge and directed-edge-mixin.
(quote cl-graph::basic-directed-edge)
:directed-edge-class
This slot is read-only.
The class used to create undirected edges in the graph. This must extend the base-class for edges of the graph type and undirected-edge-mixin. E.g., all undirected edges of a graph-container must extend graph-container-edge and undirected-edge-mixin.
(quote cl-graph::basic-undirected-edge)
:undirected-edge-class
This slot is read-only.
Returns true if graph contains at least one directed edge. [?? Not sure if this is really kept up-to-date.]
Returns true if graph contains at least one undirected edge. [?? Not sure if this is really kept up-to-date.]
(function eq)
:vertex-test
This slot is read-only.
(function identity)
:vertex-key
This slot is read-only.
(function eq)
:edge-test
This slot is read-only.
(function identity)
:edge-key
This slot is read-only.
The default edge type for the graph. This should be one of :undirected or :directed.
:default-edge-type
This slot is read-only.
The default edge class for the graph.
:default-edge-class
This slot is read-only.
This is the root class for all vertexes in CL-Graph.
container-node-mixin.
add-edge-between-vertexes.
add-edge-to-vertex.
add-vertex.
add-vertex.
adjacentp.
assign-level.
breadth-first-search-graph.
breadth-first-visitor.
(setf color).
color.
delete-vertex.
delete-vertex.
(setf depth-level).
depth-level.
dfs.
dfs-visit.
(setf discovery-time).
discovery-time.
edge-count.
edges.
(setf element).
(setf element).
element.
find-vertex.
(setf finish-time).
finish-time.
(setf graph).
graph.
in-cycle-p.
in-undirected-cycle-p.
initialize-instance.
make-edge-for-graph.
make-load-form.
map-over-all-combinations-of-k-edges.
mst-find-set.
mst-link.
mst-make-set.
mst-tree-union.
(setf next-node).
next-node.
out-edge-for-vertex-p.
(setf previous-node).
previous-node.
print-object.
(setf rank).
rank.
replace-vertex.
replace-vertex.
replace-vertex.
rooted-dfs.
rootp.
search-for-vertex.
source-edge-count.
source-edges.
(setf tag).
tag.
tag-all-edges.
target-edge-count.
target-edges.
traverse-elements-helper.
traverse-elements-helper.
untag-all-edges.
(setf value).
value.
vertex->dot.
vertex-id.
‘Depth-level‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
number
0
:depth-level
‘Vertex-id‘ is used internally to keep track of vertexes.
0
:vertex-id
This slot is read-only.
The ‘element‘ is the value that this vertex represents.
metabang.utilities.
:element
The ‘tag‘ slot is used by some algorithms to keep track of which vertexes have been visited.
metabang.utilities.
:tag
tag.
The graph in which this vertex is contained.
:graph
The ‘color‘ slot is used by some algorithms for bookkeeping.
:color
The ‘rank‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
:rank
rank.
‘Previous-node‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
:previous-node
‘Next-node‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
:next-node
‘Discovery-time‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
-1
:discovery-time
‘Finish-time‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]
-1
:finish-time
This mixin class is used to indicate that an edge is directed.
:dot-attributes
| Initarg | Value |
|---|---|
:vertex-class | (quote dot-vertex) |
:directed-edge-class | (quote dot-directed-edge) |
:undirected-edge-class | (quote dot-edge) |
A graph container is essentially an adjacency list graph representation [?? The Bad name comes from it being implemented with containers... ugh]
basic-graph.
container-uses-nodes-mixin.
initial-contents-mixin.
iteratable-container-mixin.
non-associative-container-mixin.
add-edge.
associate-edge-with-pair.
associate-edge-with-pair.
delete-all-edges.
delete-edge.
dfs-visit.
dissociate-edge-from-pair.
dissociate-edge-from-pair.
edge-count.
empty!.
find-edge.
find-edge-between-vertexes.
find-edge-between-vertexes-if.
find-edge-between-vertexes-if.
iterate-edges.
make-edge-container.
make-node-for-container.
make-vertex-container.
replace-vertex.
replace-vertex.
vertex-pair->edge.
| Initarg | Value |
|---|---|
:vertex-class | (quote graph-container-vertex) |
:directed-edge-class | (quote graph-container-directed-edge) |
:undirected-edge-class | (quote graph-container-undirected-edge) |
(metabang.cl-containers:make-container (quote metabang.cl-containers:simple-associative-container) :test (function equal))
This slot is read-only.
A graph-container-directed-edge is both a directed-edge-mixin and a graph-container-edge.
This is the root class for edges in graph-containers. It adds vertex-1 and vertex-2 slots.
‘Vertex-1‘ is one of the two vertexes that an edge connects. In a directed-edge, ‘vertex-1‘ is also the ‘source-vertex‘.
:vertex-1
This slot is read-only.
A graph-container-undirected-edge is both an undirected-edge-mixin and a graph-container-edge.
A graph container vertex keeps track of its edges in the the vertex-edges slot. The storage for this defaults to a vector-container but can be changed using the vertex-edges-container-class initarg.
add-edge-to-vertex.
find-edge-between-vertexes.
find-edge-between-vertexes-if.
has-children-p.
has-parent-p.
initialize-instance.
iterate-children.
iterate-edges.
iterate-neighbors.
iterate-parents.
iterate-source-edges.
iterate-target-edges.
make-vertex-edges-container.
other-vertex.
vertex-edges.
vertices-share-edge-p.
| Initarg | Value |
|---|---|
:vertex-edges-container-class | (quote vector-container) |
This slot is read-only.
Stub for matrix based graph. Not implemented.
| Initarg | Value |
|---|---|
:vertex-class | (quote graph-matrix-vertex) |
:undirected-edge-class | (quote graph-matrix-edge) |
This slot is read-only.
Stub for matrix based graph. Not implemented.
Stub for matrix based graph. Not implemented.
This mixin class is used to indicate that an edge is undirected.
A weighted edge is a weighted-edge-mixin, a directed-edge-mixin, and a graph-container-edge.
A weighted edge is both a weighted-edge-mixin and a graph-container-edge.
This mixin class adds a ‘weight‘ slot to an edge.
The value of the weight of this edge. Defaults to 1.0d0
metabang.cl-containers.
1.0d0
:weight
A weighted undirected edge is a weighted-edge-mixin, an undirected-edge-mixin, and a graph-container-edge.
Path to ‘dot‘
Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.
copy-seq.
Collects set of unique relatives of nodes in node-list.
Find a state that satisfies goal-p. Start with states, and search according to successors and combiner. Don’t try the same state twice.
Removes all elements in original from target.
Attaches the edge ‘edge‘ to the vertex ‘vertex‘.
graph-container-edge) (vertex graph-container-vertex)) ¶basic-edge) (vertex basic-vertex)) ¶basic-graph) (edges list) &key if-duplicate-do) ¶graph-matrix)) ¶automatically generated reader method
Sets the depth of ‘vertex‘ to level and then
recursively sets the depth of all of the children of ‘vertex‘ to
(1+ level).
basic-vertex) (level number)) ¶basic-graph) (level number)) ¶graph-container) (edge undirected-edge-mixin)) ¶graph-container) (edge graph-container-edge)) ¶basic-graph) (source basic-vertex)) ¶basic-graph) source) ¶basic-graph) (source basic-vertex) fn) ¶basic-graph) source fn) ¶Add edges between vertexes in the new-graph for
which the matching vertexes in the old-graph have edges. The vertex
matching is done using ‘find-vertex‘.
graph-container-edge)) ¶graph-container-edge)) ¶graph-container) (u basic-vertex) fn sorter) ¶graph-container) (edge undirected-edge-mixin)) ¶graph-container) (edge graph-container-edge)) ¶basic-graph)) ¶automatically generated reader method
basic-graph)) ¶automatically generated reader method
dot-edge-mixin)) ¶dot-vertex-mixin)) ¶dot-graph-mixin)) ¶Generate a ’classic’ random graph G(n, m) with n vertexes and m edges.
Generate the Erd"os-R’enyi random graph G(n,
p). I.e., a graph with n vertexes where each possible edge appears
with probability p. This implementation is from Efficient Generation
of Large Random Networks (see batagelj-generation-2005 in doab).
Generate a Barabasi-Albert type scale free graph
with multiple vertex kinds.
The idea behind this implementation is from Efficient Generation of Large Random Networks (see batagelj-generation-2005 in moab).
Generates a ’scale-free’ graph using preferential
attachment – too damn slow.
Size is the number of vertexes; kind-matrix is as in generate-undirected-graph-via-assortativity-matrix, etc.; add-edge-count is the number of edges to add for each vertex; other-vertex-kind-samplers are confusing...; and vertex-labeler is used to create vertex elements (as in other generators).
Generate a simple scale-free graph using the
preferential attachment mechanism of Barabasi and Albert. The
implementation is from Efficient Generation of Large Random Networks
(see batagelj-generation-2005 in moab). Self-edges are possible.
This generates a random graph with ’size’ vertexes.
The vertexes can be in multiple different classes and the number of
vertexes in each class is specified in the ’kind-matrix’. If the
matrix has all fixnums, then it specifies the counts and these should
add up to the size. If the kind-matrix contains non-fixnums then the
values are treated as ratios.
The assortativity-matrix specifies the number of edges between
vertexes of different kinds.
The vertex-labeler is a function of two parameters: the vertex kind and the index. It should return whatever the ’value’ of the vertex ought to be.
Generate an Erd"os-R/’enyi like random graph
having multiple vertex kinds. See the function Gnp for the simple one
vertex kind method.
Generator and graph-class specify the random number generator used and
the class of the graph produced; Size the number of vertexes. Kind
matrix is a vector of ratios specifying the distribution of vertex
kinds {0 ... (1- k)}. The probability-matrix is a k x k matrix
specifying the probability that two vertexes of the row-kind and the
column-kind will have an edge between them. vertex-labeler is a
function of two arguments (the kind and the vertex number) called to
create values for vertexes. It will be called only once for each
vertex created.
The clever sequential sampling technique in this implementation is from Efficient Generation of Large Random Networks (see batagelj-generation-2005 in moab).
basic-graph)) ¶basic-graph)) ¶automatically generated reader method
basic-graph)) ¶automatically generated reader method
Make-edge-container is called during graph creation
and can be used to create specialized containers to hold graph
edges.
graph-matrix) initial-size) ¶graph-container) initial-size) ¶It should not usually necessary to call this in
user code. Creates a new edge between vertex-1 and vertex-2 for the
graph. If the edge-type and edge-class are not specified, they will
be determined from the defaults of the graph.
basic-graph) (vertex-1 basic-vertex) (vertex-2 basic-vertex) &rest args &key edge-type edge-class &allow-other-keys) ¶Make-vertex-container is called during graph
creation and can be used to create specialized containers to hold
graph vertexes.
graph-matrix) initial-size) ¶graph-container) initial-size) ¶basic-vertex) k fn) ¶basic-graph) k fn) ¶basic-graph) k fn) ¶basic-vertex)) ¶basic-vertex) (v2 basic-vertex)) ¶basic-vertex)) ¶basic-vertex) (v2 basic-vertex)) ¶Sets the ‘tag‘ of all the edges of ‘thing‘ to true. [?? why does this exist?]
list)) ¶WIP
basic-graph) (style symbol) fn) ¶WIP
basic-vertex) (style (eql :breadth)) marker fn) ¶basic-vertex) (style (eql :depth)) marker fn) ¶Sets the ‘tag‘ of all the edges of ‘thing‘ to true. [?? why does this exist?]
list)) ¶basic-edge)) ¶automatically generated reader method
basic-vertex)) ¶The ‘element‘ is the value that this vertex represents.
basic-edge)) ¶automatically generated writer method
basic-vertex)) ¶The ‘element‘ is the value that this vertex represents.
graph-container-vertex)) ¶automatically generated reader method
basic-graph)) ¶automatically generated reader method
graph-container)) ¶automatically generated reader method
basic-graph)) ¶automatically generated reader method
| Jump to: | (
A B C D E F G H I L M N O P R S T U V W |
|---|
| Jump to: | (
A B C D E F G H I L M N O P R S T U V W |
|---|
| Jump to: | *
A C D E F G L N P R S T U V W |
|---|
| Jump to: | *
A C D E F G L N P R S T U V W |
|---|
| Jump to: | A B C D E F G I M N P S U W |
|---|
| Jump to: | A B C D E F G I M N P S U W |
|---|