The epigraph Reference Manual

Table of Contents

The epigraph Reference Manual

This is the epigraph Reference Manual, version 0.0.2, generated automatically by Declt version 3.0 "Montgomery Scott" on Fri Jun 26 11:01:00 2020 GMT+0.

1 Introduction

epigraph, a library for manipulating graphs in common lisp. Cyrus Harmon ch-lisp@bobobeach.com

Epigraph is a common lisp package for representing graph, that is sets of nodes that may contain edges between the various nodes.

Example

(defparameter graph (let ((g (make-graph :node-test 'equal)))

(loop for i from 1 below 12
   do (add-node g (concatenate 'string "Node " (princ-to-string i))))

(add-edge-between-nodes g "Node 1" "Node 2")
(add-edge-between-nodes g "Node 1" "Node 3")
(add-edge-between-nodes g "Node 3" "Node 4")
(add-edge-between-nodes g "Node 3" "Node 5")
(add-edge-between-nodes g "Node 2" "Node 6")
(add-edge-between-nodes g "Node 6" "Node 7")
(add-edge-between-nodes g "Node 6" "Node 8")
(add-edge-between-nodes g "Node 4" "Node 9")
(add-edge-between-nodes g "Node 5" "Node 10")
(add-edge-between-nodes g "Node 5" "Node 11")
(add-edge-between-nodes g "Node 1" "Node 11")
(add-edge-between-nodes g "Node 8" "Node 7")
g))

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 epigraph

Author

Cyrus Harmon <ch-lisp@bobobeach.com>

License

BSD

Description

A library for representing and processing graphs (nodes and edges)

Version

0.0.2

Dependency

alexandria

Source

epigraph.asd (file)

Components

• copyright (file)
• readme (file)
• package.lisp (file)
• utilities.lisp (file)
• epigraph.lisp (file)
• simple-edge-list-graph.lisp (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 epigraph.asd

Location

epigraph.asd

Systems

epigraph (system)

3.1.2 epigraph/package.lisp

Dependency

readme (file)

Parent

epigraph (system)

Location

package.lisp

Packages

epigraph

3.1.3 epigraph/utilities.lisp

Dependency

package.lisp (file)

Parent

epigraph (system)

Location

utilities.lisp

Internal Definitions

• carhash (function)
• remove-keyword-args (function)

3.1.4 epigraph/epigraph.lisp

Dependency

utilities.lisp (file)

Parent

epigraph (system)

Location

epigraph.lisp

Exported Definitions

• *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 (method)
• bfs-map (generic function)
• bfs-map (method)
• bfs-map-edges (generic function)
• bfs-map-edges (method)
• break-cycles (function)
• copy-edge (generic function)
• copy-edge (method)
• copy-graph (generic function)
• dfs (generic function)
• dfs (method)
• dfs-map (generic function)
• dfs-map (method)
• dfs-map-edges (generic function)
• dfs-map-edges (method)
• edge (class)
• edge-data (method)
• (setf edge-data) (method)
• edgep (generic function)
• edges (generic function)
• edges-nodes-equal (generic function)
• edges-nodes-equal (method)
• 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)
• neighbors (method)
• node-count (generic function)
• node-equal (function)
• node-find (function)
• node-position (function)
• node-remove (function)
• node1 (method)
• (setf node1) (method)
• node2 (method)
• (setf node2) (method)
• nodes (generic function)
• nodes (method)
• other-edge-node (generic function)
• other-edge-node (method)
• print-edge-data (generic function)
• print-edge-data (method)
• remove-connected-component (function)
• remove-edge (generic function)
• remove-edge-between-nodes (generic function)
• remove-node (generic function)
• self-edge-p (generic function)

Internal Definitions

• *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 (method)
• (setf graph-node-test) (method)
• graph-search (method)
• make-node-hash-table (function)
• makeq (function)
• neighbors-and-edges (method)
• q (class)
• qappend (generic function)
• qappend (method)
• qitems (method)
• (setf qitems) (method)
• qlast (method)
• (setf qlast) (method)
• qpop (generic function)
• qpop (method)
• qpush (generic function)
• qpush (method)

3.1.5 epigraph/simple-edge-list-graph.lisp

Dependency

epigraph.lisp (file)

Parent

epigraph (system)

Location

simple-edge-list-graph.lisp

Exported Definitions

• 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)

Internal Definitions

• find-edge (method)
• find-self-edges (method)
• graph-edge-list (method)
• (setf graph-edge-list) (method)
• graph-node-hash (method)
• (setf graph-node-hash) (method)
• graph-node-p (method)
• with-graph-iterator (macro)

3.2 Static

3.2.1 epigraph/COPYRIGHT

Parent

epigraph (system)

Location

COPYRIGHT

3.2.2 epigraph/README

Dependency

copyright (file)

Parent

epigraph (system)

Location

/home/quickref/quicklisp/dists/quicklisp/software/epigraph-20200325-git/README (not found)

4 Packages

Packages are listed by definition order.

4.1 epigraph

Source

package.lisp (file)

Nickname

graph

Use List

common-lisp

Exported Definitions

• *default-edge-class* (special variable)
• *default-graph-class* (special variable)
• add-edge (generic function)
• add-edge (method)
• add-edge-between-nodes (generic function)
• add-edge-between-nodes (method)
• add-node (generic function)
• add-node (method)
• bfs (generic function)
• bfs (method)
• bfs-map (generic function)
• bfs-map (method)
• bfs-map-edges (generic function)
• bfs-map-edges (method)
• break-cycles (function)
• copy-edge (generic function)
• copy-edge (method)
• copy-graph (generic function)
• copy-graph (method)
• dfs (generic function)
• dfs (method)
• dfs-map (generic function)
• dfs-map (method)
• dfs-map-edges (generic function)
• dfs-map-edges (method)
• edge (class)
• edge-data (generic function)
• edge-data (method)
• (setf edge-data) (method)
• (setf edge-data) (generic function)
• edgep (generic function)
• edgep (method)
• edges (generic function)
• edges (method)
• edges-nodes-equal (generic function)
• edges-nodes-equal (method)
• find-connected-components (function)
• find-cycle (function)
• find-cycle-edges (function)
• find-edges-containing (generic function)
• find-edges-containing (method)
• find-edges-from (generic function)
• find-edges-from (method)
• find-edges-to (generic function)
• find-edges-to (method)
• find-longest-path (function)
• find-longest-paths (function)
• first-node (generic function)
• first-node (method)
• graph (class)
• graph-distance (function)
• graph-distance-hash-table (function)
• graph-distance-matrix (function)
• make-graph (function)
• map-edges (generic function)
• map-edges (method)
• map-edges->list (generic function)
• map-edges->list (method)
• map-nodes (generic function)
• map-nodes (method)
• map-nodes->list (generic function)
• map-nodes->list (method)
• neighbors (generic function)
• neighbors (method)
• node-count (generic function)
• node-count (method)
• node-equal (function)
• node-find (function)
• node-position (function)
• node-remove (function)
• node1 (generic function)
• node1 (method)
• (setf node1) (method)
• (setf node1) (generic function)
• node2 (generic function)
• node2 (method)
• (setf node2) (method)
• (setf node2) (generic function)
• nodes (generic function)
• nodes (method)
• nodes (method)
• other-edge-node (generic function)
• other-edge-node (method)
• print-edge-data (generic function)
• print-edge-data (method)
• remove-connected-component (function)
• remove-edge (generic function)
• remove-edge (method)
• remove-edge-between-nodes (generic function)
• remove-edge-between-nodes (method)
• remove-node (generic function)
• remove-node (method)
• self-edge-p (generic function)
• self-edge-p (method)
• simple-edge-list-graph (class)

Internal Definitions

• *bfs-depth* (special variable)
• *dfs-depth* (special variable)
• bfs2 (generic function)
• bfs2 (method)
• carhash (function)
• dfs2 (generic function)
• dfs2 (method)
• find-edge (generic function)
• find-edge (method)
• find-self-edges (generic function)
• find-self-edges (method)
• floyd-warshall (function)
• graph-edge-list (generic function)
• graph-edge-list (method)
• (setf graph-edge-list) (method)
• (setf graph-edge-list) (generic function)
• graph-node-hash (generic function)
• graph-node-hash (method)
• (setf graph-node-hash) (method)
• (setf graph-node-hash) (generic function)
• graph-node-p (generic function)
• graph-node-p (method)
• graph-node-test (generic function)
• graph-node-test (method)
• (setf graph-node-test) (method)
• (setf graph-node-test) (generic function)
• graph-search (generic function)
• graph-search (method)
• make-node-hash-table (function)
• makeq (function)
• neighbors-and-edges (generic function)
• neighbors-and-edges (method)
• q (class)
• qappend (generic function)
• qappend (method)
• qitems (generic function)
• qitems (method)
• (setf qitems) (method)
• (setf qitems) (generic function)
• qlast (generic function)
• qlast (method)
• (setf qlast) (method)
• (setf qlast) (generic function)
• qpop (generic function)
• qpop (method)
• qpush (generic function)
• qpush (method)
• remove-keyword-args (function)
• with-graph-iterator (macro)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Special variables

Special Variable: *default-edge-class*

Package

epigraph

Source

epigraph.lisp (file)

Special Variable: *default-graph-class*

Package

epigraph

Source

epigraph.lisp (file)

5.1.2 Functions

Function: break-cycles GRAPH &key START PICK-FUNCTION

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.

Package

epigraph

Source

epigraph.lisp (file)

Function: find-connected-components GRAPH &key START

Package

epigraph

Source

epigraph.lisp (file)

Function: find-cycle GRAPH &key START TEST

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.

Package

epigraph

Source

epigraph.lisp (file)

Function: find-cycle-edges GRAPH &key START TEST

Package

epigraph

Source

epigraph.lisp (file)

Function: find-longest-path GRAPH

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.

Package

epigraph

Source

epigraph.lisp (file)

Function: find-longest-paths GRAPH

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.

Package

epigraph

Source

epigraph.lisp (file)

Function: graph-distance GRAPH NODE1 NODE2

Returns the (shortest) number of edges between node1 and node2. If node1 is node2, the distance is 0.

Package

epigraph

Source

epigraph.lisp (file)

Function: graph-distance-hash-table GRAPH

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.

Package

epigraph

Source

epigraph.lisp (file)

Function: graph-distance-matrix GRAPH

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.

Package

epigraph

Source

epigraph.lisp (file)

Function: make-graph &rest ARGS &key CLASS NODE-TEST &allow-other-keys

Creates a GRAPH instance whose actual class will either be specified by GRAPH-CLASS or by *DEFAULT-GRAPH-CLASS*.

Package

epigraph

Source

epigraph.lisp (file)

Function: node-equal GRAPH NODE1 NODE2 &key TEST

Package

epigraph

Source

epigraph.lisp (file)

Function: node-find GRAPH ITEM SEQUENCE &key FROM-END START END KEY TEST TEST-NOT

Package

epigraph

Source

epigraph.lisp (file)

Function: node-position GRAPH ITEM SEQUENCE &key FROM-END START END KEY TEST TEST-NOT

Package

epigraph

Source

epigraph.lisp (file)

Function: node-remove GRAPH ITEM SEQUENCE &key FROM-END START END KEY COUNT TEST TEST-NOT

Package

epigraph

Source

epigraph.lisp (file)

Function: remove-connected-component GRAPH &key START

Package

epigraph

Source

epigraph.lisp (file)

5.1.3 Generic functions

Generic Function: add-edge GRAPH EDGE

Adds an edge to the graph.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: add-edge (GRAPH simple-edge-list-graph) (EDGE edge)

Source

simple-edge-list-graph.lisp (file)

Generic Function: add-edge-between-nodes GRAPH NODE1 NODE2 &key EDGE-CLASS

Creates an edge from node1 to node2, adds it to the graph, and returns the edge.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: add-edge-between-nodes (GRAPH simple-edge-list-graph) NODE1 NODE2 &key EDGE-CLASS

Source

simple-edge-list-graph.lisp (file)

Generic Function: add-node GRAPH NODE

Add a node to the graph.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: add-node (GRAPH simple-edge-list-graph) NODE

Source

simple-edge-list-graph.lisp (file)

Generic Function: bfs GRAPH START END &key KEY TEST NEIGHBOR-FN

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

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: bfs (GRAPH graph) START END &key KEY TEST NEIGHBOR-FN

Generic Function: bfs-map GRAPH START FN &key END KEY TEST NEIGHBOR-FN

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

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: bfs-map (GRAPH graph) START FN &key END KEY TEST NEIGHBOR-FN

Generic Function: bfs-map-edges GRAPH START FN &key END KEY TEST

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

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: bfs-map-edges (GRAPH graph) START FN &key END KEY TEST

Generic Function: copy-edge EDGE

Returns a copy of the edge.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: copy-edge (EDGE edge)

Generic Function: copy-graph GRAPH &key COPY-EDGES

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.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: copy-graph (GRAPH simple-edge-list-graph) &key COPY-EDGES

Source

simple-edge-list-graph.lisp (file)

Generic Function: dfs GRAPH START END &key KEY TEST NEIGHBOR-FN

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

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: dfs (GRAPH graph) START END &key KEY TEST NEIGHBOR-FN

Generic Function: dfs-map GRAPH START FN &key END KEY TEST NEIGHBOR-FN

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

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: dfs-map (GRAPH graph) START FN &key END KEY TEST NEIGHBOR-FN

Generic Function: dfs-map-edges GRAPH START FN &key END KEY TEST

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

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: dfs-map-edges (GRAPH graph) START FN &key END KEY TEST

Generic Function: edge-data OBJECT

Generic Function: (setf edge-data) NEW-VALUE OBJECT

Package

epigraph

Methods

Method: edge-data (EDGE edge)

automatically generated reader method

Source

epigraph.lisp (file)

Method: (setf edge-data) NEW-VALUE (EDGE edge)

automatically generated writer method

Source

epigraph.lisp (file)

Generic Function: edgep GRAPH NODE1 NODE2

Returns the edge that connects node1 and node2 in
graph if the edge is present in the graph, otherwise returns NIL.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: edgep (GRAPH simple-edge-list-graph) NODE1 NODE2

Source

simple-edge-list-graph.lisp (file)

Generic Function: edges GRAPH

Returns the edges of graph. Currently the
format in which the edges are returned is not specified.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: edges (GRAPH simple-edge-list-graph)

Source

simple-edge-list-graph.lisp (file)

Generic Function: edges-nodes-equal EDGE1 EDGE2 &key TEST

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.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: edges-nodes-equal (EDGE1 edge) (EDGE2 edge) &key TEST

Generic Function: find-edges-containing GRAPH NODE &key TEST

Returns a list of the edges in graph that start or end with node.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: find-edges-containing (GRAPH simple-edge-list-graph) NODE &key TEST

Source

simple-edge-list-graph.lisp (file)

Generic Function: find-edges-from GRAPH NODE &key TEST

Returns a list of the edges in graph that begin with node.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: find-edges-from (GRAPH simple-edge-list-graph) NODE &key TEST

Source

simple-edge-list-graph.lisp (file)

Generic Function: find-edges-to GRAPH NODE &key TEST

Returns a list of the edges in graph that end with node.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: find-edges-to (GRAPH simple-edge-list-graph) NODE &key TEST

Source

simple-edge-list-graph.lisp (file)

Generic Function: first-node GRAPH

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.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: first-node (GRAPH simple-edge-list-graph)

Source

simple-edge-list-graph.lisp (file)

Generic Function: map-edges FN RESULT-TYPE GRAPH

Calls fn, a function of one argument, for each edge in graph in an unspecified order.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: map-edges FN RESULT-TYPE (GRAPH simple-edge-list-graph)

Source

simple-edge-list-graph.lisp (file)

Generic Function: map-edges->list FN 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.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: map-edges->list FN (GRAPH simple-edge-list-graph)

Source

simple-edge-list-graph.lisp (file)

Generic Function: map-nodes FN GRAPH

Calls FN on every node in the graph, without regard to the configuration of the graph.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: map-nodes FN (GRAPH simple-edge-list-graph)

Source

simple-edge-list-graph.lisp (file)

Generic Function: map-nodes->list FN 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.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: map-nodes->list FN (GRAPH simple-edge-list-graph)

Source

simple-edge-list-graph.lisp (file)

Generic Function: neighbors GRAPH NODE &key TEST

Returns a list of the nodes that are connected to node.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: neighbors GRAPH NODE &key TEST

Generic Function: node-count GRAPH

Returns the number of nodes in graph.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: node-count (GRAPH simple-edge-list-graph)

Source

simple-edge-list-graph.lisp (file)

Generic Function: node1 OBJECT

Generic Function: (setf node1) NEW-VALUE OBJECT

Package

epigraph

Methods

Method: node1 (EDGE edge)

automatically generated reader method

Source

epigraph.lisp (file)

Method: (setf node1) NEW-VALUE (EDGE edge)

automatically generated writer method

Source

epigraph.lisp (file)

Generic Function: node2 OBJECT

Generic Function: (setf node2) NEW-VALUE OBJECT

Package

epigraph

Methods

Method: node2 (EDGE edge)

automatically generated reader method

Source

epigraph.lisp (file)

Method: (setf node2) NEW-VALUE (EDGE edge)

automatically generated writer method

Source

epigraph.lisp (file)

Generic Function: nodes GRAPH

Returns the nodes of graph. Currently the
format in which the nodes are returned is not specified.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: nodes (GRAPH simple-edge-list-graph)

Source

simple-edge-list-graph.lisp (file)

Method: nodes (EDGE edge)

Generic Function: other-edge-node EDGE NODE

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.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: other-edge-node (EDGE edge) NODE

Generic Function: print-edge-data OBJECT STREAM

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.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: print-edge-data (OBJECT edge) STREAM

Generic Function: remove-edge GRAPH EDGE &key TEST

Removes edge from the graph.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: remove-edge (GRAPH simple-edge-list-graph) (EDGE edge) &key TEST

Source

simple-edge-list-graph.lisp (file)

Generic Function: remove-edge-between-nodes GRAPH NODE1 NODE2

Removes the edge from node1 to node2 in the graph.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: remove-edge-between-nodes (GRAPH simple-edge-list-graph) NODE1 NODE2

Source

simple-edge-list-graph.lisp (file)

Generic Function: remove-node GRAPH NODE

Remove a node from the graph.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: remove-node (GRAPH simple-edge-list-graph) NODE

Source

simple-edge-list-graph.lisp (file)

Generic Function: self-edge-p GRAPH EDGE &key TEST

Returns true if the edge connects a given node to itself.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: self-edge-p (GRAPH simple-edge-list-graph) EDGE &key TEST

Source

simple-edge-list-graph.lisp (file)

5.1.4 Classes

Class: edge ()

Instances of the EDGE class represent edges between nodes in a graph.

Package

epigraph

Source

epigraph.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• remove-edge (method)
• add-edge (method)
• other-edge-node (method)
• edges-nodes-equal (method)
• nodes (method)
• copy-edge (method)
• print-object (method)
• print-edge-data (method)
• edge-data (method)
• edge-data (method)
• node2 (method)
• node2 (method)
• node1 (method)
• node1 (method)

Direct slots

Slot: node1

Initargs

:node1

Readers

node1 (generic function)

Writers

(setf node1) (generic function)

Slot: node2

Initargs

:node2

Readers

node2 (generic function)

Writers

(setf node2) (generic function)

Slot: data

Initargs

:data

Readers

edge-data (generic function)

Writers

(setf edge-data) (generic function)

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

Package

epigraph

Source

epigraph.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

simple-edge-list-graph (class)

Direct methods

• dfs2 (method)
• bfs2 (method)
• graph-search (method)
• dfs-map-edges (method)
• dfs-map (method)
• dfs (method)
• bfs-map-edges (method)
• bfs-map (method)
• bfs (method)
• graph-node-test (method)
• graph-node-test (method)

Direct slots

Slot: node-test

Initargs

:node-test

Initform

(quote eql)

Readers

graph-node-test (generic function)

Writers

(setf graph-node-test) (generic function)

Class: simple-edge-list-graph ()

A concrete subclass of graph that represents the edges in the graph with a list of edges between nodes.

Package

epigraph

Source

simple-edge-list-graph.lisp (file)

Direct superclasses

graph (class)

Direct methods

• find-edges-containing (method)
• self-edge-p (method)
• find-self-edges (method)
• find-edges-to (method)
• find-edges-from (method)
• find-edge (method)
• edgep (method)
• remove-edge-between-nodes (method)
• remove-edge (method)
• add-edge-between-nodes (method)
• add-edge (method)
• copy-graph (method)
• map-edges->list (method)
• map-edges (method)
• edges (method)
• map-nodes->list (method)
• map-nodes (method)
• nodes (method)
• first-node (method)
• remove-node (method)
• add-node (method)
• node-count (method)
• graph-node-p (method)
• graph-edge-list (method)
• graph-edge-list (method)
• graph-node-hash (method)
• graph-node-hash (method)

Direct slots

Slot: node-hash

Initargs

:nodes

Initform

(make-hash-table :test (quote equal))

Readers

graph-node-hash (generic function)

Writers

(setf graph-node-hash) (generic function)

Slot: edges

Initargs

:edges

Readers

graph-edge-list (generic function)

Writers

(setf graph-edge-list) (generic function)

5.2 Internal definitions

5.2.1 Special variables

Special Variable: *bfs-depth*

Package

epigraph

Source

epigraph.lisp (file)

Special Variable: *dfs-depth*

Package

epigraph

Source

epigraph.lisp (file)

5.2.2 Macros

Macro: with-graph-iterator (FUNCTION GRAPH) &body BODY

Package

epigraph

Source

simple-edge-list-graph.lisp (file)

5.2.3 Functions

Function: carhash HASH-TABLE

Package

epigraph

Source

utilities.lisp (file)

Function: floyd-warshall GRAPH

Package

epigraph

Source

epigraph.lisp (file)

Function: make-node-hash-table GRAPH

Package

epigraph

Source

epigraph.lisp (file)

Function: makeq ()

Package

epigraph

Source

epigraph.lisp (file)

Function: remove-keyword-args KEYWORDS LIST

Package

epigraph

Source

utilities.lisp (file)

5.2.4 Generic functions

Generic Function: bfs2 GRAPH START END &key KEY TEST

Package

epigraph

Methods

Method: bfs2 (GRAPH graph) START END &key KEY TEST

Source

epigraph.lisp (file)

Generic Function: dfs2 GRAPH START END &key KEY TEST

Package

epigraph

Methods

Method: dfs2 (GRAPH graph) START END &key KEY TEST

Source

epigraph.lisp (file)

Generic Function: find-edge GRAPH NODE1 NODE2

Package

epigraph

Methods

Method: find-edge (GRAPH simple-edge-list-graph) NODE1 NODE2

Source

simple-edge-list-graph.lisp (file)

Generic Function: find-self-edges GRAPH NODE &key TEST

Returns a list of the edges in graph that begin and end with node.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: find-self-edges (GRAPH simple-edge-list-graph) NODE &key TEST

Source

simple-edge-list-graph.lisp (file)

Generic Function: graph-edge-list OBJECT

Generic Function: (setf graph-edge-list) NEW-VALUE OBJECT

Package

epigraph

Methods

Method: graph-edge-list (SIMPLE-EDGE-LIST-GRAPH simple-edge-list-graph)

automatically generated reader method

Source

simple-edge-list-graph.lisp (file)

Method: (setf graph-edge-list) NEW-VALUE (SIMPLE-EDGE-LIST-GRAPH simple-edge-list-graph)

automatically generated writer method

Source

simple-edge-list-graph.lisp (file)

Generic Function: graph-node-hash OBJECT

Generic Function: (setf graph-node-hash) NEW-VALUE OBJECT

Package

epigraph

Methods

Method: graph-node-hash (SIMPLE-EDGE-LIST-GRAPH simple-edge-list-graph)

automatically generated reader method

Source

simple-edge-list-graph.lisp (file)

Method: (setf graph-node-hash) NEW-VALUE (SIMPLE-EDGE-LIST-GRAPH simple-edge-list-graph)

automatically generated writer method

Source

simple-edge-list-graph.lisp (file)

Generic Function: graph-node-p GRAPH NODE

Returns t if node is a node in graph.

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: graph-node-p (GRAPH simple-edge-list-graph) NODE

Source

simple-edge-list-graph.lisp (file)

Generic Function: graph-node-test OBJECT

Generic Function: (setf graph-node-test) NEW-VALUE OBJECT

Package

epigraph

Methods

Method: graph-node-test (GRAPH graph)

automatically generated reader method

Source

epigraph.lisp (file)

Method: (setf graph-node-test) NEW-VALUE (GRAPH graph)

automatically generated writer method

Source

epigraph.lisp (file)

Generic Function: graph-search GRAPH START END &key KEY TEST QUEUEING-FUNCTION

Package

epigraph

Methods

Method: graph-search (GRAPH graph) START END &key KEY TEST QUEUEING-FUNCTION

Source

epigraph.lisp (file)

Generic Function: neighbors-and-edges GRAPH NODE &key TEST

Package

epigraph

Methods

Method: neighbors-and-edges GRAPH NODE &key TEST

Source

epigraph.lisp (file)

Generic Function: qappend Q ITEM

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: qappend Q ITEM

Generic Function: qitems OBJECT

Generic Function: (setf qitems) NEW-VALUE OBJECT

Package

epigraph

Methods

Method: qitems (Q q)

automatically generated reader method

Source

epigraph.lisp (file)

Method: (setf qitems) NEW-VALUE (Q q)

automatically generated writer method

Source

epigraph.lisp (file)

Generic Function: qlast OBJECT

Generic Function: (setf qlast) NEW-VALUE OBJECT

Package

epigraph

Methods

Method: qlast (Q q)

automatically generated reader method

Source

epigraph.lisp (file)

Method: (setf qlast) NEW-VALUE (Q q)

automatically generated writer method

Source

epigraph.lisp (file)

Generic Function: qpop Q

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: qpop Q

Generic Function: qpush Q ITEM

Package

epigraph

Source

epigraph.lisp (file)

Methods

Method: qpush Q ITEM

5.2.5 Classes

Class: q ()

Package

epigraph

Source

epigraph.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• qlast (method)
• qlast (method)
• qitems (method)
• qitems (method)

Direct slots

Slot: items

Readers

qitems (generic function)

Writers

(setf qitems) (generic function)

Slot: last

Readers

qlast (generic function)

Writers

(setf qlast) (generic function)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types