The graph Reference Manual

Table of Contents

The graph Reference Manual

This is the graph Reference Manual, version 0.0.0, generated automatically by Declt version 3.0 "Montgomery Scott" on Fri Jun 26 11:11:17 2020 GMT+0.

1 Introduction

GRAPH - simple graph data structure and algorithms

The GRAPH library strives for simplicity both in backing data
structures and in usage. Graphs and Digraphs are represented as CLOS
objects with methods and algorithms provided for graph manipulation
and analysis.

Note: currently this library is only supported on SBCL, Clozure CL,
      and Allegro CL because of the need to create hashes with custom
      equality tests, however custom equality tests are commonly
      supported so extending to other lisps should be simple. Patches
      welcome.

For more information see http://eschulte.github.com/graph.

2 Systems

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

2.1 graph

Authors

Eric Schulte <schulte.eric@gmail.com>
Thomas Dye

License

GPL V3

Description

simple library for building and manipulating graphs

Version

0.0.0

Defsystem Dependency

asdf-package-system

Dependencies

• alexandria
• metabang-bind
• named-readtables
• curry-compose-reader-macros
• graph/graph (system)

Source

graph.asd (file)

2.2 graph/graph

Authors

Eric Schulte <schulte.eric@gmail.com>
Thomas Dye

License

GPL V3

Dependencies

• alexandria
• metabang-bind
• named-readtables
• curry-compose-reader-macros
• cl-heap

Source

graph.asd (file)

Component

lisp.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 graph.asd

Location

graph.asd

Systems

• graph (system)
• graph/graph (system)

3.1.2 graph/graph/lisp.lisp

Parent

graph/graph (system)

Location

graph.lisp

Packages

graph/graph

Exported Definitions

• add-edge (generic function)
• add-edge (method)
• add-node (generic function)
• add-node (method)
• add-paths (generic function)
• add-paths (method)
• add-paths (method)
• adjacent-from (generic function)
• adjacent-from (method)
• adjacent-to (generic function)
• adjacent-to (method)
• all-paths (generic function)
• all-paths (method)
• basic-cycles (generic function)
• basic-cycles (method)
• betweenness (generic function)
• betweenness (method)
• carrierp (generic function)
• carrierp (method)
• carriers (generic function)
• carriers (method)
• cliques (generic function)
• cliques (method)
• closedp (generic function)
• closedp (method)
• closeness (generic function)
• closeness (method)
• clustering-coefficient (generic function)
• clustering-coefficient (method)
• connected-component (generic function)
• connected-component (method)
• connected-component (method)
• connected-components (generic function)
• connected-components (method)
• connected-groups-of-size (generic function)
• connected-groups-of-size (method)
• connectedp (generic function)
• connectedp (method)
• connectedp (method)
• copy (generic function)
• copy (method)
• cycles (generic function)
• cycles (method)
• degeneracy (generic function)
• degeneracy (method)
• degree (generic function)
• degree (method)
• delete-edge (generic function)
• delete-edge (method)
• delete-node (generic function)
• delete-node (method)
• digraph (class)
• digraph-of (generic function)
• digraph-of (method)
• edgar-gilbert-digraph (function)
• edgar-gilbert-graph (function)
• edgar-gilbert-populate (generic function)
• edgar-gilbert-populate (method)
• edgar-gilbert-populate (method)
• edge-neighbors (generic function)
• edge-neighbors (method)
• edge-value (generic function)
• edge-value (method)
• (setf edge-value) (method)
• (setf edge-value) (generic function)
• edges (generic function)
• edges (method)
• (setf edges) (method)
• (setf edges) (generic function)
• edges-w-values (generic function)
• edges-w-values (method)
• (setf edges-w-values) (method)
• (setf edges-w-values) (generic function)
• erdos-renyi-digraph (function)
• erdos-renyi-graph (function)
• erdos-renyi-populate (generic function)
• erdos-renyi-populate (method)
• farness (generic function)
• farness (method)
• from-plist (generic function)
• from-plist (method)
• from-value-matrix (generic function)
• from-value-matrix (method)
• graph (class)
• graph-equal (generic function)
• graph-equal (method)
• graph-of (generic function)
• graph-of (method)
• has-edge-p (generic function)
• has-edge-p (method)
• has-node-p (generic function)
• has-node-p (method)
• indegree (generic function)
• indegree (method)
• isolatep (generic function)
• isolatep (method)
• isolates (generic function)
• isolates (method)
• k-cores (generic function)
• k-cores (method)
• katz-centrality (generic function)
• katz-centrality (method)
• levels (generic function)
• levels (method)
• max-flow (generic function)
• max-flow (method)
• merge-edges (generic function)
• merge-edges (method)
• merge-nodes (generic function)
• merge-nodes (method)
• min-cut (generic function)
• min-cut (method)
• minimum-spanning-tree (generic function)
• minimum-spanning-tree (method)
• neighbors (generic function)
• neighbors (method)
• neighbors (method)
• node-edges (generic function)
• node-edges (method)
• (setf node-edges) (method)
• (setf node-edges) (generic function)
• nodes (generic function)
• nodes (method)
• (setf nodes) (method)
• (setf nodes) (generic function)
• nodes-w-values (generic function)
• nodes-w-values (method)
• ordinaries (generic function)
• ordinaries (method)
• ordinaryp (generic function)
• ordinaryp (method)
• outdegree (generic function)
• outdegree (method)
• populate (generic function)
• populate (method)
• precedents (generic function)
• precedents (method)
• preferential-attachment-populate (generic function)
• preferential-attachment-populate (method)
• receiverp (generic function)
• receiverp (method)
• receivers (generic function)
• receivers (method)
• residual (generic function)
• residual (method)
• reverse-edges (generic function)
• reverse-edges (method)
• shortest-path (generic function)
• shortest-path (method)
• strongly-connected-components (generic function)
• strongly-connected-components (method)
• subgraph (generic function)
• subgraph (method)
• to-plist (generic function)
• to-plist (method)
• to-value-matrix (generic function)
• to-value-matrix (method)
• topological-sort (generic function)
• topological-sort (method)
• transmitterp (generic function)
• transmitterp (method)
• transmitters (generic function)
• transmitters (method)

Internal Definitions

• connected-component- (function)
• copy-hash (function)
• dir-edge-equalp (function)
• edge-eq (method)
• (setf edge-eq) (method)
• edge-eq (method)
• (setf edge-eq) (method)
• edge-equalp (function)
• edge-h (method)
• (setf edge-h) (method)
• edge-h (method)
• (setf edge-h) (method)
• edge-hash-equal (function)
• make-diedge-hash-table (function)
• make-edge-hash-table (function)
• node-h (method)
• (setf node-h) (method)
• node-hash-equal (function)
• sxhash-edge (function)
• weigh-cut (function)

4 Packages

Packages are listed by definition order.

4.1 graph/graph

Source

lisp.lisp (file)

Nickname

graph

Use List

• cl-heap
• curry-compose-reader-macros
• editor-hints.named-readtables
• metabang.bind
• alexandria
• common-lisp

Exported Definitions

• add-edge (generic function)
• add-edge (method)
• add-node (generic function)
• add-node (method)
• add-paths (generic function)
• add-paths (method)
• add-paths (method)
• adjacent-from (generic function)
• adjacent-from (method)
• adjacent-to (generic function)
• adjacent-to (method)
• all-paths (generic function)
• all-paths (method)
• basic-cycles (generic function)
• basic-cycles (method)
• betweenness (generic function)
• betweenness (method)
• carrierp (generic function)
• carrierp (method)
• carriers (generic function)
• carriers (method)
• cliques (generic function)
• cliques (method)
• closedp (generic function)
• closedp (method)
• closeness (generic function)
• closeness (method)
• clustering-coefficient (generic function)
• clustering-coefficient (method)
• connected-component (generic function)
• connected-component (method)
• connected-component (method)
• connected-components (generic function)
• connected-components (method)
• connected-groups-of-size (generic function)
• connected-groups-of-size (method)
• connectedp (generic function)
• connectedp (method)
• connectedp (method)
• copy (generic function)
• copy (method)
• cycles (generic function)
• cycles (method)
• degeneracy (generic function)
• degeneracy (method)
• degree (generic function)
• degree (method)
• delete-edge (generic function)
• delete-edge (method)
• delete-node (generic function)
• delete-node (method)
• digraph (class)
• digraph-of (generic function)
• digraph-of (method)
• edgar-gilbert-digraph (function)
• edgar-gilbert-graph (function)
• edgar-gilbert-populate (generic function)
• edgar-gilbert-populate (method)
• edgar-gilbert-populate (method)
• edge-neighbors (generic function)
• edge-neighbors (method)
• edge-value (generic function)
• edge-value (method)
• (setf edge-value) (method)
• (setf edge-value) (generic function)
• edges (generic function)
• edges (method)
• (setf edges) (method)
• (setf edges) (generic function)
• edges-w-values (generic function)
• edges-w-values (method)
• (setf edges-w-values) (method)
• (setf edges-w-values) (generic function)
• erdos-renyi-digraph (function)
• erdos-renyi-graph (function)
• erdos-renyi-populate (generic function)
• erdos-renyi-populate (method)
• farness (generic function)
• farness (method)
• from-plist (generic function)
• from-plist (method)
• from-value-matrix (generic function)
• from-value-matrix (method)
• graph (class)
• graph-equal (generic function)
• graph-equal (method)
• graph-of (generic function)
• graph-of (method)
• has-edge-p (generic function)
• has-edge-p (method)
• has-node-p (generic function)
• has-node-p (method)
• indegree (generic function)
• indegree (method)
• isolatep (generic function)
• isolatep (method)
• isolates (generic function)
• isolates (method)
• k-cores (generic function)
• k-cores (method)
• katz-centrality (generic function)
• katz-centrality (method)
• levels (generic function)
• levels (method)
• max-flow (generic function)
• max-flow (method)
• merge-edges (generic function)
• merge-edges (method)
• merge-nodes (generic function)
• merge-nodes (method)
• min-cut (generic function)
• min-cut (method)
• minimum-spanning-tree (generic function)
• minimum-spanning-tree (method)
• neighbors (generic function)
• neighbors (method)
• neighbors (method)
• node-edges (generic function)
• node-edges (method)
• (setf node-edges) (method)
• (setf node-edges) (generic function)
• nodes (generic function)
• nodes (method)
• (setf nodes) (method)
• (setf nodes) (generic function)
• nodes-w-values (generic function)
• nodes-w-values (method)
• ordinaries (generic function)
• ordinaries (method)
• ordinaryp (generic function)
• ordinaryp (method)
• outdegree (generic function)
• outdegree (method)
• populate (generic function)
• populate (method)
• precedents (generic function)
• precedents (method)
• preferential-attachment-populate (generic function)
• preferential-attachment-populate (method)
• receiverp (generic function)
• receiverp (method)
• receivers (generic function)
• receivers (method)
• residual (generic function)
• residual (method)
• reverse-edges (generic function)
• reverse-edges (method)
• shortest-path (generic function)
• shortest-path (method)
• strongly-connected-components (generic function)
• strongly-connected-components (method)
• subgraph (generic function)
• subgraph (method)
• to-plist (generic function)
• to-plist (method)
• to-value-matrix (generic function)
• to-value-matrix (method)
• topological-sort (generic function)
• topological-sort (method)
• transmitterp (generic function)
• transmitterp (method)
• transmitters (generic function)
• transmitters (method)

Internal Definitions

• connected-component- (function)
• copy-hash (function)
• dir-edge-equalp (function)
• edge-eq (generic function)
• edge-eq (method)
• (setf edge-eq) (method)
• edge-eq (method)
• (setf edge-eq) (method)
• (setf edge-eq) (generic function)
• edge-equalp (function)
• edge-h (generic function)
• edge-h (method)
• (setf edge-h) (method)
• edge-h (method)
• (setf edge-h) (method)
• (setf edge-h) (generic function)
• edge-hash-equal (function)
• make-diedge-hash-table (function)
• make-edge-hash-table (function)
• node-h (generic function)
• node-h (method)
• (setf node-h) (method)
• (setf node-h) (generic function)
• node-hash-equal (function)
• sxhash-edge (function)
• weigh-cut (function)

5 Definitions

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

5.1 Exported definitions

5.1.1 Functions

Function: edgar-gilbert-digraph N P

Package

graph/graph

Source

lisp.lisp (file)

Function: edgar-gilbert-graph N P

Package

graph/graph

Source

lisp.lisp (file)

Function: erdos-renyi-digraph N M

Return an Erdős–Rényi digraph with N nodes and M edges.

Package

graph/graph

Source

lisp.lisp (file)

Function: erdos-renyi-graph N M

Return an Erdős–Rényi graph with N nodes and M edges.

Package

graph/graph

Source

lisp.lisp (file)

5.1.2 Generic functions

Generic Function: add-edge GRAPH EDGE &optional VALUE

Add EDGE to GRAPH with optional VALUE. The nodes of EDGE are also added to GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: add-edge (GRAPH graph) EDGE &optional VALUE

Generic Function: add-node GRAPH NODE

Add NODE to GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: add-node (GRAPH graph) NODE

Generic Function: add-paths GRAPH PATH1 PATH2

Return the combination of paths PATH1 and PATH2 through GRAPH. Each element of PATH has the form (cons edge value).

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: add-paths (DIGRAPH digraph) PATH1 PATH2

Return the combination of paths PATH1 and PATH2 through DIGRAPH. Each element of path has the form (cons edge value).

Method: add-paths (GRAPH graph) PATH1 PATH2

Generic Function: adjacent-from DIGRAPH NODE

List nodes adjacent from NODE in DIGRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: adjacent-from (DIGRAPH digraph) NODE

Generic Function: adjacent-to DIGRAPH NODE

List nodes adjacent to NODE in DIGRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: adjacent-to (DIGRAPH digraph) NODE

Generic Function: all-paths GRAPH A B

Return all paths in GRAPH from A to B.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: all-paths (GRAPH graph) A B

Generic Function: basic-cycles GRAPH

Return all basic cycles in the GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: basic-cycles (GRAPH graph)

Generic Function: betweenness GRAPH NODE &optional HEURISTIC

Fraction of shortest paths through GRAPH which pass through NODE. Fraction of node pairs (s,t) s.t. s and t ≠ NODE and the shortest path between s and t in GRAPH passes through NODE.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: betweenness (GRAPH graph) NODE &optional HEURISTIC

Generic Function: carrierp DIGRAPH NODE

Returns t if node is a carrier, i.e., both indegree and outdegree are 1.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: carrierp (DIGRAPH digraph) NODE

Generic Function: carriers DIGRAPH

Return a list of the carrier nodes in digraph.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: carriers (DIGRAPH digraph)

Generic Function: cliques GRAPH

Return the maximal cliques of GRAPH. The Bron-Kerbosh algorithm is used.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: cliques (GRAPH graph) &aux CLIQUES

Generic Function: closedp GRAPH NODES

Return true if NODES are fully connected in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: closedp (GRAPH graph) NODES

Generic Function: closeness GRAPH NODE

Inverse of the ‘farness’ for NODE in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: closeness (GRAPH graph) NODE

Generic Function: clustering-coefficient GRAPH

Fraction of connected triples which are closed.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: clustering-coefficient (GRAPH graph)

Generic Function: connected-component GRAPH NODE &key TYPE

Return the connected component of NODE in GRAPH.
The TYPE keyword argument only has an effect for directed graphs in which it may be set to one of the following with :STRONG being the default value.

:STRONG ..... connections only traverse edges along the direction of the edge

:WEAK ....... connections may traverse edges in any direction regardless of the edge direction

:UNILATERAL . two nodes a and b connected iff a is strongly connected to b or b is strongly connected to a

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: connected-component (DIGRAPH digraph) NODE &key TYPE

Method: connected-component (GRAPH graph) NODE &key TYPE

Generic Function: connected-components GRAPH &key TYPE

Return a list of the connected components of GRAPH.
Keyword TYPE is passed to ‘connected-component’ and only has effect for directed graphs. Returns strongly connected components of a directed graph by default.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: connected-components (GRAPH graph) &key TYPE

Generic Function: connected-groups-of-size GRAPH SIZE

Return all connected node groups of SIZE in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: connected-groups-of-size (GRAPH graph) SIZE

Generic Function: connectedp GRAPH &key TYPE

Return true if the graph is connected.
TYPE keyword argument is passed to ‘connected-components’.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: connectedp (DIGRAPH digraph) &key TYPE

Method: connectedp (GRAPH graph) &key TYPE

Generic Function: copy GRAPH

Return a copy of GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: copy (GRAPH graph)

Generic Function: cycles GRAPH

Return all cycles of GRAPH (both basic and compound).

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: cycles (GRAPH graph)

Generic Function: degeneracy GRAPH

Return the degeneracy and k-cores of GRAPH.
Also return the node ordering with optimal coloring number as an alist. The ‘car’ of each element of the alist identifies k-cores and the ‘cdr’ holds the nodes in the ordering.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: degeneracy (GRAPH graph)

Generic Function: degree GRAPH NODE

Return the degree of NODE in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: degree (GRAPH graph) NODE

Generic Function: delete-edge GRAPH EDGE

Delete EDGE from GRAPH. Return the old value of EDGE.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: delete-edge (GRAPH graph) EDGE

Generic Function: delete-node GRAPH NODE

Delete NODE from GRAPH.
Delete and return the old edges of NODE in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: delete-node (GRAPH graph) NODE

Generic Function: digraph-of GRAPH

Copy GRAPH into a ‘digraph’ and return.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: digraph-of (GRAPH graph)

Generic Function: edgar-gilbert-populate GRAPH P

Populate GRAPH including every possible edge with probability P.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: edgar-gilbert-populate (DIGRAPH digraph) P

Method: edgar-gilbert-populate (GRAPH graph) P

Generic Function: edge-neighbors GRAPH EDGE

Return all edges which share a node with EDGE in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: edge-neighbors (GRAPH graph) EDGE

Generic Function: edge-value GRAPH EDGE

Return the value of EDGE in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Writer

(setf edge-value) (generic function)

Methods

Method: edge-value (GRAPH graph) EDGE

Generic Function: (setf edge-value) NEW GRAPH EDGE

Set the value of EDGE in GRAPH to NEW.

Package

graph/graph

Source

lisp.lisp (file)

Reader

edge-value (generic function)

Methods

Method: (setf edge-value) NEW (GRAPH graph) EDGE

Generic Function: edges GRAPH

Return a list of the edges in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Writer

(setf edges) (generic function)

Methods

Method: edges (GRAPH graph)

Generic Function: (setf edges) NEW GRAPH

Set the edges in GRAPH to NEW.

Package

graph/graph

Source

lisp.lisp (file)

Reader

edges (generic function)

Methods

Method: (setf edges) NEW (GRAPH graph)

Generic Function: edges-w-values GRAPH

Return an alist of edges of GRAPH with their values.

Package

graph/graph

Source

lisp.lisp (file)

Writer

(setf edges-w-values) (generic function)

Methods

Method: edges-w-values (GRAPH graph) &aux ALIST

Generic Function: (setf edges-w-values) NEW GRAPH

Set the edges of graph to edges and values in NEW.

Package

graph/graph

Source

lisp.lisp (file)

Reader

edges-w-values (generic function)

Methods

Method: (setf edges-w-values) NEW (GRAPH graph)

Generic Function: erdos-renyi-populate GRAPH M

Populate GRAPH with M edges in an Erdős–Rényi random graph model.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: erdos-renyi-populate (GRAPH graph) M

Generic Function: farness GRAPH NODE &optional HEURISTIC

Sum of the distance from NODE to every other node in connected GRAPH. Optional argument HEURISTIC if supplied is passed through to guide the A* search used in ‘shortest-path’.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: farness (GRAPH graph) NODE &optional HEURISTIC

Generic Function: from-plist GRAPH PLIST

Populate GRAPH with the contents of PLIST.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: from-plist (GRAPH graph) PLIST

Generic Function: from-value-matrix GRAPH MATRIX

Populate GRAPH from the value matrix MATRIX.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: from-value-matrix (GRAPH graph) MATRIX

Generic Function: graph-equal GRAPH1 GRAPH2

Compare GRAPH1 and GRAPH2 for equality.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: graph-equal (GRAPH1 graph) (GRAPH2 graph)

Generic Function: graph-of DIGRAPH

Copy DIGRAPH into a ‘graph’ and return.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: graph-of (DIGRAPH digraph)

Generic Function: has-edge-p GRAPH EDGE

Return ‘true’ if GRAPH has edge EDGE.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: has-edge-p (GRAPH graph) EDGE

Generic Function: has-node-p GRAPH NODE

Return ‘true’ if GRAPH has node NODE.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: has-node-p (GRAPH graph) NODE

Generic Function: indegree DIGRAPH NODE

The number of edges directed to NODE in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: indegree (DIGRAPH digraph) NODE

Generic Function: isolatep DIGRAPH NODE

Returns t if node is an isolate, i.e., both indegree and outdegree are 0.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: isolatep (DIGRAPH digraph) NODE

Generic Function: isolates DIGRAPH

Return a list of the isolated nodes in digraph.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: isolates (DIGRAPH digraph)

Generic Function: k-cores GRAPH

Return the k-cores of GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: k-cores (GRAPH graph)

Generic Function: katz-centrality GRAPH NODE &key ATTENUATION HEURISTIC

Combined measure of number and nearness of nodes to NODE.
Keyword argument HEURISTIC if supplied is passed through to guide the A* search used in ‘shortest-path’.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: katz-centrality (GRAPH graph) NODE &key ATTENUATION HEURISTIC

Generic Function: levels DIGRAPH &key ALIST

Assign a positive integer to each node in DIGRAPH,
called its level, where, for each directed edge (a b) the corresponding integers satisfy a < b. Returns either a hash table where the nodes are keys and the levels are values, or an association list of nodes and their levels, along with the number of levels in DIGRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: levels DIGRAPH &key ALIST

Generic Function: max-flow GRAPH FROM TO &optional HEURISTIC

Return the maximum flow from FROM and to TO in GRAPH.
GRAPHS must be a network with numeric values of all edges (otherwise a default cost of 1 is used for every edge). The Ford-Fulkerson algorithm is used. Optional argument HEURISTIC if supplied is passed through to guide the A* search used in ‘shortest-path’.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: max-flow (DIGRAPH digraph) FROM TO &optional HEURISTIC

Generic Function: merge-edges GRAPH EDGE1 EDGE2 &key VALUE

Combine EDGE1 and EDGE2 in GRAPH into a new EDGE.
Optionally provide a value for the new edge, the values of EDGE1 and EDGE2 will be combined.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: merge-edges (GRAPH graph) EDGE1 EDGE2 &key VALUE

Generic Function: merge-nodes GRAPH NODE1 NODE2 &key NEW

Combine NODE1 and NODE2 in GRAPH into the node NEW.
All edges of NODE1 and NODE2 in GRAPH will be combined into a new node of value NEW. Edges between only NODE1 and NODE2 will be removed.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: merge-nodes (GRAPH graph) NODE1 NODE2 &key NEW

Generic Function: min-cut GRAPH

Return both the global min-cut of GRAPH and the weight of the cut.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: min-cut (GRAPH graph)

Generic Function: minimum-spanning-tree GRAPH &optional TREE

Return a minimum spanning tree of GRAPH.
Prim’s algorithm is used. Optional argument TREE may be used to specify an initial tree, otherwise a random node is used.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: minimum-spanning-tree (GRAPH graph) &optional TREE

Generic Function: neighbors GRAPH NODE

Return all nodes which share an edge with NODE in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: neighbors (DIGRAPH digraph) NODE

Method: neighbors (GRAPH graph) NODE

Generic Function: node-edges GRAPH NODE

Return the value of NODE in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Writer

(setf node-edges) (generic function)

Methods

Method: node-edges (GRAPH graph) NODE

Generic Function: (setf node-edges) NEW GRAPH NODE

Set the edges of NODE in GRAPH to NEW.
Delete and return the old edges of NODE in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Reader

node-edges (generic function)

Methods

Method: (setf node-edges) NEW (GRAPH graph) NODE

Generic Function: nodes GRAPH

Return a list of the nodes in GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Writer

(setf nodes) (generic function)

Methods

Method: nodes (GRAPH graph)

Generic Function: (setf nodes) NEW GRAPH

Set the nodes in GRAPH to NEW.

Package

graph/graph

Source

lisp.lisp (file)

Reader

nodes (generic function)

Methods

Method: (setf nodes) NEW (GRAPH graph)

Generic Function: nodes-w-values GRAPH

Return an alist of nodes of GRAPH with their values.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: nodes-w-values (GRAPH graph) &aux ALIST

Generic Function: ordinaries DIGRAPH

Return a list of the ordinary nodes in digraph.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: ordinaries (DIGRAPH digraph)

Generic Function: ordinaryp DIGRAPH NODE

Returns t if node is ordinary, i.e., is not a transmitter, receiver, isolate, or carrier.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: ordinaryp (DIGRAPH digraph) NODE

Generic Function: outdegree DIGRAPH NODE

The number of edges directed from NODE in DIGRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: outdegree (DIGRAPH digraph) NODE

Generic Function: populate GRAPH &key NODES EDGES EDGES-W-VALUES

Populate the nodes and edges of GRAPH based on keyword arguments.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: populate (GRAPH graph) &key NODES EDGES EDGES-W-VALUES

Generic Function: precedents DIGRAPH NODE

Return all nodes preceding NODE in an edge of DIGRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: precedents (DIGRAPH digraph) NODE

Generic Function: preferential-attachment-populate GRAPH NODES &key EDGE-VALS

Add NODES to GRAPH using preferential attachment, return the new edges. Optionally assign edge values from those listed in EDGE-VALS.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: preferential-attachment-populate (GRAPH graph) NODES &key EDGE-VALS

Generic Function: receiverp DIGRAPH NODE

Returns t if node is a receiver, i.e., has outdegree of 0 and positive indegree.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: receiverp (DIGRAPH digraph) NODE

Generic Function: receivers DIGRAPH

Return a list of the receivers in digraph.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: receivers (DIGRAPH digraph)

Generic Function: residual GRAPH FLOW

Return the residual graph of GRAPH with FLOW.
Each edge in the residual has a value equal to the original capacity minus the current flow, or equal to the negative of the current flow.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: residual (GRAPH graph) FLOW

Generic Function: reverse-edges GRAPH

Return a copy of GRAPH with all edges reversed.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: reverse-edges (GRAPH graph)

Generic Function: shortest-path GRAPH A B &optional HEURISTIC

Return the shortest path in GRAPH from A to B.
Implemented using A* search. Optional argument HEURISTIC may be a function which returns an estimated heuristic cost from an node to the target B. The default value for HEURISTIC is the constant function of 0, reducing this implementation to Dijkstra’s algorithm. The HEURISTIC function must satisfy HEURITIC(x)≤d(x,y)+HEURITIC(y) ∀ x,y in GRAPH allowing the more efficient monotonic or "consistent" implementation of A*.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: shortest-path (GRAPH graph) A B &optional HEURISTIC &aux FROM FRINGE OPEN CLOSED G F

Generic Function: strongly-connected-components GRAPH

Return the nodes of GRAPH partitioned into strongly connected components. Uses Tarjan’s algorithm.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: strongly-connected-components (GRAPH graph)

Generic Function: subgraph GRAPH NODES

Return the subgraph of GRAPH restricted to NODES.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: subgraph (GRAPH graph) NODES

Generic Function: to-plist GRAPH &key NODE-FN EDGE-FN

Serialize GRAPH as a plist.
Keyword arguments NODE-FN and EDGE-FN will be called on a node or edge and should return a plist of data to associate with the given node or edge in the results.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: to-plist (GRAPH graph) &key NODE-FN EDGE-FN

Generic Function: to-value-matrix GRAPH

Return the value matrix of GRAPH.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: to-value-matrix (GRAPH graph)

Generic Function: topological-sort DIGRAPH

Returns a topologically ordered list of the nodes in DIGRAPH, such that, for each edge in DIGRAPH, the start of the edge appears in the list before the end of the edge.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: topological-sort DIGRAPH

Generic Function: transmitterp DIGRAPH NODE

Returns t if node is a transmitter, i.e., has indegree of 0 and positive outdegree.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: transmitterp (DIGRAPH digraph) NODE

Generic Function: transmitters DIGRAPH

Return a list of the transmitters in digraph.

Package

graph/graph

Source

lisp.lisp (file)

Methods

Method: transmitters (DIGRAPH digraph)

5.1.3 Classes

Class: digraph ()

A ‘graph’ with directed edges.

Package

graph/graph

Source

lisp.lisp (file)

Direct superclasses

graph (class)

Direct methods

• edgar-gilbert-populate (method)
• max-flow (method)
• add-paths (method)
• connectedp (method)
• connected-component (method)
• precedents (method)
• neighbors (method)
• carriers (method)
• ordinaries (method)
• isolates (method)
• receivers (method)
• transmitters (method)
• ordinaryp (method)
• carrierp (method)
• isolatep (method)
• receiverp (method)
• transmitterp (method)
• adjacent-to (method)
• adjacent-from (method)
• outdegree (method)
• indegree (method)
• graph-of (method)
• edge-eq (method)
• edge-eq (method)
• edge-h (method)
• edge-h (method)

Direct slots

Slot: edge-h

Initargs

:edge-h

Initform

(graph/graph::make-diedge-hash-table)

Readers

edge-h (generic function)

Writers

(setf edge-h) (generic function)

Slot: edge-eq

Initargs

:edge-eq

Initform

(quote graph/graph::dir-edge-equalp)

Readers

edge-eq (generic function)

Writers

(setf edge-eq) (generic function)

Class: graph ()

A graph consisting of ‘nodes’ connected by ‘edges’.
Nodes must be numbers symbols or keywords. Edges may be assigned arbitrary values, although some functions assume numeric values (e.g., ‘merge-nodes’, ‘merge-edges’, ‘max-flow’ and ‘min-cut’).

Package

graph/graph

Source

lisp.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

digraph (class)

Direct methods

• k-cores (method)
• degeneracy (method)
• katz-centrality (method)
• betweenness (method)
• closeness (method)
• farness (method)
• edgar-gilbert-populate (method)
• erdos-renyi-populate (method)
• preferential-attachment-populate (method)
• min-cut (method)
• add-paths (method)
• residual (method)
• shortest-path (method)
• all-paths (method)
• cliques (method)
• clustering-coefficient (method)
• closedp (method)
• connected-groups-of-size (method)
• minimum-spanning-tree (method)
• cycles (method)
• basic-cycles (method)
• strongly-connected-components (method)
• connected-components (method)
• connectedp (method)
• connected-component (method)
• neighbors (method)
• edge-neighbors (method)
• merge-edges (method)
• merge-nodes (method)
• reverse-edges (method)
• delete-edge (method)
• edge-value (method)
• edge-value (method)
• delete-node (method)
• node-edges (method)
• degree (method)
• node-edges (method)
• add-edge (method)
• add-node (method)
• subgraph (method)
• has-edge-p (method)
• has-node-p (method)
• nodes-w-values (method)
• nodes (method)
• nodes (method)
• edges-w-values (method)
• edges-w-values (method)
• edges (method)
• edges (method)
• from-value-matrix (method)
• to-value-matrix (method)
• from-plist (method)
• to-plist (method)
• graph-equal (method)
• populate (method)
• digraph-of (method)
• copy (method)
• edge-eq (method)
• edge-eq (method)
• edge-h (method)
• edge-h (method)
• node-h (method)
• node-h (method)

Direct slots

Slot: node-h

Initargs

:node-h

Initform

(make-hash-table)

Readers

node-h (generic function)

Writers

(setf node-h) (generic function)

Slot: edge-h

Initargs

:edge-h

Initform

(graph/graph::make-edge-hash-table)

Readers

edge-h (generic function)

Writers

(setf edge-h) (generic function)

Slot: edge-eq

Initargs

:edge-eq

Initform

(quote graph/graph::edge-equalp)

Readers

edge-eq (generic function)

Writers

(setf edge-eq) (generic function)

5.2 Internal definitions

5.2.1 Functions

Function: connected-component- NODE NEIGHBOR-FN

Package

graph/graph

Source

lisp.lisp (file)

Function: copy-hash HASH &optional TEST COMB

Return a copy of HASH.
Optional argument TEST specifies a new equality test to use for the copy. Second optional argument COMB specifies a function to use to combine the values of elements of HASH which collide in the copy due to a new equality test specified with TEST.

Package

graph/graph

Source

lisp.lisp (file)

Function: dir-edge-equalp EDGE1 EDGE2

Package

graph/graph

Source

lisp.lisp (file)

Function: edge-equalp EDGE1 EDGE2

Package

graph/graph

Source

lisp.lisp (file)

Function: edge-hash-equal HASH1 HASH2

Test edge hashes HASH1 and HASH2 for equality.

Package

graph/graph

Source

lisp.lisp (file)

Function: make-diedge-hash-table ()

Package

graph/graph

Source

lisp.lisp (file)

Function: make-edge-hash-table ()

Package

graph/graph

Source

lisp.lisp (file)

Function: node-hash-equal HASH1 HASH2

Test node hashes HASH1 and HASH2 for equality.

Package

graph/graph

Source

lisp.lisp (file)

Function: sxhash-edge EDGE

Package

graph/graph

Source

lisp.lisp (file)

Function: weigh-cut GRAPH CUT

Package

graph/graph

Source

lisp.lisp (file)

5.2.2 Generic functions

Generic Function: edge-eq OBJECT

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

Package

graph/graph

Methods

Method: edge-eq (DIGRAPH digraph)

automatically generated reader method

Source

lisp.lisp (file)

Method: (setf edge-eq) NEW-VALUE (DIGRAPH digraph)

automatically generated writer method

Source

lisp.lisp (file)

Method: edge-eq (GRAPH graph)

automatically generated reader method

Source

lisp.lisp (file)

Method: (setf edge-eq) NEW-VALUE (GRAPH graph)

automatically generated writer method

Source

lisp.lisp (file)

Generic Function: edge-h OBJECT

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

Package

graph/graph

Methods

Method: edge-h (DIGRAPH digraph)

automatically generated reader method

Source

lisp.lisp (file)

Method: (setf edge-h) NEW-VALUE (DIGRAPH digraph)

automatically generated writer method

Source

lisp.lisp (file)

Method: edge-h (GRAPH graph)

automatically generated reader method

Source

lisp.lisp (file)

Method: (setf edge-h) NEW-VALUE (GRAPH graph)

automatically generated writer method

Source

lisp.lisp (file)

Generic Function: node-h OBJECT

Generic Function: (setf node-h) NEW-VALUE OBJECT

Package

graph/graph

Methods

Method: node-h (GRAPH graph)

automatically generated reader method

Source

lisp.lisp (file)

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

automatically generated writer method

Source

lisp.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions