Class Basic-Graph

This is the root class for all graphs in CL-Graph.

Part of:

package cl-graph, class graph-matrix, class graph-container

Default initargs

:initial-size → #

Direct Subclass

graph-container

A graph container is essentially an adjacency list graph representation [?? The Bad name comes fr...

graph-matrix

Stub for matrix based graph. Not implemented.

Slot

contains-directed-edge-p
Returns true if graph contains at least one directed edge. [?? Not sure if this is really keep up-to-date.]
Accessors:contains-directed-edge-p.
contains-undirected-edge-p
Returns true if graph contains at least one undirected edge. [?? Not sure if this is really keep up-to-date.]
Accessors:contains-undirected-edge-p.
default-edge-class
The default edge class for the graph.
Initargs::default-edge-class; Reader:default-edge-class.
default-edge-type
The default edge type for the graph. This should be one of :undirected or :directed.
Initargs::default-edge-type; Reader:default-edge-type.
directed-edge-class
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.
Initform:(quote basic-directed-edge), Initargs::directed-edge-class; Reader:directed-edge-class.
edge-keyInitform:(function identity), Initargs::edge-key; Reader:edge-key.
edge-testInitform:(function eq), Initargs::edge-test; Reader:edge-test.
graph-edgesInitargs::graph-edges; Reader:graph-edges.
graph-vertexesInitargs::graph-vertexes; Reader:graph-vertexes.
largest-edge-idInitform:0; Reader:largest-edge-id.
largest-vertex-idInitform:0; Reader:largest-vertex-id.
undirected-edge-class
The class used to create undirected edges in the graph. This must extend the base-class for edges of the graph type. E.g., all edges of a graph-container must extend graph-container-edge
Initform:(quote basic-edge), Initargs::undirected-edge-class; Reader:undirected-edge-class.
vertex-class
The class of the vertexes in the graph. This must extend the base-class for vertexes of the graph type. E.g., all vertexes of a graph-container must extend graph-container-vertex.
Initform:(quote basic-vertex), Initargs::vertex-class; Reader:vertex-class.
vertex-keyInitform:(function identity), Initargs::vertex-key; Reader:vertex-key.
vertex-testInitform:(function eq), Initargs::vertex-test; Reader:vertex-test.

Direct Method

add-edge

Add-edge adds an existing edge to a graph. As
add-edge-between-vertexes is generally more natur...

add-edge-between-vertexes

Adds an edge between two vertexes and returns it.
If force-new? is true, the edge is added even i...

add-edges-to-graph
add-vertex

Adds a vertex to a graph. If called with a vertex,
then this vertex is added. If called with a ...

adjacentp

Return true if vertex-1 and vertex-2 are connected
by an edge. [?? compare with vertices-share-...

any-undirected-cycle-p

Returns true if there are any undirected cycles in graph.

assign-level

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

breadth-first-search-graph
breadth-first-visitor
complete-links

Add edges between vertexes in the new-graph for
which the matching vertexes in the old-graph ha...

connected-component-count

Returns the number of connected-components of
graph.

connected-components

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

connected-graph-p

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

delete-all-edges

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

delete-edge

Delete the edge' from the graph' and returns it.

delete-edge-between-vertexes

Finds an edge in the graph between the two
specified vertexes. If values (i.e., non-vertexes) a...

delete-vertex

Remove a vertex from a graph. The 'vertex-or-value'
argument can be a vertex of the graph or a 'v...

depth

Returns the maximum depth of the vertexes in graph
assuming that the roots are of depth 0 and t...

dfs
edge-count

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

edges

Returns a list of the edges of thing.

empty!

Removes all items from the container and returns nil.

find-connected-components

Returns a list of sub-graphs of graph where each
sub-graph is a different connected component...

find-edge-between-vertexes

Searches graph for an edge that connects vertex-1
and vertex-2. [?? Ignores error-if-not-fou...

find-edge-if

Returns the first edge in thing for which the
predicate function returns non-nil. If the `k...

find-edges-if

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

find-vertex

Search 'graph' for a vertex with element
'value'. The search is fast but inflexible because it ...

find-vertex-if

Returns the first vertex in thing for which the
predicate function returns non-nil. If the ...

find-vertexes-if

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

force-undirected

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

generate-directed-free-tree

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

graph->dot

Generates a description of graph in DOT file format. The
formatting can be altered using `gr...

graph->dot-external
graph-roots

Returns a list of the roots of graph. A root is
defined as a vertex with no source edges (i.e.,...

in-cycle-p

Returns true if start-vertex is in some cycle in
graph. This uses child-vertexes to generat...

in-undirected-cycle-p

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

initialize-vertex-data
insert-item

Adds item to the container

iterate-elements
iterate-nodes

Applies function to each node in the container. If the container doesn't have nodes, then this is...

iterate-vertexes

Calls fn on each of the vertexes of thing.

make-edge-for-graph

It should not usually necessary to call this in
user code. Creates a new edge between vertex-1 ...

make-filtered-graph

Takes a GRAPH and a TEST-FN (a single argument
function returning NIL or non-NIL), and filters th...

make-vertex-for-graph

Creates a new vertex for graph graph. The keyword
arguments include:

* vertex-class : specif...

map-over-all-combinations-of-k-edges
map-over-all-combinations-of-k-vertexes
minimum-spanning-tree

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

project-bipartite-graph

Creates the unimodal bipartite projects of
existing-graph with vertexes for each vertex of existi...

renumber-edges

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

renumber-vertexes

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

replace-vertex

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

search-for-vertex

Search 'graph' for a vertex with element
'value'. The 'key' function is applied to each element...

size

Returns the number of items currently in the container.

subgraph-containing

Returns a new graph that is a subset of graph
that contains vertex and all of the other verte...

tag-all-edges

Sets the tag of all the edges of thing to
true. [?? why does this exist?]

topological-sort

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

traverse-elements

WIP

untag-all-edges

Sets the tag of all the edges of thing to nil.
[?? why does this exist?]

vertex-count

Returns the number of vertexes in graph. [??
could be a defun]

vertexes

Returns a list of the vertexes of thing.