Class Tinaa-Graph

Part of:

package tinaa

Default initargs

:default-edge-class → #:dot-attributes → #
:vertex-class → #:directed-edge-class → #
:undirected-edge-class → #:initial-size → #

Direct Superclass

dot-graph-mixin
graph-container

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

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.
dot-attributesInitargs::dot-attributes; Accessors:dot-attributes.
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.

Other 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
dfs-visit
dot-attribute-value
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.

ensure-valid-dot-attribute
find-connected-components

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

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

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-external
graph->dot-properties

Unless a different graph-formatter is specified,
this method is called by graph->dot to output ...

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
iterate-edges

Calls fn on each edge of graph or vertex.

iterate-vertexes

Calls fn on each of the vertexes of thing.

make-edge-container

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

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

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

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

setfdot-attribute-value
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.