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 dictionary
    1. add-edge
    2. add-node
    3. add-paths
    4. basic-cycles
    5. betweenness
    6. cliques
    7. closedp
    8. closeness
    9. clustering-coefficient
    10. connected-component
    11. connected-components
    12. connected-groups-of-size
    13. connectedp
    14. copy
    15. cycles
    16. degeneracy
    17. degree
    18. delete-edge
    19. delete-node
    20. digraph
    21. digraph-of
    22. edgar-gilbert-digraph
    23. edgar-gilbert-graph
    24. edgar-gilbert-populate
    25. edge-neighbors
    26. edge-value
    27. edges
    28. edges-w-values
    29. erdos-renyi-digraph
    30. erdos-renyi-graph
    31. erdos-renyi-populate
    32. farness
    33. from-plist
    34. from-value-matrix
    35. graph
    36. graph-equal
    37. graph-of
    38. has-edge-p
    39. has-node-p
    40. indegree
    41. k-cores
    42. katz-centrality
    43. levels
    44. max-flow
    45. merge-edges
    46. merge-nodes
    47. min-cut
    48. minimum-spanning-tree
    49. neighbors
    50. node-edges
    51. nodes
    52. nodes-w-values
    53. outdegree
    54. populate
    55. precedents
    56. preferential-attachment-populate
    57. residual
    58. reverse-edges
    59. shortest-path
    60. strongly-connected-components
    61. subgraph
    62. to-plist
    63. to-value-matrix
    64. topological-sort
  4. Acknowledgements

 

Source

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


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


Sum of the distance from NODE to every other node in connected GRAPH.


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


Combined measure of number and nearness of nodes to NODE.


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


Return the maximum flow from FROM and TO in GRAPH. GRAPHS must be a network with numeric values of all edges. The Ford-Fulkerson algorithm is used.


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


Return a minimum spanning tree of GRAPH. Prim's algorithm 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 => result


Return the shortest path in GRAPH from A to B. GRAPH must be a directed graph. Dijkstra's algorithm is used.


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