In Mathematics and Computer Science, a *graph* is a collection of *vertexes* connected by *edges*. Edges may be *directed* or *undirected* (i.e., sometimes you really can't get there from here). Both edges and vertexes may have additional data associated with them. Graphs are useful because you can use them to represent most anything: food webs, hypertext, the world wide web, protein/protein interactions, language, who publishes with whom, etc.

CL-Graph is a general graph library built on cl-containers. It provides an open-ended API for building, examining and manipulating graphs as well as implementations of many of the usual suspects of graph algorithms and measures.

X
make-graph
graph-type &key &allow-other-keys

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

X
add-edges-to-graph
graph edges &key if-duplicate-do

function
X
add-vertex
graph value-or-vertex &key if-duplicate-do &allow-other-keys

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

X
add-edge
graph edge &rest args &key force-new?

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

X
add-edge-between-vertexes
graph value-or-vertex-1 value-or-vertex-2 &rest args &key if-duplicate-do edge-type &allow-other-keys

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

X
delete-edge
graph edge

function
Delete the

`edge' from the `

graph' and returns it.
X
delete-all-edges
graph

function
Delete all edges from `graph'. Returns the graph..

X
delete-edge-between-vertexes
graph value-or-vertex-1 value-or-vertex-2 &rest args

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

X
delete-vertex
graph value-or-vertex

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

X
replace-vertex
graph old new

function
Replace vertex

`old`

in graph `graph`

with vertex `new`

. The edge structure of the graph is maintained.
X
add-edge-to-vertex
edge vertex

function
Attaches the edge

`edge`

to the vertex `vertex`

.
X
make-vertex-container
graph initial-size

function
Make-vertex-container is called during graph creation and can be used to create specialized containers to hold graph vertexes.

X
make-edge-container
graph initial-size

function
Make-edge-container is called during graph creation and can be used to create specialized containers to hold graph edges.

X
make-edge-for-graph
graph vertex-1 vertex-2 &key edge-type edge-class &allow-other-keys

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

X
make-vertex-for-graph
graph &key &allow-other-keys

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

X
make-graph-from-vertexes
vertex-list

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

X
edge-count
vertex

function
Returns the number of edges attached to

`vertex`

. Compare with the more flexible `vertex-degree`

.
X
vertex-count
graph

function
Returns the number of vertexes in

`graph`

. [?? could be a defun]
X
source-edge-count
vertex

function
Returns the number of source edges of vertex (cf. source-edges). [?? could be a defun]

X
target-edge-count
vertex

function
Returns the number of target edges of vertex (cf. target-edges). [?? could be a defun]

X
number-of-neighbors
vertex

function
Returns the number of neighbors of

`vertex`

(cf. `neighbor-vertexes`

). [?? could be a defun]
X
has-children-p
vertex

function
In a directed graph, returns true if vertex has any edges that point from vertex to some other vertex (cf. iterate-target-edges). In an undirected graph,

`has-children-p`

is testing only whether or not the vertex has any edges.
X
has-parent-p
vertex

function
In a directed graph, returns true if vertex has any edges that point from some other vertex to this vertex (cf. iterate-source-edges). In an undirected graph,

`has-parent-p`

is testing only whether or not the vertex has any edges.
X
source-vertex
edge

function
Returns the source-vertex of a directed edge. Compare with

`vertex-1`

.
X
target-vertex
edge

function
Returns the target-vertex of a directed edge. Compare with

`vertex-2`

.
X
undirected-edge-p
edge

function
Returns true if-and-only-if edge is undirected

X
directed-edge-p
edge

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

X
make-vertex-edges-container
vertex container-class &rest args

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

X
other-vertex
edge value-or-vertex

function
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]
X
vertices-share-edge-p
vertex-1 vertex-2

function
Return true if vertex-1 and vertex-2 are connected by an edge. [?? Compare adjacentp]

X
out-edge-for-vertex-p
edge vertex

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

X
in-undirected-cycle-p
graph start-vertex &optional marked previous

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

X
adjacentp
graph vertex-1 vertex-2

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

X
depth
graph

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

X
edge-lessp-by-weight
edge-1 edge-2

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

X
edge-lessp-by-direction
edge-1 edge-2

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

X
weight
edge

function
Returns the weight of an edge. This defaults to 1.0 and can only be altered if the edge is a sub-class of

`weighted-edge-mixin`

.
X
rootp
vertex

function
Returns true if

`vertex`

is a root vertex (i.e., it has no incoming (source) edges).
X
in-cycle-p
graph start-vertex

function
Returns true if

`start-vertex`

is in some cycle in `graph`

. This uses child-vertexes to generate the vertexes adjacent to a vertex.
X
any-undirected-cycle-p
graph

function
Returns true if there are any undirected cycles in

`graph`

.
X
find-vertex
graph value &optional error-if-not-found?

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

X
search-for-vertex
graph value &key key test error-if-not-found?

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

X
find-edge
graph edge &optional error-if-not-found?

function
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?]
X
find-edge-between-vertexes
graph value-or-vertex-1 value-or-vertex-2 &key error-if-not-found?

function
Searches

`graph`

for an edge that connects vertex-1 and vertex-2. [?? Ignores error-if-not-found? Does directedness matter? need test]
X
find-vertex-if
thing predicate &key key

function
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.
X
find-edge-if
graph fn &key key

function
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.
X
find-edges-if
thing predicate

function
Returns a list of edges in

`thing`

for which the `predicate`

returns non-nil. [?? why no key function?]
X
find-vertexes-if
thing predicate

function
Returns a list of vertexes in

`thing`

for which the `predicate`

returns non-nil. [?? why no key function?]
X
find-edge-between-vertexes-if
graph value-or-vertex-1 value-or-vertex-2 fn &key error-if-not-found?

function
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.]
X
connected-components
graph

function
Returns a union-find-container representing the connected-components of

`graph`

.
X
connected-component-count
graph

function
Returns the number of connected-components of graph.

X
find-connected-components
graph

function
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.
X
connected-graph-p
graph &key edge-sorter

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

X
breadth-first-visitor
graph source fn

function
X
breadth-first-search-graph
graph source

function
X
dfs
graph root fn &key out-edge-sorter

function
X
dfs-visit
graph u fn sorter

function
X
dfs-tree-edge-p
edge

function
X
dfs-back-edge-p
edge

function
X
dfs-forward-edge-p
edge

function
X
dfs-cross-edge-p
edge

function
X
dfs-edge-type
edge

function
X
mst-find-set
vertex

function
X
mst-make-set
vertex

function
X
mst-tree-union
v1 v2

function
X
mst-link
v1 v2

function
X
minimum-spanning-tree
graph &key edge-sorter

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

X
generate-directed-free-tree
graph root

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

X
project-bipartite-graph
new-graph existing-graph vertex-class vertex-classifier

function
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.
X
traverse-elements
thing style fn

function
WIP

X
traverse-elements-helper
thing style marker fn

function
WIP

X
assortativity-coefficient
mixing-matrix

nil
No documentation found

X
graph-roots
graph

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

X
topological-sort
graph

function
Returns a list of vertexes sorted by the depth from the roots of the graph. See also assign-level and graph-roots.

X
assign-level
vertex level

function
Sets the depth of

`vertex`

to level and then recursively sets the depth of all of the children of `vertex`

to (1+ level).
X
iterate-children
node fn

function
Calls

`fn`

on every child of `node`

.
X
iterate-parents
vertex fn

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

X
iterate-neighbors
vertex fn

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

X
iterate-edges
graph-or-vertex fn

function
Calls

`fn`

on each edge of graph or vertex.
X
iterate-source-edges
vertex fn

function
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`

.
X
iterate-target-edges
vertex fn

function
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`

.
X
source-edges
vertex &optional filter

function
Returns a list of the source edges of

`vertex`

. I.e., the edges that begin at `vertex`

.
X
target-edges
vertex &optional filter

function
Returns a list of the target edges of

`vertex`

. I.e., the edges that end at `vertex`

.
X
child-vertexes
vertex &optional filter

function
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].
X
parent-vertexes
vertex &optional filter

function
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].
X
neighbor-vertexes
vertex &optional filter

function
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].
X
iterate-vertexes
thing fn

function
Calls

`fn`

on each of the vertexes of `thing`

.
X
edges
thing

function
Returns a list of the edges of

`thing`

.
X
vertexes
thing

function
Returns a list of the vertexes of

`thing`

.
X
graph->dot
graph output &key graph-formatter vertex-key vertex-labeler vertex-formatter edge-labeler edge-formatter

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

X
graph->dot-properties
g stream

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

X
vertex->dot
vertex stream

function
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.
X
edge->dot
edge stream

function
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.
X
dot-attribute-value
attribute thing

function
X
graph->dot-external
graph file-name &key type

function
Generate an external represenation of a graph to a file, by running the program in *dot-path*.

X
ensure-valid-dot-attribute
key object

function
X
write-name-for-dot
attribute stream

function
Requires cl-variants.

X
generate-gnm
generator graph n m &key

nil
No documentation found

X
generate-gnp
generator graph n p &key

nil
No documentation found

X
generate-undirected-graph-via-assortativity-matrix
generator graph-class size edge-count kind-matrix assortativity-matrix vertex-labeler &key

nil
No documentation found

X
generate-undirected-graph-via-vertex-probabilities
generator graph-class size kind-matrix probability-matrix vertex-labeler

nil
No documentation found

X
generate-scale-free-graph
generator graph size kind-matrix add-edge-count other-vertex-kind-samplers vertex-labeler &key

nil
No documentation found

X
generate-assortative-graph-with-degree-distributions
generator graph edge-count assortativity-matrix average-degrees degree-distributions vertex-labeler &key

nil
No documentation found

X
generate-simple-preferential-attachment-graph
generator graph size minimum-degree

nil
No documentation found

X
generate-preferential-attachment-graph
generator graph size kind-matrix minimum-degree assortativity-matrix &key

nil
No documentation found

X
graph-edge-mixture-matrix
graph vertex-classifier &key edge-weight

nil
No documentation found

X
graph-mixing-matrix
graph vertex-classifier &key edge-weight

nil
No documentation found

X
force-undirected
graph

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

X
renumber-vertexes
graph

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

X
renumber-edges
graph

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

X
initialize-vertex-data
graph

function
X
complete-links
new-graph old-graph

function
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`

.
X
subgraph-containing
graph vertex &key depth new-graph

function
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.]
X
make-filtered-graph
old-graph test-fn &key graph-completion-method depth new-graph

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

X
map-over-all-combinations-of-k-vertexes
graph k fn

function
X
map-over-all-combinations-of-k-edges
vertex k fn

function
X
tag-edges
edges

function
Sets the

`tag`

of all the edges of `thing`

to true. [?? why does this exist?]
X
tag-all-edges
thing

function
Sets the

`tag`

of all the edges of `thing`

to true. [?? why does this exist?]
X
untag-edges
edges

function
Sets the

`tag`

of all the edges of `thing`

to true. [?? why does this exist?]
X
untag-all-edges
thing

function
Sets the

`tag`

of all the edges of `thing`

to nil. [?? why does this exist?]
X
tagged-edge-p
edge

function
Returns true if-and-only-if edge's tag slot is t

X
untagged-edge-p
edge

function
Returns true if-and-only-if edge's tage slot is nil

- add-edge
- add-edge-between-vertexes
- add-edge-to-vertex
- add-edges-to-graph
- add-vertex
- adjacentp
- any-undirected-cycle-p
- assign-level
- breadth-first-search-graph
- breadth-first-visitor
- child-vertexes
- complete-links
- connected-component-count
- connected-components
- connected-graph-p
- delete-all-edges
- delete-edge
- delete-edge-between-vertexes
- delete-vertex
- depth
- dfs
- dfs-back-edge-p
- dfs-cross-edge-p
- dfs-edge-type
- dfs-forward-edge-p
- dfs-tree-edge-p
- dfs-visit
- directed-edge-p
- dot-attribute-value
- edge->dot
- edge-count
- edge-lessp-by-direction
- edge-lessp-by-weight
- edges
- ensure-valid-dot-attribute
- find-connected-components
- find-edge
- find-edge-between-vertexes
- find-edge-between-vertexes-if
- find-edge-if
- find-edges-if
- find-vertex
- find-vertex-if
- find-vertexes-if
- force-undirected
- generate-directed-free-tree
- graph->dot
- graph->dot-external
- graph->dot-properties
- graph-roots
- has-children-p
- has-parent-p
- in-cycle-p
- in-undirected-cycle-p
- initialize-vertex-data
- iterate-children
- iterate-edges
- iterate-neighbors
- iterate-parents
- iterate-source-edges
- iterate-target-edges
- iterate-vertexes
- make-edge-container
- make-edge-for-graph
- make-filtered-graph
- make-graph
- make-graph-from-vertexes
- make-vertex-container
- make-vertex-edges-container
- make-vertex-for-graph
- map-over-all-combinations-of-k-edges
- map-over-all-combinations-of-k-vertexes
- minimum-spanning-tree
- mst-find-set
- mst-link
- mst-make-set
- mst-tree-union
- neighbor-vertexes
- number-of-neighbors
- other-vertex
- out-edge-for-vertex-p
- parent-vertexes
- project-bipartite-graph
- renumber-edges
- renumber-vertexes
- replace-vertex
- rootp
- search-for-vertex
- source-edge-count
- source-edges
- source-vertex
- subgraph-containing
- tag-all-edges
- tag-edges
- tagged-edge-p
- target-edge-count
- target-edges
- target-vertex
- topological-sort
- traverse-elements
- traverse-elements-helper
- undirected-edge-p
- untag-all-edges
- untag-edges
- untagged-edge-p
- vertex->dot
- vertex-count
- vertexes
- vertices-share-edge-p
- weight
- write-name-for-dot