This is the epigraph Reference Manual, version 0.0.2, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Feb 26 16:21:41 2024 GMT+0.
The main system appears first, followed by any subsystem dependency.
epigraphA library for representing and processing graphs (nodes and edges)
Cyrus Harmon <ch-lisp@bobobeach.com>
BSD
0.0.2
alexandria (system).
copyright (file).
readme (file).
package.lisp (file).
utilities.lisp (file).
epigraph.lisp (file).
simple-edge-list-graph.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
epigraph/epigraph.asdepigraph/package.lispepigraph/utilities.lispepigraph/epigraph.lispepigraph/simple-edge-list-graph.lispepigraph/package.lispepigraph/utilities.lisppackage.lisp (file).
epigraph (system).
carhash (function).
remove-keyword-args (function).
epigraph/epigraph.lisputilities.lisp (file).
epigraph (system).
*default-edge-class* (special variable).
*default-graph-class* (special variable).
add-edge (generic function).
add-edge-between-nodes (generic function).
add-node (generic function).
bfs (generic function).
bfs-map (generic function).
bfs-map-edges (generic function).
break-cycles (function).
copy-edge (generic function).
copy-graph (generic function).
dfs (generic function).
dfs-map (generic function).
dfs-map-edges (generic function).
edge (class).
edge-data (reader method).
(setf edge-data) (writer method).
edgep (generic function).
edges (generic function).
edges-nodes-equal (generic function).
find-connected-components (function).
find-cycle (function).
find-cycle-edges (function).
find-edges-containing (generic function).
find-edges-from (generic function).
find-edges-to (generic function).
find-longest-path (function).
find-longest-paths (function).
first-node (generic function).
graph (class).
graph-distance (function).
graph-distance-hash-table (function).
graph-distance-matrix (function).
make-graph (function).
map-edges (generic function).
map-edges->list (generic function).
map-nodes (generic function).
map-nodes->list (generic function).
neighbors (generic function).
node-count (generic function).
node-equal (function).
node-find (function).
node-position (function).
node-remove (function).
node1 (reader method).
(setf node1) (writer method).
node2 (reader method).
(setf node2) (writer method).
nodes (generic function).
other-edge-node (generic function).
print-edge-data (generic function).
print-object (method).
remove-connected-component (function).
remove-edge (generic function).
remove-edge-between-nodes (generic function).
remove-node (generic function).
self-edge-p (generic function).
*bfs-depth* (special variable).
*dfs-depth* (special variable).
bfs2 (method).
dfs2 (method).
find-self-edges (generic function).
floyd-warshall (function).
graph-node-p (generic function).
graph-node-test (reader method).
(setf graph-node-test) (writer method).
graph-search (method).
make-node-hash-table (function).
makeq (function).
neighbors-and-edges (method).
q (class).
qappend (generic function).
qitems (reader method).
(setf qitems) (writer method).
qlast (reader method).
(setf qlast) (writer method).
qpop (generic function).
qpush (generic function).
epigraph/simple-edge-list-graph.lispepigraph.lisp (file).
epigraph (system).
add-edge (method).
add-edge-between-nodes (method).
add-node (method).
copy-graph (method).
edgep (method).
edges (method).
find-edges-containing (method).
find-edges-from (method).
find-edges-to (method).
first-node (method).
map-edges (method).
map-edges->list (method).
map-nodes (method).
map-nodes->list (method).
node-count (method).
nodes (method).
remove-edge (method).
remove-edge-between-nodes (method).
remove-node (method).
self-edge-p (method).
simple-edge-list-graph (class).
find-edge (method).
find-self-edges (method).
graph-edge-list (reader method).
(setf graph-edge-list) (writer method).
graph-node-hash (reader method).
(setf graph-node-hash) (writer method).
graph-node-p (method).
with-graph-iterator (macro).
Packages are listed by definition order.
epigraphgraph
common-lisp.
*default-edge-class* (special variable).
*default-graph-class* (special variable).
add-edge (generic function).
add-edge-between-nodes (generic function).
add-node (generic function).
bfs (generic function).
bfs-map (generic function).
bfs-map-edges (generic function).
break-cycles (function).
copy-edge (generic function).
copy-graph (generic function).
dfs (generic function).
dfs-map (generic function).
dfs-map-edges (generic function).
edge (class).
edge-data (generic reader).
(setf edge-data) (generic writer).
edgep (generic function).
edges (generic function).
edges-nodes-equal (generic function).
find-connected-components (function).
find-cycle (function).
find-cycle-edges (function).
find-edges-containing (generic function).
find-edges-from (generic function).
find-edges-to (generic function).
find-longest-path (function).
find-longest-paths (function).
first-node (generic function).
graph (class).
graph-distance (function).
graph-distance-hash-table (function).
graph-distance-matrix (function).
make-graph (function).
map-edges (generic function).
map-edges->list (generic function).
map-nodes (generic function).
map-nodes->list (generic function).
neighbors (generic function).
node-count (generic function).
node-equal (function).
node-find (function).
node-position (function).
node-remove (function).
node1 (generic reader).
(setf node1) (generic writer).
node2 (generic reader).
(setf node2) (generic writer).
nodes (generic function).
other-edge-node (generic function).
print-edge-data (generic function).
remove-connected-component (function).
remove-edge (generic function).
remove-edge-between-nodes (generic function).
remove-node (generic function).
self-edge-p (generic function).
simple-edge-list-graph (class).
*bfs-depth* (special variable).
*dfs-depth* (special variable).
bfs2 (generic function).
carhash (function).
dfs2 (generic function).
find-edge (generic function).
find-self-edges (generic function).
floyd-warshall (function).
graph-edge-list (generic reader).
(setf graph-edge-list) (generic writer).
graph-node-hash (generic reader).
(setf graph-node-hash) (generic writer).
graph-node-p (generic function).
graph-node-test (generic reader).
(setf graph-node-test) (generic writer).
graph-search (generic function).
make-node-hash-table (function).
makeq (function).
neighbors-and-edges (generic function).
q (class).
qappend (generic function).
qitems (generic reader).
(setf qitems) (generic writer).
qlast (generic reader).
(setf qlast) (generic writer).
qpop (generic function).
qpush (generic function).
remove-keyword-args (function).
with-graph-iterator (macro).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Finds all of the cycles in a graph and returns four VALUEs, a list of the edges that make complete the cycles, a list of the paths that form the cycles, a list of the cycle-forming edges, and a copy of GRAPH, with the cycle-forming edges removed.
Finds a cycle in graph, if one exists, using depth-first-search and returns two VALUES, a list of the edges in the cycle, and a list of the nodes in the cycle.
Returns a single vector containing a longest path reachable from any node in graph. The vector contains the elements in path order, starting with the first node and ending in the most distant node on the path.
Finds a longest path acecssible from each node in the
graph. Returns a list of vectors containing the longest paths for each
node. Each vector represents the path to the farthest node from the
first node of the vector to the last node of the vector.
Returns the (shortest) number of edges between node1 and node2. If node1 is node2, the distance is 0.
Returns a hash-table where each value is another hash-table, where each value is the distance from the node that is the key of the first hash-table to the node that is the key of the second hash-table.
Returns two values, an array where each entry i,j is the distance from node i to node j (distance from a node to itself is 0) and an array of nodes in the order corresponding to a dimension of the array of distances.
Creates a GRAPH instance whose actual class will either be specified by GRAPH-CLASS or by *DEFAULT-GRAPH-CLASS*.
Adds an edge to the graph.
simple-edge-list-graph) (edge edge)) ¶Creates an edge from node1 to node2, adds it to the graph, and returns the edge.
simple-edge-list-graph) node1 node2 &key edge-class) ¶Add a node to the graph.
simple-edge-list-graph) node) ¶Performs a breadth-first-search on graph starting
at start and returns a path end if end is reachable from start,
otherwise returns NIL. [DOCUMENT KEY AND TEST ARGS PLEASE!]
Performs a breadth-first-search on graph starting
at start until node end is found, if it is specified, calling fn, a
function of one argument, for each node as it is found. [DOCUMENT
KEY AND TEST ARGS PLEASE!]
Performs a breadth-first-search on graph, starting
at start until node end is found, if it is specified, calling fn, a
function of one argument, for each edge as it is found. [DOCUMENT
KEY AND TEST ARGS PLEASE!]
Returns a copy of the edge.
Returns a copy of the graph which will contain the
same nodes as the original graph and either the same edges as graph
or copies of the edges, depending on the value of &key copy-edges.
simple-edge-list-graph) &key copy-edges) ¶Performs a depth-first-search on graph, starting at
start and returns a path end if end is reachable from start,
otherwise returns NIL. [DOCUMENT KEY AND TEST ARGS PLEASE!]
Performs a depth-first-search on graph, starting at
start until node end is found, if it is specified, calling fn, a
function of one argument, for each node as it is found. [DOCUMENT
KEY AND TEST ARGS PLEASE!]
Performs a depth-first-search on graph, starting at
start until node end is found, if it is specified, calling fn, a
function of one argument, for each edge as it is found. [DOCUMENT
KEY AND TEST ARGS PLEASE!]
Returns the edge that connects node1 and node2 in
graph if the edge is present in the graph, otherwise returns NIL.
simple-edge-list-graph) node1 node2) ¶Returns the edges of graph. Currently the
format in which the edges are returned is not specified.
simple-edge-list-graph)) ¶Returns T if the two edges connect the same
nodes. Note that currently there is no notion of direction between
edges, so edges from A to B and from B to A are equivalent and
therefore edges-nodes-equal returns T for those two edges.
Returns a list of the edges in graph that start or end with node.
simple-edge-list-graph) node &key test) ¶Returns a list of the edges in graph that begin with node.
simple-edge-list-graph) node &key test) ¶Returns a list of the edges in graph that end with node.
simple-edge-list-graph) node &key test) ¶Returns the first node in a graph. Note that not
all graphs are rquired to support this function and that even graphs
that do support this might not have a consistent ordering of the
nodes such that successive first-node calls might not return the
same node.
simple-edge-list-graph)) ¶Calls fn, a function of one argument, for each edge in graph in an unspecified order.
simple-edge-list-graph)) ¶Calls fn, a function of one argument, for each edge
in graph in an unspecified order and accumulates the return first
returned values of fn in a list.
simple-edge-list-graph)) ¶Calls FN on every node in the graph, without regard to the configuration of the graph.
simple-edge-list-graph)) ¶Calls FN on every node in the graph, without regard
to the configuration of the graph and returns the resulting values
in a list.
simple-edge-list-graph)) ¶Returns a list of the nodes that are connected to node.
Returns the number of nodes in graph.
simple-edge-list-graph)) ¶Returns the nodes of graph. Currently the
format in which the nodes are returned is not specified.
simple-edge-list-graph)) ¶Returns the other node in the edge. That is if
there is an edge between A and B, other-edge-node of A would return
B. If the edge is a self-edge, returns node.
Prints data about a given edge. This function is
called from the print-object method specialied on EDGE objects. To
add additional data to be printed by subclasses of edge create
an :AFTER method on PRINT-EDGE-DATA.
Removes edge from the graph.
simple-edge-list-graph) (edge edge) &key test) ¶Removes the edge from node1 to node2 in the graph.
simple-edge-list-graph) node1 node2) ¶Remove a node from the graph.
simple-edge-list-graph) node) ¶Returns true if the edge connects a given node to itself.
simple-edge-list-graph) edge &key test) ¶Instances of the EDGE class represent edges between nodes in a graph.
The protocol class of graphs. The intent is that
there will be concrete subclasses of GRAPH with different
implementations of storing the nodes and edges.
(quote eql)
:node-test
A concrete subclass of graph that represents the edges in the graph with a list of edges between nodes.
add-edge.
add-edge-between-nodes.
add-node.
copy-graph.
edgep.
edges.
find-edge.
find-edges-containing.
find-edges-from.
find-edges-to.
find-self-edges.
first-node.
(setf graph-edge-list).
graph-edge-list.
(setf graph-node-hash).
graph-node-hash.
graph-node-p.
map-edges.
map-edges->list.
map-nodes.
map-nodes->list.
node-count.
nodes.
remove-edge.
remove-edge-between-nodes.
remove-node.
self-edge-p.
(make-hash-table :test (quote equal))
:nodes
:edges
simple-edge-list-graph) node1 node2) ¶Returns a list of the edges in graph that begin and end with node.
simple-edge-list-graph) node &key test) ¶simple-edge-list-graph)) ¶automatically generated reader method
simple-edge-list-graph)) ¶automatically generated writer method
simple-edge-list-graph)) ¶automatically generated reader method
simple-edge-list-graph)) ¶automatically generated writer method
Returns t if node is a node in graph.
simple-edge-list-graph) node) ¶| Jump to: | (
A B C D E F G M N O P Q R S W |
|---|
| Jump to: | (
A B C D E F G M N O P Q R S W |
|---|
| Jump to: | *
D E I L N S |
|---|
| Jump to: | *
D E I L N S |
|---|
| Jump to: | C E F G P Q R S U |
|---|
| Jump to: | C E F G P Q R S U |
|---|