Representing a directed acyclic graph in Common Lisp

Question

Normally, to represent a basic undirected graph in Lisp, I can create a list of parent nodes and their corresponding children nodes, as was discussed in this question (illustrated below for convenience).

this graph yields a list of edges:

(1 (2 6 7 8) 3 (4 (9 12)) 5 (10 11))

This works in the case of a tree or any other undirected graph. However, this type of representation breaks down when we want to represent a directed acyclic graph where each node can have multiple parents:

Now, Node 8 has multiple parents (2, 3), but when we attempt to represent this, we lose the ability to tell if node 8 is connected to two parent nodes, or if there are two node 8's:

(1 (2 6 7 8) (3 8) (4 (9 12)) (5 10 11))

In the case of a graph with unique nodes, we certainly can make this assumption, but to my knowledge, DAGs can have duplicate nodes ... so how do we deal with this? Further, how do we represent it as a list in Lisp?

sds sds · Accepted Answer · 2018-09-06T18:24:29

The right way to represent a DAG is a collection of nodes (vertices):

(defstruct node
  payload
  children)

Since the struct has just two slots, one can use, of course, cons cells instead.

The list representation of the tree you give conflates payload with a childless node and messes up the rightmost branch. The correct representation is

(1 (2 (6) (7) (8)) (3) (4 (9 (12))) (5 (10) (11)))

Now, the DAG that shares the childless node (8) between the children of nodes (2 ...) and (3 ...) should merely share the cell:

(1 (2 (6) (7) #1=(8)) (3 #1#) (4 (9 (12))) (5 (10) (11)))

See #n= and #n# for the reader notation. Of course, you should not use them to create DAGs.

Here is how one would create the DAG:

(defun make-node (&key payload children)
  (cons payload children))
(defparameter *my-dag*
  (let ((shared-mode (make-node :payload 8)))
    (make-node
     :payload 1
     :children
     (list (make-node :payload 2
                      :children (list (make-node :payload 6)
                                      (make-node :payload 7)
                                      shared-mode))
           (make-node :payload 3
                      :children (list shared-mode))
           (make-node :payload 4
                      :children (list (make-node :payload 9
                                                 :children (list (make-node :payload 12)))))
           (make-node :payload 5
                      :children (list (make-node :payload 10)
                                      (make-node :payload 11)))))))
(setq *print-circle* t)
*my-dag*
==> (1 (2 (6) (7) #1=(8)) (3 #1#) (4 (9 (12))) (5 (10) (11)))

Representing a directed acyclic graph in Common Lisp

2 Answers