## GRAPH/GRAPH - simple graph data structure and algorithms

### Abstract

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.

The code is available under the GNU General Public License.

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

### Contents

1. Source
2. Introduction
3. The GRAPH/GRAPH dictionary
4. Acknowledgements

### Source

GRAPH/GRAPH together with this documentation can be found at http://github.com/eschulte/graph.

### Introduction

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

### The GRAPH/GRAPH dictionary

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

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

[Generic function]

[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 => result

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 => result

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 => result

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 => result

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 => result

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 => result

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 => result

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 => result

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 => result

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 => result

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 => result

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 => result

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 => result

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 => result

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 => result

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.

### Acknowledgements

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