Wow, what a simple graph. Sometimes you just want to add some nodes and edges, and see what it all looks like, right? This library lets you do that. It has no dependencies.

Keep in mind that:

• Nodes are compared via #'equalp.
• All edges are directed.
• Edge weights are not supported.
• Other than a few conveniences, no fancy algorithms are provided.

• Compatibility
• Usage
  • Importing
  • API
    • The graph Type
      • make-graph, graph-nodes, graph-edges
      • add-node!, add-edge!
      • leaf?, leaves
    • Algorithms
      • nodes-to, paths-to
      • subgraph
      • flip-edges
    • Visualisation
      • to-dot, to-dot-with-stream

Written using only standard Common Lisp, so should be portable to all implementations.

When importing, you should probably use a nickname:

(:local-nicknames (:g :simple-graph))

Although the examples below use in-package directly for brevity.

The graph itself is just a simple struct with a two Hash Tables:

• Nodes: node -> T
• Edges: node -> list-of-node

To create one:

(in-package :simple-graph)
(make-graph)

As you can see, graph-nodes and graph-edges can be used to access the struct fields.

To mutably add entries to the graph (hence the !):

(in-package :simple-graph)
(let ((g (make-graph)))
  (add-node! g :a)
  (add-node! g :b)
  (add-edge! g :a :b)
  g)

#S(GRAPH
   :NODES #<HASH-TABLE :TEST EQUAL :COUNT 2 {1008601393}>
   :EDGES #<HASH-TABLE :TEST EQUAL :COUNT 1 {1008601433}>)

Note that:

• add-node! will ignore multiple attempts to add the same node.
• Multiple edges can be added between two of the same node.
• Edges between non-existent nodes can be added.

Is some given node a leaf node (i.e. has no outbound edges)?

(in-package :simple-graph)
(let ((g (make-graph)))
  (add-node! g :a)
  (add-node! g :b)
  (add-edge! g :a :b)
  (leaf? g :b))

T

To fetch all the leaves:

(in-package :simple-graph)
(let ((g (make-graph)))
  (add-node! g :a)
  (add-node! g :b)
  (add-node! g :c)
  (add-edge! g :a :b)
  (add-edge! g :a :c)
  (leaves g))

(:C :B)

To find all nodes with a directed edge to some given node:

(in-package :simple-graph)
(let ((g (make-graph)))
  (add-node! g :a)
  (add-node! g :b)
  (add-node! g :c)
  (add-node! g :d)
  (add-edge! g :a :c)
  (add-edge! g :a :b)
  (add-edge! g :b :d)
  (add-edge! g :c :d)
  (nodes-to g :d))

(:C :B)

All paths that lead to a given node. The result sublists are in reverse order:

(in-package :simple-graph)
(let ((g (make-graph)))
  (add-node! g :a)
  (add-node! g :b)
  (add-node! g :c)
  (add-node! g :d)
  (add-edge! g :a :c)
  (add-edge! g :a :b)
  (add-edge! g :b :d)
  (add-edge! g :c :d)
  (paths-to g :d))

((:D :C :A) (:D :B :A))

To yield a new subgraph graph that starts from a given node (or nodes):

(in-package :simple-graph)
(let ((g (make-graph)))
  (add-node! g :a)
  (add-node! g :b)
  (add-node! g :c)
  (add-node! g :d)
  (add-node! g :e)
  (add-edge! g :a :c)
  (add-edge! g :d :e)
  (subgraph g :a)))

#S(GRAPH
   :NODES #<HASH-TABLE :TEST EQUAL :COUNT 2 {1008A4C3A3}>
   :EDGES #<HASH-TABLE :TEST EQUAL :COUNT 1 {1008A4C443}>)

If visualised (see to-dot below), we would see only a -> c.

Reverse the direction of all edges.

(in-package :simple-graph)
(let ((g (make-graph)))
  (add-node! g :a)
  (add-node! g :b)
  (add-node! g :c)
  (add-edge! g :a :b)
  (add-edge! g :a :c)
  (flip-edges g))

(in-package :simple-graph)
(let ((g (make-graph)))
  (add-node! g "A")
  (add-node! g "B")
  (add-node! g "C")
  (add-node! g "D")
  (add-node! g "E")
  (add-node! g "F")
  (add-edge! g "A" "B")
  (add-edge! g "A" "C")
  (add-edge! g "B" "D")
  (add-edge! g "C" "D")
  (add-edge! g "E" "F")
  (to-dot (subgraph g "A")))

graph {
  \"A\";
  \"C\";
  \"D\";
  \"B\";
  \"A\" -- \"B\";
  \"A\" -- \"C\";
  \"C\" -- \"D\";
  \"B\" -- \"D\";
}

Similarly, to write a graph’s DOT format directly to a file:

(in-package :simple-graph)
(let ((g (make-graph)))
  (add-node! g "A")
  (add-node! g "B")
  (add-node! g "C")
  (add-node! g "D")
  (add-edge! g "A" "B")
  (add-edge! g "A" "C")
  (add-edge! g "B" "D")
  (add-edge! g "C" "D")
  (with-open-file (stream #p"deps.dot" :direction :output :if-exists :supersede)
    (to-dot-with-stream g stream)))

Then you can either write it to a png with dot:

cat deps.dot | dot -Tpng -o deps.png

Or visualise it directly with xdot:

xdot deps.dot