A graph that has arrows on its edges is called a directed graph:

But sometimes we have data that is undirected, allowing us to travel in both directions along an edge. Such a graph is less busy than a directed graph, and can be easier to understand:

The following code expands our graph utilities with new functions that let us draw undirected graphs:

(defun uedges->dot (edges)
   (maplist (lambda (lst)
               (mapc (lambda (edge)
                      (unless (assoc (car edge) (cdr lst))
                         (fresh-line)
                         (princ (dot-name (caar lst)))
                         (princ "--")
                         (princ (dot-name (car edge)))
                         (princ "[label="")
                         (princ (dot-label (cdr edge)))
                         (princ ""];")))
                     (cdar lst)))
             edges))

 (defun ugraph->dot (nodes edges)
   (princ "graph{")
    (nodes->dot nodes)
    (uedges->dot edges)
    (princ "}"))

 (defun ugraph->png (fname nodes edges)
    (dot->png fname
              (lambda ()
                (ugraph->dot nodes edges))))

This code is very similar to the code for creating our directed graphs. Let’s look at some of the differences.

The uedges->dot function is very similar to the edges->dot function . However, the graph we’re drawing may have multiple directed edges between the same nodes that we want to replace with a single, undirected edge. For instance, on our wizard map, we can walk from the garden to the living room by going east through the door. Of course, we can also walk from the living room to the garden by going west through the exact same door. In our undirected graph, we’ll want to collapse this; in essence, we just want to say, “There’s a door between the garden and living room.”

The uedges->dot function erases such duplicate edges by running through the list of edges using the maplist function. This is like the mapcar function, except that the function inside it receives the entire remainder of the list, not just the current item in the list:

> (mapcar #'print '(a b c))
A
B
C
...
> (maplist #'print '(a b c))
(A B C)
(B C)
(C)
...

The maplist function sends the print function everything in the list from the current item until the end. uedges->dot then uses the information about future nodes it gets from maplist to check whether the destination of the node appears later in the edge list. The actual checking is done with the assoc function, looking for the current edge in the list of remaining edges, calculated as (cdr lst) . In this case, it skips the edge so that only one of any pair of edges will be printed.

The ugraph->dot function is similar to the graph->dot function, except that it describes the graph as just a graph when generating the DOT data, instead of a digraph. The ugraph->png function is essentially identical to the graph->png function, except that it calls ugraph->dot instead of graph->dot.

We designed the dot->png function to accept different thunks so it could work with different DOT data generators. Now we’ve used this flexibility to generate these functions that output pictures for undirected graphs. For example, let’s try generating an undirected graph for the wizard’s house:

(ugraph->png "uwizard.dot" *wizard-nodes* *wizard-edges*)

Here, "uwizard.dot" is the name of the DOT file we want to create. The *wizard-nodes* and *wizard-edges* variables contain the data describing the nodes and edges of the map of the wizard’s world. This code generates the uwizard.dot.png file, which looks like this:

Now that you have a full suite of utilities for both directed and undirected graphs, write these functions to a file named graph-util.lisp, so you can access them from other programs.