The cl-graph Reference Manual

Table of Contents

The cl-graph Reference Manual

This is the cl-graph Reference Manual, version 0.10.2, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Oct 13 09:41:24 2021 GMT+0.

1 Systems

The main system appears first, followed by any subsystem dependency.

1.1 cl-graph

Maintainer

Gary Warren King <gwking@metabang.com>

Author

Gary Warren King <gwking@metabang.com>

License

MIT Style License

Description

Graph manipulation utilities for Common Lisp

Version

0.10.2

Dependencies

• metatilities-base (at least version 0.6.0)
• cl-containers (at least version 0.12.0)
• metabang-bind

Source

cl-graph.asd (file)

Components

• copying (file)
• dev (module)
• website (module)

2 Modules

Modules are listed depth-first from the system components tree.

2.1 cl-graph/dev

Parent

cl-graph (system)

Location

dev/

Components

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

2.2 cl-graph/dev/graphviz

Dependency

graph.lisp (file)

Parent

dev (module)

Location

dev/graphviz/

Component

graphviz-support.lisp (file)

2.3 cl-graph/website

Parent

cl-graph (system)

Location

website/

Component

source (module)

2.4 cl-graph/website/source

Parent

website (module)

Location

website/source/

Component

index.mmd (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 cl-graph.asd

Location

cl-graph.asd

Systems

cl-graph (system)

3.1.2 cl-graph/dev/package.lisp

Parent

dev (module)

Location

dev/package.lisp

Packages

cl-graph

3.1.3 cl-graph/dev/api.lisp

Dependency

package.lisp (file)

Parent

dev (module)

Location

dev/api.lisp

Exported Definitions

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

Internal Definitions

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

3.1.4 cl-graph/dev/macros.lisp

Dependency

package.lisp (file)

Parent

dev (module)

Location

dev/macros.lisp

Exported Definitions

with-changing-vertex (macro)

3.1.5 cl-graph/dev/graph.lisp

Dependencies

• api.lisp (file)
• macros.lisp (file)

Parent

dev (module)

Location

dev/graph.lisp

Exported Definitions

• 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 (method)
• (setf color) (method)
• color (method)
• (setf color) (method)
• contains-directed-edge-p (method)
• (setf contains-directed-edge-p) (method)
• contains-undirected-edge-p (method)
• (setf contains-undirected-edge-p) (method)
• default-edge-class (method)
• default-edge-type (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 (method)
• (setf depth-level) (method)
• directed-edge-class (method)
• directed-edge-mixin (class)
• directed-edge-p (method)
• discovery-time (method)
• (setf discovery-time) (method)
• edge (method)
• edge-count (method)
• edge-count (method)
• edge-error (condition)
• edge-id (method)
• (setf edge-id) (method)
• edges (method)
• edges (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 (method)
• (setf finish-time) (method)
• force-undirected (method)
• generate-directed-free-tree (method)
• get-transitive-closure (function)
• graph (method)
• graph (method)
• (setf graph) (method)
• graph (method)
• graph-edge-not-found-error (condition)
• graph-edges (method)
• graph-error (condition)
• graph-roots (method)
• graph-vertex-not-found-error (condition)
• graph-vertex-not-found-in-edge-error (condition)
• graph-vertexes (method)
• in-cycle-p (method)
• in-cycle-p (method)
• in-undirected-cycle-p (method)
• iterate-vertexes (method)
• iterate-vertexes (method)
• make-graph (method)
• make-vertex-for-graph (method)
• map-paths (function)
• map-shortest-paths (function)
• neighbor-vertexes (method)
• next-node (method)
• (setf next-node) (method)
• number-of-neighbors (method)
• parent-vertexes (method)
• previous-node (method)
• (setf previous-node) (method)
• project-bipartite-graph (method)
• project-bipartite-graph (method)
• rank (method)
• (setf rank) (method)
• renumber-edges (method)
• renumber-vertexes (method)
• replace-vertex (method)
• rootp (method)
• search-for-vertex (method)
• search-for-vertex (method)
• source-edge-count (method)
• source-edges (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 (method)
• undirected-edge-mixin (class)
• undirected-edge-p (method)
• untag-all-edges (method)
• untag-all-edges (method)
• untagged-edge-p (method)
• vertex (method)
• vertex (method)
• vertex-1 (method)
• vertex-2 (method)
• vertex-class (method)
• vertex-count (compiler macro)
• vertex-count (method)
• vertex-id (method)
• vertexes (method)
• weighted-edge-mixin (class)

Internal Definitions

• add-edge-to-vertex (method)
• append-unique (function)
• assign-level (method)
• assign-level (method)
• edge-key (method)
• edge-test (method)
• get-nodelist-relatives (function)
• graph-search-for-cl-graph (function)
• largest-edge-id (method)
• largest-vertex-id (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 (method)
• (setf value) (method)
• value (method)
• (setf value) (method)
• vertex-key (method)
• vertex-test (method)

3.1.6 cl-graph/dev/graph-container.lisp

Dependency

graph.lisp (file)

Parent

dev (module)

Location

dev/graph-container.lisp

Exported Definitions

• add-edge (method)
• delete-all-edges (method)
• delete-edge (method)
• edge-count (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)
• iterate-edges (method)
• iterate-edges (method)
• iterate-neighbors (method)
• iterate-parents (method)
• iterate-source-edges (method)
• iterate-target-edges (method)
• make-vertex-edges-container (method)
• other-vertex (method)
• other-vertex (method)
• replace-vertex (method)
• replace-vertex (method)
• source-vertex (method)
• target-vertex (method)
• vertex-1 (method)
• vertex-2 (method)
• vertexes (method)
• vertices-share-edge-p (method)
• weighted-directed-edge (class)
• weighted-edge (class)
• weighted-undirected-edge (class)

Internal Definitions

• 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 (method)
• vertex-pair->edge (method)

3.1.7 cl-graph/dev/graph-matrix.lisp

Dependency

graph.lisp (file)

Parent

dev (module)

Location

dev/graph-matrix.lisp

Exported Definitions

• graph-matrix (class)
• graph-matrix-edge (class)
• graph-matrix-vertex (class)

Internal Definitions

• adjencency-matrix (method)
• make-edge-container (method)
• make-vertex-container (method)

3.1.8 cl-graph/dev/graph-algorithms.lisp

Dependency

graph.lisp (file)

Parent

dev (module)

Location

dev/graph-algorithms.lisp

Exported Definitions

• 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)
• rooted-dfs (method)
• rooted-dfs (method)

Internal Definitions

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

3.1.9 cl-graph/dev/graphviz/graphviz-support.lisp

Parent

graphviz (module)

Location

dev/graphviz/graphviz-support.lisp

Exported Definitions

• *dot-graph-attributes* (special variable)
• dot-attribute-value (method)
• (setf dot-attribute-value) (method)
• (setf dot-attribute-value) (method)
• dot-attributes (method)
• (setf dot-attributes) (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)

Internal Definitions

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

3.2 Static

3.2.1 cl-graph/COPYING

Parent

cl-graph (system)

Location

COPYING

3.2.2 cl-graph/dev/notes.text

Parent

dev (module)

Location

dev/notes.text

3.2.3 cl-graph/website/source/index.mmd

Parent

source (module)

Location

website/source/index.mmd

4 Packages

Packages are listed by definition order.

4.1 cl-graph

CL-Graph is a Common Lisp library for manipulating graphs and running graph algorithms.

Source

package.lisp (file)

Nickname

metabang.graph

Use List

• metabang.bind
• metabang.cl-containers
• metabang.utilities
• common-lisp

Exported Definitions

• *dot-graph-attributes* (special variable)
• add-edge (generic function)
• add-edge (method)
• add-edge (method)
• add-edge-between-vertexes (generic function)
• add-edge-between-vertexes (method)
• add-edge-between-vertexes (method)
• add-vertex (generic function)
• add-vertex (method)
• add-vertex (method)
• add-vertex (method)
• adjacentp (generic function)
• adjacentp (method)
• adjacentp (method)
• any-undirected-cycle-p (generic function)
• any-undirected-cycle-p (method)
• assortativity-coefficient (generic function)
• basic-edge (class)
• basic-graph (class)
• basic-vertex (class)
• child-vertexes (generic function)
• child-vertexes (method)
• color (generic function)
• color (method)
• (setf color) (method)
• color (method)
• (setf color) (method)
• (setf color) (generic function)
• connected-component-count (generic function)
• connected-component-count (method)
• connected-components (generic function)
• connected-components (method)
• connected-graph-p (generic function)
• connected-graph-p (method)
• contains-directed-edge-p (generic function)
• contains-directed-edge-p (method)
• (setf contains-directed-edge-p) (method)
• (setf contains-directed-edge-p) (generic function)
• contains-undirected-edge-p (generic function)
• contains-undirected-edge-p (method)
• (setf contains-undirected-edge-p) (method)
• (setf contains-undirected-edge-p) (generic function)
• default-edge-class (generic function)
• default-edge-class (method)
• default-edge-type (generic function)
• default-edge-type (method)
• delete-all-edges (generic function)
• delete-all-edges (method)
• delete-all-edges (method)
• delete-edge (generic function)
• delete-edge (method)
• delete-edge (method)
• delete-edge-between-vertexes (generic function)
• delete-edge-between-vertexes (method)
• delete-vertex (generic function)
• delete-vertex (method)
• delete-vertex (method)
• delete-vertex (method)
• depth (generic function)
• depth (method)
• depth-level (generic function)
• depth-level (method)
• (setf depth-level) (method)
• (setf depth-level) (generic function)
• dfs (generic function)
• dfs (method)
• dfs (method)
• dfs-back-edge-p (generic function)
• dfs-back-edge-p (method)
• dfs-edge-type (generic function)
• dfs-edge-type (method)
• dfs-tree-edge-p (generic function)
• dfs-tree-edge-p (method)
• directed-edge-class (generic function)
• directed-edge-class (method)
• directed-edge-mixin (class)
• directed-edge-p (generic function)
• directed-edge-p (method)
• discovery-time (generic function)
• discovery-time (method)
• (setf discovery-time) (method)
• (setf discovery-time) (generic function)
• dot-attribute-value (generic function)
• dot-attribute-value (method)
• (setf dot-attribute-value) (method)
• (setf dot-attribute-value) (generic function)
• (setf dot-attribute-value) (method)
• dot-attributes (generic function)
• dot-attributes (method)
• (setf dot-attributes) (method)
• (setf dot-attributes) (generic function)
• 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 function)
• edge (method)
• edge->dot (generic function)
• edge->dot (method)
• edge->dot (method)
• edge-count (generic function)
• edge-count (method)
• edge-count (method)
• edge-count (method)
• edge-error (condition)
• edge-id (generic function)
• edge-id (method)
• (setf edge-id) (method)
• (setf edge-id) (generic function)
• edge-lessp-by-direction (generic function)
• edge-lessp-by-direction (method)
• edge-lessp-by-weight (generic function)
• edge-lessp-by-weight (method)
• edges (generic function)
• edges (method)
• edges (method)
• find-connected-components (generic function)
• find-connected-components (method)
• find-edge (generic function)
• find-edge (method)
• find-edge-between-vertexes (generic function)
• find-edge-between-vertexes (method)
• find-edge-between-vertexes (method)
• find-edge-between-vertexes-if (generic function)
• find-edge-between-vertexes-if (method)
• find-edge-between-vertexes-if (method)
• find-edge-if (generic function)
• find-edge-if (method)
• find-edges-if (generic function)
• find-edges-if (method)
• find-vertex (generic function)
• find-vertex (method)
• find-vertex (method)
• find-vertex (method)
• find-vertex-if (generic function)
• find-vertex-if (method)
• find-vertex-if (method)
• find-vertexes-if (generic function)
• find-vertexes-if (method)
• finish-time (generic function)
• finish-time (method)
• (setf finish-time) (method)
• (setf finish-time) (generic function)
• force-undirected (generic function)
• force-undirected (method)
• generate-directed-free-tree (generic function)
• generate-directed-free-tree (method)
• get-transitive-closure (function)
• graph (generic function)
• graph (method)
• graph (method)
• (setf graph) (method)
• graph (method)
• (setf graph) (generic function)
• graph->dot (generic function)
• graph->dot (method)
• graph->dot (method)
• graph->dot (method)
• graph->dot (method)
• graph->dot (method)
• graph->dot-external (generic function)
• graph->dot-external (method)
• graph->dot-properties (generic function)
• graph->dot-properties (method)
• graph->dot-properties (method)
• 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 function)
• graph-edges (method)
• graph-error (condition)
• graph-matrix (class)
• graph-matrix-edge (class)
• graph-matrix-vertex (class)
• graph-mixing-matrix (generic function)
• graph-roots (generic function)
• graph-roots (method)
• graph-vertex-not-found-error (condition)
• graph-vertex-not-found-in-edge-error (condition)
• graph-vertexes (generic function)
• graph-vertexes (method)
• has-children-p (generic function)
• has-children-p (method)
• has-parent-p (generic function)
• has-parent-p (method)
• height-in-pixels (generic function)
• height-in-pixels (method)
• (setf height-in-pixels) (method)
• (setf height-in-pixels) (generic function)
• in-cycle-p (generic function)
• in-cycle-p (method)
• in-cycle-p (method)
• in-undirected-cycle-p (generic function)
• in-undirected-cycle-p (method)
• iterate-edges (generic function)
• iterate-edges (method)
• iterate-edges (method)
• iterate-neighbors (generic function)
• iterate-neighbors (method)
• iterate-parents (generic function)
• iterate-parents (method)
• iterate-source-edges (generic function)
• iterate-source-edges (method)
• iterate-target-edges (generic function)
• iterate-target-edges (method)
• iterate-vertexes (generic function)
• iterate-vertexes (method)
• iterate-vertexes (method)
• make-filtered-graph (generic function)
• make-graph (generic function)
• make-graph (method)
• make-graph-from-vertexes (generic function)
• make-vertex-edges-container (generic function)
• make-vertex-edges-container (method)
• make-vertex-for-graph (generic function)
• make-vertex-for-graph (method)
• map-paths (function)
• map-shortest-paths (function)
• minimum-spanning-tree (generic function)
• minimum-spanning-tree (method)
• neighbor-vertexes (generic function)
• neighbor-vertexes (method)
• next-node (generic function)
• next-node (method)
• (setf next-node) (method)
• (setf next-node) (generic function)
• number-of-neighbors (generic function)
• number-of-neighbors (method)
• other-vertex (generic function)
• other-vertex (method)
• other-vertex (method)
• out-edge-for-vertex-p (generic function)
• out-edge-for-vertex-p (method)
• parent-vertexes (generic function)
• parent-vertexes (method)
• previous-node (generic function)
• previous-node (method)
• (setf previous-node) (method)
• (setf previous-node) (generic function)
• print-dot-key-value (function)
• project-bipartite-graph (generic function)
• project-bipartite-graph (method)
• project-bipartite-graph (method)
• rank (generic function)
• rank (method)
• (setf rank) (method)
• (setf rank) (generic function)
• renumber-edges (generic function)
• renumber-edges (method)
• renumber-vertexes (generic function)
• renumber-vertexes (method)
• replace-vertex (generic function)
• replace-vertex (method)
• replace-vertex (method)
• replace-vertex (method)
• rooted-dfs (generic function)
• rooted-dfs (method)
• rooted-dfs (method)
• rootp (generic function)
• rootp (method)
• search-for-vertex (generic function)
• search-for-vertex (method)
• search-for-vertex (method)
• source-edge-count (generic function)
• source-edge-count (method)
• source-edges (generic function)
• source-edges (method)
• source-vertex (generic function)
• source-vertex (method)
• subgraph-containing (generic function)
• tag-all-edges (generic function)
• tag-all-edges (method)
• tag-all-edges (method)
• tagged-edge-p (generic function)
• tagged-edge-p (method)
• target-edge-count (generic function)
• target-edge-count (method)
• target-edges (generic function)
• target-edges (method)
• target-vertex (generic function)
• target-vertex (method)
• topological-sort (generic function)
• topological-sort (method)
• undirected-edge-class (generic function)
• undirected-edge-class (method)
• undirected-edge-mixin (class)
• undirected-edge-p (generic function)
• undirected-edge-p (method)
• untag-all-edges (generic function)
• untag-all-edges (method)
• untag-all-edges (method)
• untagged-edge-p (generic function)
• untagged-edge-p (method)
• vertex (generic function)
• vertex (method)
• vertex (method)
• vertex-1 (generic function)
• vertex-1 (method)
• vertex-1 (method)
• vertex-2 (generic function)
• vertex-2 (method)
• vertex-2 (method)
• vertex->dot (generic function)
• vertex->dot (method)
• vertex->dot (method)
• vertex-class (generic function)
• vertex-class (method)
• vertex-count (compiler macro)
• vertex-count (generic function)
• vertex-count (method)
• vertex-id (generic function)
• vertex-id (method)
• vertexes (generic function)
• vertexes (method)
• vertexes (method)
• vertices-share-edge-p (generic function)
• vertices-share-edge-p (method)
• weighted-directed-edge (class)
• weighted-edge (class)
• weighted-edge-mixin (class)
• weighted-undirected-edge (class)
• width-in-pixels (generic function)
• width-in-pixels (method)
• (setf width-in-pixels) (method)
• (setf width-in-pixels) (generic function)
• with-changing-vertex (macro)

Internal Definitions

• *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-edge-to-vertex (method)
• add-edge-to-vertex (method)
• add-edges-to-graph (generic function)
• add-edges-to-graph (method)
• adjencency-matrix (generic function)
• adjencency-matrix (method)
• append-unique (function)
• assign-level (generic function)
• assign-level (method)
• assign-level (method)
• associate-edge-with-pair (generic function)
• associate-edge-with-pair (method)
• associate-edge-with-pair (method)
• breadth-first-search-graph (generic function)
• breadth-first-search-graph (method)
• breadth-first-search-graph (method)
• breadth-first-visitor (generic function)
• breadth-first-visitor (method)
• breadth-first-visitor (method)
• complete-links (generic function)
• copy-vertex-datum (function)
• defpixel-inch-accessors (macro)
• dfs-cross-edge-p (generic function)
• dfs-cross-edge-p (method)
• dfs-forward-edge-p (generic function)
• dfs-forward-edge-p (method)
• dfs-visit (generic function)
• dfs-visit (method)
• dissoc-val-from-key-or-delete (function)
• dissociate-edge-from-pair (generic function)
• dissociate-edge-from-pair (method)
• dissociate-edge-from-pair (method)
• edge-key (generic function)
• edge-key (method)
• edge-test (generic function)
• edge-test (method)
• ensure-valid-dot-attribute (generic function)
• ensure-valid-dot-attribute (method)
• ensure-valid-dot-attribute (method)
• ensure-valid-dot-attribute (method)
• 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)
• initialize-vertex-data (method)
• largest-edge-id (generic function)
• largest-edge-id (method)
• largest-vertex-id (generic function)
• largest-vertex-id (method)
• make-edge-container (generic function)
• make-edge-container (method)
• make-edge-container (method)
• make-edge-for-graph (generic function)
• make-edge-for-graph (method)
• make-vertex-container (generic function)
• make-vertex-container (method)
• make-vertex-container (method)
• make-vertex-datum (function)
• map-over-all-combinations-of-k-edges (generic function)
• map-over-all-combinations-of-k-edges (method)
• map-over-all-combinations-of-k-edges (method)
• map-over-all-combinations-of-k-vertexes (generic function)
• map-over-all-combinations-of-k-vertexes (method)
• mst-find-set (generic function)
• mst-find-set (method)
• mst-link (generic function)
• mst-link (method)
• mst-make-set (generic function)
• mst-make-set (method)
• mst-tree-union (generic function)
• mst-tree-union (method)
• 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)
• tag-edges (method)
• textify (function)
• traverse-elements (generic function)
• traverse-elements (method)
• traverse-elements-helper (generic function)
• traverse-elements-helper (method)
• traverse-elements-helper (method)
• untag-edges (generic function)
• untag-edges (method)
• value (generic function)
• value (method)
• (setf value) (method)
• value (method)
• (setf value) (method)
• (setf value) (generic function)
• vertex-edges (generic function)
• vertex-edges (method)
• vertex-key (generic function)
• vertex-key (method)
• vertex-pair->edge (generic function)
• vertex-pair->edge (method)
• vertex-test (generic function)
• vertex-test (method)
• write-name-for-dot (generic function)
• write-name-for-dot (method)
• write-name-for-dot (method)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Special variables

Special Variable: *dot-graph-attributes*

Package

cl-graph

Source

graphviz-support.lisp (file)

5.1.2 Macros

Macro: with-changing-vertex (VERTEX) &body BODY

This is used to maintain consistency when changing the value of vertex elements while iterating over the vertexes...

Package

cl-graph

Source

macros.lisp (file)

5.1.3 Compiler macros

Compiler Macro: vertex-count &rest ARGS

Package

cl-graph

Source

graph.lisp (file)

5.1.4 Functions

Function: get-transitive-closure VERTEX-LIST &optional DEPTH

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

Package

cl-graph

Source

graph.lisp (file)

Function: map-paths GRAPH START-VERTEX LENGTH FN &key FILTER

Apply fn to each path that starts at start-vertex and is of exactly length length

Package

cl-graph

Source

graph.lisp (file)

Function: map-shortest-paths GRAPH START-VERTEX DEPTH FN &key FILTER

Apply fn to each shortest path starting at ‘start-vertex‘ of depth ‘depth‘. The ‘filter‘ predicate is used to remove vertexes from consideration.

Package

cl-graph

Source

graph.lisp (file)

Function: print-dot-key-value KEY VALUE DOT-ATTRIBUTES STREAM

Package

cl-graph

Source

graphviz-support.lisp (file)

5.1.5 Generic functions

Generic Function: add-edge GRAPH EDGE &rest ARGS &key FORCE-NEW?

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: add-edge (GRAPH graph-container) (EDGE graph-container-edge) &key FORCE-NEW?

Source

graph-container.lisp (file)

Method: add-edge (GRAPH basic-graph) (EDGE basic-edge) &key FORCE-NEW? before

Source

graph.lisp (file)

Generic Function: add-edge-between-vertexes GRAPH VALUE-OR-VERTEX-1 VALUE-OR-VERTEX-2 &rest ARGS &key IF-DUPLICATE-DO EDGE-TYPE VALUE EDGE-CLASS &allow-other-keys

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: add-edge-between-vertexes (GRAPH basic-graph) (V-1 basic-vertex) (V-2 basic-vertex) &rest ARGS &key VALUE IF-DUPLICATE-DO EDGE-TYPE EDGE-CLASS &allow-other-keys

Source

graph.lisp (file)

Method: add-edge-between-vertexes (GRAPH basic-graph) VALUE-1 VALUE-2 &rest ARGS &key IF-DUPLICATE-DO &allow-other-keys

Source

graph.lisp (file)

Generic Function: add-vertex GRAPH VALUE-OR-VERTEX &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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: add-vertex (GRAPH basic-graph) (VERTEX basic-vertex) &key &allow-other-keys before

Source

graph.lisp (file)

Method: add-vertex (GRAPH basic-graph) VALUE &rest ARGS &key IF-DUPLICATE-DO &allow-other-keys

Source

graph.lisp (file)

Method: add-vertex (GRAPH basic-graph) (VALUE basic-vertex) &key IF-DUPLICATE-DO

Source

graph.lisp (file)

Generic Function: adjacentp GRAPH VERTEX-1 VERTEX-2

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]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: adjacentp (GRAPH basic-graph) (VERTEX-1 basic-vertex) (VERTEX-2 basic-vertex)

Source

graph.lisp (file)

Method: adjacentp (GRAPH basic-graph) VERTEX-1 VERTEX-2

Source

graph.lisp (file)

Generic Function: any-undirected-cycle-p GRAPH

Returns true if there are any undirected cycles in ‘graph‘.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: any-undirected-cycle-p (GRAPH basic-graph)

Source

graph.lisp (file)

Generic Function: assortativity-coefficient MIXING-MATRIX

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

Package

cl-graph

Source

api.lisp (file)

Generic Function: child-vertexes VERTEX &optional FILTER

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

Package

cl-graph

Source

api.lisp (file)

Methods

Method: child-vertexes VERTEX &optional FILTER

Source

graph.lisp (file)

Generic Function: color OBJECT

Generic Function: (setf color) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: color (BASIC-EDGE basic-edge)

Method: (setf color) NEW-VALUE (BASIC-EDGE basic-edge)

The ‘color‘ is used by some algorithms for bookkeeping. [?? Should probably be in a mixin]

Source

graph.lisp (file)

Method: color (BASIC-VERTEX basic-vertex)

Method: (setf color) NEW-VALUE (BASIC-VERTEX basic-vertex)

The ‘color‘ slot is used by some algorithms for bookkeeping.

Source

graph.lisp (file)

Generic Function: connected-component-count GRAPH

Returns the number of connected-components of graph.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: connected-component-count (GRAPH basic-graph)

Source

graph-algorithms.lisp (file)

Generic Function: connected-components GRAPH

Returns a union-find-container representing the connected-components of ‘graph‘.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: connected-components (GRAPH basic-graph)

Source

graph-algorithms.lisp (file)

Generic Function: connected-graph-p GRAPH &key EDGE-SORTER

Returns true if graph is a connected graph and nil otherwise.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: connected-graph-p (GRAPH basic-graph) &key EDGE-SORTER

Source

graph-algorithms.lisp (file)

Generic Function: contains-directed-edge-p OBJECT

Generic Function: (setf contains-directed-edge-p) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: contains-directed-edge-p (BASIC-GRAPH basic-graph)

Method: (setf contains-directed-edge-p) NEW-VALUE (BASIC-GRAPH basic-graph)

Returns true if graph contains at least one directed edge. [?? Not sure if this is really kept up-to-date.]

Source

graph.lisp (file)

Generic Function: contains-undirected-edge-p OBJECT

Generic Function: (setf contains-undirected-edge-p) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: contains-undirected-edge-p (BASIC-GRAPH basic-graph)

Method: (setf contains-undirected-edge-p) NEW-VALUE (BASIC-GRAPH basic-graph)

Returns true if graph contains at least one undirected edge. [?? Not sure if this is really kept up-to-date.]

Source

graph.lisp (file)

Generic Function: default-edge-class OBJECT

Package

cl-graph

Methods

Method: default-edge-class (BASIC-GRAPH basic-graph)

The default edge class for the graph.

Source

graph.lisp (file)

Generic Function: default-edge-type OBJECT

Package

cl-graph

Methods

Method: default-edge-type (BASIC-GRAPH basic-graph)

The default edge type for the graph. This should be one of :undirected or :directed.

Source

graph.lisp (file)

Generic Function: delete-all-edges GRAPH

Delete all edges from ‘graph’. Returns the graph..

Package

cl-graph

Source

api.lisp (file)

Methods

Method: delete-all-edges (GRAPH graph-container)

Source

graph-container.lisp (file)

Method: delete-all-edges (GRAPH basic-graph) after

Source

graph.lisp (file)

Generic Function: delete-edge GRAPH EDGE

Delete the ‘edge’ from the ‘graph’ and returns it.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: delete-edge (GRAPH graph-container) (EDGE graph-container-edge)

Source

graph-container.lisp (file)

Method: delete-edge (GRAPH basic-graph) (EDGE basic-edge) after

Source

graph.lisp (file)

Generic Function: delete-edge-between-vertexes GRAPH VALUE-OR-VERTEX-1 VALUE-OR-VERTEX-2 &rest ARGS

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: delete-edge-between-vertexes (GRAPH basic-graph) VALUE-OR-VERTEX-1 VALUE-OR-VERTEX-2 &rest ARGS

Source

graph.lisp (file)

Generic Function: delete-vertex GRAPH VALUE-OR-VERTEX

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: delete-vertex (GRAPH basic-graph) (VERTEX basic-vertex) after

Source

graph.lisp (file)

Method: delete-vertex (GRAPH basic-graph) (VERTEX basic-vertex)

Source

graph.lisp (file)

Method: delete-vertex (GRAPH basic-graph) VALUE-OR-VERTEX

Source

graph.lisp (file)

Generic Function: depth GRAPH

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: depth (GRAPH basic-graph)

Source

graph.lisp (file)

Generic Function: depth-level OBJECT

Generic Function: (setf depth-level) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: depth-level (BASIC-VERTEX basic-vertex)

Method: (setf depth-level) NEW-VALUE (BASIC-VERTEX basic-vertex)

‘Depth-level‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]

Source

graph.lisp (file)

Generic Function: dfs GRAPH ROOT FN &key OUT-EDGE-SORTER

Package

cl-graph

Source

api.lisp (file)

Methods

Method: dfs (GRAPH basic-graph) (ROOT basic-vertex) FN &key OUT-EDGE-SORTER

Source

graph-algorithms.lisp (file)

Method: dfs (GRAPH basic-graph) ROOT FN &key OUT-EDGE-SORTER

Source

graph-algorithms.lisp (file)

Generic Function: dfs-back-edge-p EDGE

Package

cl-graph

Source

api.lisp (file)

Methods

Method: dfs-back-edge-p (EDGE graph-container-edge)

Source

graph-algorithms.lisp (file)

Generic Function: dfs-edge-type EDGE

Package

cl-graph

Source

api.lisp (file)

Methods

Method: dfs-edge-type (EDGE graph-container-edge)

Source

graph-algorithms.lisp (file)

Generic Function: dfs-tree-edge-p EDGE

Package

cl-graph

Source

api.lisp (file)

Methods

Method: dfs-tree-edge-p (EDGE graph-container-edge)

Source

graph-algorithms.lisp (file)

Generic Function: directed-edge-class OBJECT

Package

cl-graph

Methods

Method: directed-edge-class (BASIC-GRAPH 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.

Source

graph.lisp (file)

Generic Function: directed-edge-p EDGE

Returns true if-and-only-if edge is directed

Package

cl-graph

Source

api.lisp (file)

Methods

Method: directed-edge-p (EDGE basic-edge)

Source

graph.lisp (file)

Generic Function: discovery-time OBJECT

Generic Function: (setf discovery-time) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: discovery-time (BASIC-VERTEX basic-vertex)

Method: (setf discovery-time) NEW-VALUE (BASIC-VERTEX basic-vertex)

‘Discovery-time‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]

Source

graph.lisp (file)

Generic Function: dot-attribute-value ATTRIBUTE THING

Generic Function: (setf dot-attribute-value) VALUE ATTRIBUTE THING

Package

cl-graph

Source

api.lisp (file)

Methods

Method: dot-attribute-value (ATTR symbol) (THING dot-attributes-mixin)

Method: (setf dot-attribute-value) VALUE (ATTR symbol) (THING dot-attributes-mixin)

Source

graphviz-support.lisp (file)

Method: (setf dot-attribute-value) VALUE (ATTR symbol) (THING dot-attributes-mixin) before

Source

graphviz-support.lisp (file)

Generic Function: dot-attributes OBJECT

Generic Function: (setf dot-attributes) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: dot-attributes (DOT-ATTRIBUTES-MIXIN dot-attributes-mixin)

automatically generated reader method

Source

graphviz-support.lisp (file)

Method: (setf dot-attributes) NEW-VALUE (DOT-ATTRIBUTES-MIXIN dot-attributes-mixin)

automatically generated writer method

Source

graphviz-support.lisp (file)

Generic Function: edge CONDITION

Package

cl-graph

Methods

Method: edge (CONDITION edge-error)

Source

graph.lisp (file)

Generic Function: edge->dot EDGE STREAM

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: edge->dot (EDGE dot-edge-mixin) STREAM

Source

graphviz-support.lisp (file)

Method: edge->dot (V basic-edge) (STREAM stream)

Source

graphviz-support.lisp (file)

Generic Function: edge-count VERTEX

Returns the number of edges attached to
‘vertex‘. Compare with the more flexible ‘vertex-degree‘.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: edge-count (GRAPH graph-container)

Source

graph-container.lisp (file)

Method: edge-count (VERTEX basic-vertex)

Source

graph.lisp (file)

Method: edge-count (GRAPH basic-graph)

Source

graph.lisp (file)

Generic Function: edge-id OBJECT

Generic Function: (setf edge-id) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: edge-id (BASIC-EDGE basic-edge)

Method: (setf edge-id) NEW-VALUE (BASIC-EDGE basic-edge)

The ‘edge-id‘ is used internally by CL-Graph for bookkeeping.

Source

graph.lisp (file)

Generic Function: edge-lessp-by-direction EDGE-1 EDGE-2

Returns true if and only if edge-1 is undirected and edge-2 is directed.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: edge-lessp-by-direction (E1 basic-edge) (E2 basic-edge)

Source

graph-algorithms.lisp (file)

Generic Function: edge-lessp-by-weight EDGE-1 EDGE-2

Returns true if the weight of edge-1 is strictly less than the weight of edge-2.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: edge-lessp-by-weight (E1 basic-edge) (E2 basic-edge)

Source

graph-algorithms.lisp (file)

Generic Function: edges THING

Returns a list of the edges of ‘thing‘.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: edges (VERTEX basic-vertex)

Source

graph.lisp (file)

Method: edges (GRAPH basic-graph)

Source

graph.lisp (file)

Generic Function: find-connected-components 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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: find-connected-components (GRAPH basic-graph)

Source

graph-algorithms.lisp (file)

Generic Function: find-edge GRAPH EDGE &optional ERROR-IF-NOT-FOUND?

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?]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: find-edge (GRAPH graph-container) (EDGE graph-container-edge) &optional ERROR-IF-NOT-FOUND?

Source

graph-container.lisp (file)

Generic Function: find-edge-between-vertexes GRAPH VALUE-OR-VERTEX-1 VALUE-OR-VERTEX-2 &key 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]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: find-edge-between-vertexes (GRAPH graph-container) (VERTEX-1 graph-container-vertex) (VERTEX-2 graph-container-vertex) &key ERROR-IF-NOT-FOUND?

Source

graph-container.lisp (file)

Method: find-edge-between-vertexes (GRAPH basic-graph) VALUE-1 VALUE-2 &key ERROR-IF-NOT-FOUND?

Source

graph.lisp (file)

Generic Function: find-edge-between-vertexes-if GRAPH VALUE-OR-VERTEX-1 VALUE-OR-VERTEX-2 FN &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.]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: find-edge-between-vertexes-if (GRAPH graph-container) VALUE-1 VALUE-2 FN &key ERROR-IF-NOT-FOUND?

Source

graph-container.lisp (file)

Method: find-edge-between-vertexes-if (GRAPH graph-container) (VERTEX-1 graph-container-vertex) (VERTEX-2 graph-container-vertex) FN &key ERROR-IF-NOT-FOUND?

Source

graph-container.lisp (file)

Generic Function: find-edge-if GRAPH FN &key KEY

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: find-edge-if (GRAPH basic-graph) FN &key KEY

Source

graph.lisp (file)

Generic Function: find-edges-if THING PREDICATE

Returns a list of edges in ‘thing‘ for which the ‘predicate‘ returns non-nil. [?? why no key function?]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: find-edges-if (GRAPH basic-graph) FN

Source

graph.lisp (file)

Generic Function: find-vertex GRAPH VALUE &optional ERROR-IF-NOT-FOUND?

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: find-vertex (EDGE basic-edge) VALUE &optional ERROR-IF-NOT-FOUND?

Source

graph.lisp (file)

Method: find-vertex (GRAPH basic-graph) (VERTEX basic-vertex) &optional ERROR-IF-NOT-FOUND?

Source

graph.lisp (file)

Method: find-vertex (GRAPH basic-graph) VALUE &optional ERROR-IF-NOT-FOUND?

Source

graph.lisp (file)

Generic Function: find-vertex-if THING PREDICATE &key KEY

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: find-vertex-if (EDGE basic-edge) FN &key KEY

Source

graph.lisp (file)

Method: find-vertex-if (GRAPH basic-graph) FN &key KEY

Source

graph.lisp (file)

Generic Function: find-vertexes-if THING PREDICATE

Returns a list of vertexes in ‘thing‘ for which the ‘predicate‘ returns non-nil. [?? why no key function?]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: find-vertexes-if (GRAPH basic-graph) FN

Source

graph.lisp (file)

Generic Function: finish-time OBJECT

Generic Function: (setf finish-time) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: finish-time (BASIC-VERTEX basic-vertex)

Method: (setf finish-time) NEW-VALUE (BASIC-VERTEX basic-vertex)

‘Finish-time‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]

Source

graph.lisp (file)

Generic Function: force-undirected GRAPH

Ensures that the graph is undirected (possibly by calling change-class on the edges).

Package

cl-graph

Source

api.lisp (file)

Methods

Method: force-undirected (GRAPH basic-graph)

Source

graph.lisp (file)

Generic Function: generate-directed-free-tree GRAPH ROOT

Returns a version of graph which is a directed free tree rooted at root.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: generate-directed-free-tree (GRAPH basic-graph) ROOT

Source

graph.lisp (file)

Generic Function: graph OBJECT

Generic Function: (setf graph) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: graph (BASIC-EDGE basic-edge)

The ‘graph‘ of which this edge is a part.

Source

graph.lisp (file)

Method: graph (BASIC-VERTEX basic-vertex)

Method: (setf graph) NEW-VALUE (BASIC-VERTEX basic-vertex)

The graph in which this vertex is contained.

Source

graph.lisp (file)

Method: graph (CONDITION graph-error)

Source

graph.lisp (file)

Generic Function: graph->dot GRAPH OUTPUT &key GRAPH-FORMATTER VERTEX-KEY VERTEX-LABELER VERTEX-FORMATTER EDGE-LABELER EDGE-FORMATTER &allow-other-keys

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

Package

cl-graph

Source

api.lisp (file)

Methods

Method: graph->dot (G basic-graph) (STREAM pathname) &rest ARGS &key &allow-other-keys

Source

graphviz-support.lisp (file)

Method: graph->dot (G basic-graph) (STREAM string) &rest ARGS &key &allow-other-keys

Source

graphviz-support.lisp (file)

Method: graph->dot (G basic-graph) (STREAM (eql t)) &rest ARGS &key &allow-other-keys

Source

graphviz-support.lisp (file)

Method: graph->dot (G basic-graph) (STREAM (eql nil)) &rest ARGS &key &allow-other-keys

Source

graphviz-support.lisp (file)

Method: graph->dot (G basic-graph) (STREAM stream) &key GRAPH-FORMATTER VERTEX-KEY VERTEX-LABELER VERTEX-FORMATTER EDGE-LABELER EDGE-FORMATTER &allow-other-keys

Source

graphviz-support.lisp (file)

Generic Function: graph->dot-external GRAPH FILE-NAME &key TYPE &allow-other-keys

Package

cl-graph

Source

api.lisp (file)

Methods

Method: graph->dot-external (G 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*.

Source

graphviz-support.lisp (file)

Generic Function: graph->dot-properties G STREAM

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: graph->dot-properties (GRAPH dot-graph-mixin) STREAM

Source

graphviz-support.lisp (file)

Method: graph->dot-properties G STREAM

Source

graphviz-support.lisp (file)

Generic Function: graph-edge-mixture-matrix GRAPH VERTEX-CLASSIFIER &key EDGE-WEIGHT

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

Package

cl-graph

Source

api.lisp (file)

Generic Function: graph-edges OBJECT

Package

cl-graph

Methods

Method: graph-edges (BASIC-GRAPH basic-graph)

automatically generated reader method

Source

graph.lisp (file)

Generic Function: graph-mixing-matrix GRAPH VERTEX-CLASSIFIER &key EDGE-WEIGHT

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

Package

cl-graph

Source

api.lisp (file)

Generic Function: graph-roots GRAPH

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]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: graph-roots (GRAPH basic-graph)

Source

graph.lisp (file)

Generic Function: graph-vertexes OBJECT

Package

cl-graph

Methods

Method: graph-vertexes (BASIC-GRAPH basic-graph)

automatically generated reader method

Source

graph.lisp (file)

Generic Function: has-children-p VERTEX

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: has-children-p (VERTEX graph-container-vertex)

Source

graph-container.lisp (file)

Generic Function: has-parent-p 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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: has-parent-p (VERTEX graph-container-vertex)

Source

graph-container.lisp (file)

Generic Function: height-in-pixels THING

Generic Function: (setf height-in-pixels) VALUE THING

Package

cl-graph

Methods

Method: height-in-pixels (THING dot-vertex-mixin)

Return the attribute in pixels assuming 72 dpi

Source

graphviz-support.lisp (file)

Method: (setf height-in-pixels) VALUE (THING dot-vertex-mixin)

Set the attribute in pixels assuming 72 dpi

Source

graphviz-support.lisp (file)

Generic Function: in-cycle-p GRAPH START-VERTEX

Returns true if ‘start-vertex‘ is in some cycle in
‘graph‘. This uses child-vertexes to generate the vertexes adjacent to a vertex.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: in-cycle-p (GRAPH basic-graph) (START-VERTEX basic-vertex)

Source

graph.lisp (file)

Method: in-cycle-p (GRAPH basic-graph) VERTEX

Source

graph.lisp (file)

Generic Function: in-undirected-cycle-p GRAPH START-VERTEX &optional MARKED PREVIOUS

Return true if-and-only-if an undirected cycle in graph is reachable from start-vertex.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: in-undirected-cycle-p (GRAPH basic-graph) (CURRENT basic-vertex) &optional MARKED PREVIOUS

Source

graph.lisp (file)

Generic Function: iterate-edges GRAPH-OR-VERTEX FN

Calls ‘fn‘ on each edge of graph or vertex.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: iterate-edges (VERTEX graph-container-vertex) FN

Source

graph-container.lisp (file)

Method: iterate-edges (GRAPH graph-container) FN

Source

graph-container.lisp (file)

Generic Function: iterate-neighbors VERTEX FN

Calls fn on every vertex adjecent to vertex See also iterate-children and iterate-parents.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: iterate-neighbors (VERTEX graph-container-vertex) FN

Source

graph-container.lisp (file)

Generic Function: iterate-parents 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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: iterate-parents (VERTEX graph-container-vertex) FN

Source

graph-container.lisp (file)

Generic Function: iterate-source-edges 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‘.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: iterate-source-edges (VERTEX graph-container-vertex) FN

Source

graph-container.lisp (file)

Generic Function: iterate-target-edges 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‘.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: iterate-target-edges (VERTEX graph-container-vertex) FN

Source

graph-container.lisp (file)

Generic Function: iterate-vertexes THING FN

Calls ‘fn‘ on each of the vertexes of ‘thing‘.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: iterate-vertexes (EDGE basic-edge) FN

Source

graph.lisp (file)

Method: iterate-vertexes (GRAPH basic-graph) FN

Source

graph.lisp (file)

Generic Function: make-filtered-graph OLD-GRAPH TEST-FN &key GRAPH-COMPLETION-METHOD DEPTH NEW-GRAPH

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.

Package

cl-graph

Source

api.lisp (file)

Generic Function: make-graph GRAPH-TYPE &key &allow-other-keys

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: make-graph (GRAPH-TYPE symbol) &rest ARGS &key &allow-other-keys

Source

graph.lisp (file)

Generic Function: make-graph-from-vertexes VERTEX-LIST

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.

Package

cl-graph

Source

api.lisp (file)

Generic Function: make-vertex-edges-container VERTEX CONTAINER-CLASS &rest ARGS

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: make-vertex-edges-container (VERTEX graph-container-vertex) CONTAINER-CLASS &rest ARGS

Source

graph-container.lisp (file)

Generic Function: make-vertex-for-graph GRAPH &key VERTEX-CLASS &allow-other-keys

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: make-vertex-for-graph (GRAPH basic-graph) &rest ARGS &key VERTEX-CLASS &allow-other-keys

Source

graph.lisp (file)

Generic Function: minimum-spanning-tree GRAPH &key EDGE-SORTER

Returns a minimum spanning tree of graph if one exists and nil otherwise.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: minimum-spanning-tree (GRAPH basic-graph) &key EDGE-SORTER

Source

graph-algorithms.lisp (file)

Generic Function: neighbor-vertexes VERTEX &optional FILTER

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

Package

cl-graph

Source

api.lisp (file)

Methods

Method: neighbor-vertexes VERTEX &optional FILTER

Source

graph.lisp (file)

Generic Function: next-node OBJECT

Generic Function: (setf next-node) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: next-node (BASIC-VERTEX basic-vertex)

Method: (setf next-node) NEW-VALUE (BASIC-VERTEX basic-vertex)

‘Next-node‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]

Source

graph.lisp (file)

Generic Function: number-of-neighbors VERTEX

Returns the number of neighbors of
‘vertex‘ (cf. ‘neighbor-vertexes‘). [?? could be a defun]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: number-of-neighbors VERTEX

Source

graph.lisp (file)

Generic Function: other-vertex EDGE VALUE-OR-VERTEX

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]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: other-vertex (EDGE graph-container-edge) VALUE

Source

graph-container.lisp (file)

Method: other-vertex (EDGE graph-container-edge) (V graph-container-vertex)

Source

graph-container.lisp (file)

Generic Function: out-edge-for-vertex-p EDGE 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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: out-edge-for-vertex-p (EDGE basic-edge) (VERTEX basic-vertex)

Source

graph-algorithms.lisp (file)

Generic Function: parent-vertexes VERTEX &optional FILTER

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

Package

cl-graph

Source

api.lisp (file)

Methods

Method: parent-vertexes VERTEX &optional FILTER

Source

graph.lisp (file)

Generic Function: previous-node OBJECT

Generic Function: (setf previous-node) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: previous-node (BASIC-VERTEX basic-vertex)

Method: (setf previous-node) NEW-VALUE (BASIC-VERTEX basic-vertex)

‘Previous-node‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]

Source

graph.lisp (file)

Generic Function: project-bipartite-graph NEW-GRAPH EXISTING-GRAPH VERTEX-CLASS VERTEX-CLASSIFIER

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.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: project-bipartite-graph (NEW-GRAPH basic-graph) GRAPH VERTEX-CLASS VERTEX-CLASSIFIER

Source

graph.lisp (file)

Method: project-bipartite-graph (NEW-GRAPH symbol) GRAPH VERTEX-CLASS VERTEX-CLASSIFIER

Source

graph.lisp (file)

Generic Function: rank OBJECT

Generic Function: (setf rank) NEW-VALUE OBJECT

Package

cl-graph

Methods

Method: rank (BASIC-VERTEX basic-vertex)

Method: (setf rank) NEW-VALUE (BASIC-VERTEX basic-vertex)

The ‘rank‘ is used by some algorithms for bookkeeping. [?? Should be in a mixin]

Source

graph.lisp (file)

Generic Function: renumber-edges GRAPH

Assign a number to each edge in a graph in some unspecified order. [?? internal]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: renumber-edges (GRAPH basic-graph)

Source

graph.lisp (file)

Generic Function: renumber-vertexes GRAPH

Assign a number to each vertex in a graph in some unspecified order. [?? internal]

Package

cl-graph

Source

api.lisp (file)

Methods

Method: renumber-vertexes (GRAPH basic-graph)

Source

graph.lisp (file)

Generic Function: replace-vertex GRAPH OLD NEW

Replace vertex ‘old‘ in graph ‘graph‘ with vertex ‘new‘. The edge structure of the graph is maintained.

Package

cl-graph

Source

api.lisp (file)

Methods

Method: replace-vertex (GRAPH graph-container) (OLD basic-vertex) (NEW basic-vertex) after

Source

graph-container.lisp (file)

Method: replace-vertex (GRAPH graph-container) (OLD basic-vertex) (NEW basic-vertex) before

Source

graph-container.lisp (file)

Method: replace-vertex (GRAPH basic-graph) (OLD basic-vertex) (NEW basic-vertex)

Source

graph.lisp (file)

Generic Function: rooted-dfs GRAPH ROOT FN &key OUT-EDGE-SORTER

A variant of DFS that does not visit nodes that are unreachable from the ROOT.

Package

cl-graph

Source

graph-algorithms.lisp (file)

Methods

Method: rooted-dfs (GRAPH basic-graph) ROOT FN &key OUT-EDGE-SORTER

Method: rooted-dfs (GRAPH basic-graph) (ROOT basic-vertex) FN &key OUT-EDGE-SORTER

Generic Function: rootp VERTEX

Returns true if ‘vertex‘ is a root vertex (i.e., it has no incoming (source) edges).

Package

cl-graph

Source

api.lisp (file)

Methods

Method: rootp (VERTEX basic-vertex)

Source

graph.lisp (file)