Programmatically Drawing Simple Graphviz Graphs

For my book, I had to draw a number of graphs. Obviously, I wanted to have a programmatic way to do that, and Graphviz is the goto-library for that. In Lisp, the interface to Graphviz is cl-dot, but, for me, it wasn't easy to figure out from the manual the "simple and easy" way to use it. I.e. I couldn't find a stupid beginner-level interface, so I had to code it myself. Here's the implementation that allows anyone with a REPL to send to Graphviz lists of edges and obtain graph images.

	(defclass dwim-graph () ())
	(defmethod cl-dot:graph-object-node ((graph (eql 'dwim-graph)) object)
	(make-instance 'cl-dot:node
	:attributes (list :label (format nil "~A" object)
	:shape :circle)))
	(defmacro dwim-graph ((file &key (directed t)) &body edges)
	`(progn
	(eval-when (:compile-toplevel :load-toplevel :execute)
	(defmethod cl-dot:graph-object-edges ((graph (eql 'dwim-graph)))
	,(coerce (mapcar (lambda (edge)
	(destructuring-bind (beg end &rest args) edge
	(append (list beg end)
	(unless directed `((:arrowhead :none)))
	args)))))
	edges)
	'vector)))
	(cl-dot:dot-graph
	(cl-dot:generate-graph-from-roots 'dwim-graph () '(:rankdir "LR"))
	,file
	:format (intern (or (etypecase ,file
	(pathname (pathname-type ,file))
	(string (let ((dot-pos (position #\. ,file
	:from-end t)))
	(when dot-pos
	(subseq ,file (1+ dot-pos))))))
	"jpg")
	:keyword))
	,file))
	#+directed-weighted-graph
	(dwim-graph ("/tmp/g.jpg")
	(0 1 4)
	(0 2 4)
	(1 3 4)
	(1 4 1)
	(2 3 2)
	(2 4 2)
	(3 5 3)
	(4 5 5))
	#+undirected-unweighted-graph
	(dwim-graph ("/tmp/g.jpg" :directed nil)
	(0 1)
	(0 2)
	(1 3)
	(1 4)
	(2 3)
	(2 4)
	(3 5)
	(4 5))

view raw dwim-graph.lisp hosted with ❤ by GitHub

Generated images:

Programming Algorithms: Graphs

This is a snippet of the "Graphs" chapter of the book.

Graphs have already been mentioned several times, in the book, in quite diverse contexts. Actually, if you are familiar with graphs you can spot opportunities to use them in quite different areas for problems that aren't explicitly formulated with graphs in mind. So, in this chapter, we'll discuss how to handle graphs to develop such intuition to some degree.

But first, let's list the most prominent examples of the direct graph applications, some of which we'll see here in action:

• pathfinding
• network analysis
• dependency analysis in planning, compilers, etc.
• various optimization problems
• distributing and optimizing computations
• knowledge representation and reasoning with it
• meaning representation in natural language processing

Graphs may be thought of as a generalization of trees: indeed, trees are, as we said earlier, connected directed acyclic graphs. But there's an important distinction in the patterns of the usage of graphs and trees. Graphs, much more frequently than trees, have weights associated with the edges, which adds a whole new dimension both to algorithms for processing them and to possible data that can be represented in the graph form. So, while the main application of trees is reflecting some hierarchy, for graphs, it is often more about determining connectedness and its magnitude, based on the weights.

Graph Representations

A graph is, basically, a set of nodes (called "vertices", V) and an enumeration of their pairs ("edges", E). The edges may be directed or undirected (i.e. bidirectional), and also weighted or unweighted. There are many ways that may be used to represent these sets, which have varied utility for different situations. Here are the most common ones:

• as a linked structure: (defstruct node data links) where links may be either a list of other nodes, possibly, paired with weights, or a list of edge structures represented as (defsturct edge source destination weight). For directed graphs, this representation will be similar to a singly-linked list but for undirected — to a heavier doubly-linked one
• as an adjacency matrix (V x V). This matrix is indexed by vertices and has zeroes when there's no connection between them and some nonzero number for the weight (1 — in case of unweighted graphs) when there is a connection. Undirected graphs have a symmetric adjacency matrix and so need to store only the abovediagonal half of it
• as an adjacency list that enumerates for each vertex the other vertices it's connected to and the weights of connections
• as an incidence matrix (V x E). This matrix is similar to the previous representation, but with much more wasted space. The adjacency list may be thought of as a sparse representation of the incidence matrix. The matrix representation may be more useful for hypergraphs (that have more than 2 vertices for each edge), though
• just as a list of edges

More details about of the book may be found on its website.