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.
add-edgeadd-nodeadd-pathsbasic-cyclesbetweennesscliquesclosedpclosenessclustering-coefficientconnected-componentconnected-componentsconnected-groups-of-sizeconnectedpcopycyclesdegeneracydegreedelete-edgedelete-nodedigraphdigraph-ofedgar-gilbert-digraphedgar-gilbert-graphedgar-gilbert-populateedge-neighborsedge-valueedgesedges-w-valueserdos-renyi-digrapherdos-renyi-grapherdos-renyi-populatefarnessfrom-plistfrom-value-matrixgraphgraph-equalgraph-ofhas-edge-phas-node-pindegreek-coreskatz-centralitylevelsmax-flowmerge-edgesmerge-nodesmin-cutminimum-spanning-treeneighborsnode-edgesnodesnodes-w-valuesoutdegreepopulateprecedentspreferential-attachment-populateresidualreverse-edgesshortest-pathstrongly-connected-componentssubgraphto-plistto-value-matrixtopological-sortGraphs 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 => result
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 => 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 thefarnessfor 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 toconnected-componentand 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 toconnected-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. Thecarof each element of the alist identifies k-cores and thecdrholds 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
Agraphwith directed edges.
[Generic function]
digraph-of graph => result
Copy GRAPH into adigraphand 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 inshortest-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 ofnodesconnected byedges. 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-flowandmin-cut).
[Generic function]
graph-equal graph1 graph2 => result
Compare GRAPH1 and GRAPH2 for equality.
[Generic function]
graph-of digraph => result
Copy DIGRAPH into agraphand return.
[Generic function]
has-edge-p graph edge => result
Returntrueif GRAPH has edge EDGE.
[Generic function]
has-node-p graph node => result
Returntrueif 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 inshortest-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 inshortest-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.
This documentation was prepared with a hacked up version of DOCUMENTATION-TEMPLATE.