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.

See the GRAPH/JSON and GRAPH/DOT libraries for serialization and visualization of graphs.

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

Source:
http://github.com/eschulte/graph.

- Source
- Introduction
- The GRAPH/GRAPH dictionary
`add-edge`

`add-node`

`add-paths`

`basic-cycles`

`betweenness`

`cliques`

`closedp`

`closeness`

`clustering-coefficient`

`connected-component`

`connected-components`

`connected-groups-of-size`

`connectedp`

`copy`

`cycles`

`degeneracy`

`degree`

`delete-edge`

`delete-node`

`digraph`

`digraph-of`

`edgar-gilbert-digraph`

`edgar-gilbert-graph`

`edgar-gilbert-populate`

`edge-neighbors`

`edge-value`

`edges`

`edges-w-values`

`erdos-renyi-digraph`

`erdos-renyi-graph`

`erdos-renyi-populate`

`farness`

`from-plist`

`from-value-matrix`

`graph`

`graph-equal`

`graph-of`

`has-edge-p`

`has-node-p`

`indegree`

`k-cores`

`katz-centrality`

`levels`

`max-flow`

`merge-edges`

`merge-nodes`

`min-cut`

`minimum-spanning-tree`

`neighbors`

`node-edges`

`nodes`

`nodes-w-values`

`outdegree`

`populate`

`precedents`

`preferential-attachment-populate`

`residual`

`reverse-edges`

`shortest-path`

`strongly-connected-components`

`subgraph`

`to-plist`

`to-value-matrix`

`topological-sort`

- Acknowledgements

Graphs are composed of two hash tables, nodes and edges. The node hash is keyed by node and holds the edges containing that node, while the edge hash is keyed by edge containing any optional edge value.

```
Nodes Edges
------- -------
+----Graph G-----+ key | value key | value
| 3 2 | -----+--------- -------+----------
| a---b---c g | a | (a b) (a b) | 3
| 1| |1 | b | (b d) (b c) (b d) | 1
| d---e---f | c | (b c) (c e) (b c) | 2
| 2 3 | d | (b d) (d e) (c e) | 1
+----------------+ e | (d e) (c e) (d e) | 2
f | (e f) (e f) | 3
g |
```

Graphs are CLOS objects which are constructed with the usual ```
make
instance
```

and are populated with the `populate`

function.

```
(defvar *graph* (populate (make-instance 'graph)
:nodes '(a b c d e f g)
:edges-w-values '(((a b) . 3)
((b d) . 1)
((b c) . 2)
((c e) . 1)
((d e) . 2)
((e f) . 3))))
```

Standard accessors are provided.

```
* (nodes *graph*)
(A B C D E F G)
* (edges *graph*)
((A B) (B D) (B C) (C E) (D E) (E F))
* (node-edges *graph* 'b)
((B C) (B D) (A B))
* (edge-value *graph* '(d e))
2
```

Nodes and edges may be removed using `delete-node`

and
`delete-edge`

, or using setf methods on any of the accessors above.

```
* (delete-edge *graph* '(e f))
3
* (edges *graph*)
((A B) (B D) (B C) (C E) (D E))
* (setf (nodes *graph*) (remove 'a (nodes *graph*)))
(B C D E F G)
* (edges *graph*)
((B D) (B C) (C E) (D E))
```

Some more sophisticated graph algorithms are implemented. A couple are shown below, see the dictionary for a complete list.

```
* (shortest-path *graph* 'b 'e)
((B C) (C E))
* (connected-components *graph*)
((G) (B D C E) (F))
* (setf (nodes *graph*) '(B D C E))
(B C D E)
* (min-cut *graph*)
((B C) (E D))
2
```

Additionally digraphs represent graphs with directed edges. Starting with the original graph above we get the following.

```
* (strongly-connected-components *graph*)
((G) (D F E C B A))
* (strongly-connected-components (digraph-of *graph*))
((G) (A) (B) (D) (C) (E) (F))
* (delete-edge *graph* '(d e))
2
* (push '(e d) (edges *graph*))
((A B) (B D) (B C) (C E) (E D) (E F))
* (push '(d c) (edges *graph*))
((A B) (B D) (B C) (C E) (E D) (E F) (D C))
* (strongly-connected-components (digraph-of *graph*))
((G) (A) (B) (D E C) (F))
```

[Generic function]**add-edge** *graph edge &optional value* =>

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

[Generic function]**add-node** *graph node* => *result*

Add NODE to GRAPH.

[Generic function]**add-paths** *graph path1 path2* => *result*

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

[Generic function]**basic-cycles** *graph* => *result*

Return all basic cycles in the 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.

[Generic function]**cliques** *graph* => *result*

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

[Generic function]**closedp** *graph nodes* => *result*

Return true if NODES are fully connected in GRAPH.

[Generic function]**closeness** *graph node* => *result*

Inverse of the`farness`

for NODE in GRAPH.

[Generic function]**clustering-coefficient** *graph* => *result*

Fraction of connected triples which are closed.

[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 @begin example the edge @end example :WEAK ....... connections may traverse edges in any direction @begin example regardless of the edge direction @end example :UNILATERAL . two nodes a and b connected iff a is strongly connected @begin example to b or b is strongly connected to a @end example

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

[Generic function]**connected-groups-of-size** *graph size* => *result*

Return all connected node groups of SIZE in GRAPH.

[Generic function]**connectedp** *graph &key type* =>

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

.

[Generic function]**copy** *graph* => *result*

Return a copy of GRAPH.

[Generic function]**cycles** *graph* => *result*

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

[Generic function]**degeneracy** *graph* => *result*

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.

[Generic function]**degree** *graph node* => *result*

Return the degree of NODE in GRAPH.

[Generic function]**delete-edge** *graph edge* => *result*

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

[Generic function]**delete-node** *graph node* => *result*

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

[Standard class]**digraph**

A`graph`

with directed edges.

[Generic function]**digraph-of** *graph* => *result*

Copy GRAPH into a`digraph`

and return.

[Function]**edgar-gilbert-digraph** *n p* => *result*

[Function]**edgar-gilbert-graph** *n p* => *result*

[Generic function]**edgar-gilbert-populate** *graph p* => *result*

Populate GRAPH including every possible edge with probability P.

[Generic function]**edge-neighbors** *graph edge* => *result*

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

[Generic accessor]**edge-value** *graph edge* => *result*
`(setf (`**edge-value** *graph edge*`)` *new*`)`

Return the value of EDGE in GRAPH.

[Generic accessor]**edges** *graph* => *result*
`(setf (`**edges** *graph*`)` *new*`)`

Return a list of the edges in GRAPH.

[Generic accessor]**edges-w-values** *graph* => *result*
`(setf (`**edges-w-values** *graph*`)` *new*`)`

Return an alist of edges of GRAPH with their values.

[Function]**erdos-renyi-digraph** *n m* => *result*

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

[Function]**erdos-renyi-graph** *n m* => *result*

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

[Generic function]**erdos-renyi-populate** *graph m* => *result*

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

[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`

.

[Generic function]**from-plist** *graph plist* => *result*

Populate GRAPH with the contents of PLIST.

[Generic function]**from-value-matrix** *graph matrix* => *result*

Populate GRAPH from the value matrix MATRIX.

[Standard 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`

).

[Generic function]**graph-equal** *graph1 graph2* => *result*

Compare GRAPH1 and GRAPH2 for equality.

[Generic function]**graph-of** *digraph* => *result*

Copy DIGRAPH into a`graph`

and return.

[Generic function]**has-edge-p** *graph edge* => *result*

Return`true`

if GRAPH has edge EDGE.

[Generic function]**has-node-p** *graph node* => *result*

Return`true`

if GRAPH has node NODE.

[Generic function]**indegree** *digraph node* => *result*

The number of edges directed to NODE in GRAPH.

[Generic function]**k-cores** *graph* => *result*

Return the k-cores of 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`

.

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

[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`

.

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

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

[Generic function]**min-cut** *graph* => *result*

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

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

[Generic function]**neighbors** *graph node* => *result*

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

[Generic accessor]**node-edges** *graph node* => *result*
`(setf (`**node-edges** *graph node*`)` *new*`)`

Return the value of NODE in GRAPH.

[Generic accessor]**nodes** *graph* => *result*
`(setf (`**nodes** *graph*`)` *new*`)`

Return a list of the nodes in GRAPH.

[Generic function]**nodes-w-values** *graph* => *result*

Return an alist of nodes of GRAPH with their values.

[Generic function]**outdegree** *digraph node* => *result*

The number of edges directed from NODE in DIGRAPH.

[Generic function]**populate** *graph &key nodes edges edges-w-values* =>

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

[Generic function]**precedents** *digraph node* => *result*

Return all nodes preceding NODE in an edge of DIGRAPH.

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

[Generic function]**residual** *graph flow* => *result*

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.

[Generic function]**reverse-edges** *graph* => *result*

Return a copy of GRAPH with all edges reversed.

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

[Generic function]**strongly-connected-components** *graph* => *result*

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

[Generic function]**subgraph** *graph nodes* => *result*

Return the subgraph of GRAPH restricted to 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.

[Generic function]**to-value-matrix** *graph* => *result*

Return the value matrix of GRAPH.

[Generic function]**topological-sort** *digraph* => *result*

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.

This documentation was prepared with a hacked up version of DOCUMENTATION-TEMPLATE.