Class Graph-Container

A graph container is essentially an adjacency list graph representation [?? The Bad name comes from it being implemented with containers... ugh]

Part of:

class tinaa-part-graph, class tinaa-graph, package cl-graph, class basic-graph, class dot-graph

Default initargs

:vertex-class → #:directed-edge-class → #
:undirected-edge-class → #:initial-size → #

Direct Superclass

basic-graph

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

container-uses-nodes-mixin
initial-contents-mixin
iteratable-container-mixin
non-associative-container-mixin

A non associative container should implement at least empty-p,
empty, insert-item and delete-item...

Direct Subclass

dot-graph

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.
testInitform:(function equal), Initargs::test.
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-pair->edgeInitform:(make-container (quote simple-associative-container) test (function equal)); Reader:vertex-pair->edge.
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...

delete-all-edges

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

delete-edge

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

dfs-visit
edge-count

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

empty!

Removes all items from the container and returns nil.

find-edge

Search graph for an edge whose vertexes match
edge. This means that vertex-1 of the edge ...

find-edge-between-vertexes

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

find-edge-between-vertexes-if

Finds and returns an edge between value-or-vertex-1
and value-or-vertex-2 if one exists. Unless...

iterate-edges

Calls fn on each edge of graph or vertex.

make-edge-container

Make-edge-container is called during graph creation
and can be used to create specialized conta...

make-node-for-container
make-vertex-container

Make-vertex-container is called during graph
creation and can be used to create specialized con...

Other Method

%operate-after-finding
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-initial-contents
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 ...

best-item

Returns the item in items with the 'best' value of function where
'best' is determined by test. Y...

breadth-first-search-graph
breadth-first-visitor
collect-elements

Returns a possibly filtered and possibly transformed list of the elements in a container. If the ...

collect-elements-stably
collect-nodes

Returns a possibly filtered and possibly transformed list
of the nodes in a container. If the con...

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.

count-elements
count-elements-if
count-items
delete-edge-between-vertexes

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

delete-element
delete-item
delete-item-if
delete-list

Deletes each item in the list from the container.

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
edges

Returns a list of the edges of thing.

element-position

Returns the position of element in container using test and
key to match. Key defaults to identit...

every-element-p
every-item-p

Returns true if every item in the container satisfies the
predicate. Predicate should be a funct...

find-connected-components

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

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-element

For now, compare find-item.

find-item

Find item in container using the container's test
method for comparisons. The test method must ta...

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

first-element
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-initial-contents-p

Returns true if this container type should rely on the default behavior of basic-initial-contents...

insert-item

Adds item to the container

insert-list

Adds each item in the list to the container in an
upspecified order.

insert-new-item

Adds item to the container unless it is already there

insert-sequence

Adds each item in the sequence to the container in an
upspecified order.

iteratable-p

Returns true if thing knows how to iterate-nodes.

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.

nth-element

Returns the nth element in the container's 'natural' order.

predecessor

Return the item that comes before item in the container. Only makes sense for sorted containers...

print-container

Prints the contents of container (using PRINT). Returns the container.

project-bipartite-graph

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

reduce-container
reduce-elements
reduce-nodes
remove-items-if

Removes items from a container that satisfy the test. The
container is returned.

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-element
search-for-item

Hunt for the item in the container. Key and Test
are as in member.

search-for-match

Hunt for an item in the container that satisfies
the predicate. Key is as in count-if.

search-for-matching-node
search-for-node
search-for-node*
search-for-vertex

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

setffirst-element
size

Returns the number of items currently in the container.

some-element-p
some-item-p

Returns the first item in the container for which predicate
holds. Predicate should be a function...

subgraph-containing

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

successor

Return the item that comes after item in the container. Only makes sense for sorted containers. R...

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

unique-elements
unique-nodes
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.