Repository files navigation

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:

• Its assumed that the nodes and edges are “light” things like keywords or strings and can be compared via#'equal.
• All edges are directed.
• Edge weights are not supported.
• Other thansubgraph andpaths-to, no fancy algorithms are provided.

• Compatibility
• Usage
  • Importing
  • API
    • Thegraph Type
      • make-graph, graph-nodes, graph-edges
      • add-node!, add-edge!
      • leaf?, leaves
      • nodes-to, paths-to
      • subgraph
    • 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 usein-package directly for brevity.

Thegraph 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 andgraph-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 subgraphgraph 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 (seeto-dot below), we would see onlya -> c.

(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 gstream)))

Then you can either write it to apng withdot:

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

Or visualise it directly withxdot:

xdot deps.dot