Index: libabac/abac_graph.c
===================================================================
--- libabac/abac_graph.c	(revision 3613ab87ace94edbe5a0812b0dd0546e1116f546)
+++ libabac/abac_graph.c	(revision 06ef09cd307b513e6fa30f72ab67b28ff673e047)
@@ -13,4 +13,5 @@
     abac_role_t *role;
     char *name;
+    int refcount;
 
     abac_list_t *edges;
@@ -25,4 +26,5 @@
 // edge
 typedef struct _abac_edge_t {
+    int refcount;
     abac_vertex_t *vertex;
     abac_vertex_t *reverse_vertex;
@@ -83,7 +85,9 @@
     return clone;
 }
-
-/**
- * Add a vertex to the graph. Should only be called by abac_graph_add_credential.
+/**
+ * Add a vertex to the graph. Should only be called by
+ * abac_graph_add_credential. This returns an existing vertex with the refcount
+ * bumped, or a new vertex with a refcount of 1.  Either way it gets and
+ * references the vertex.
  */
 static abac_vertex_t *_get_vertex(abac_graph_t *graph, abac_role_t *role) {
@@ -97,4 +101,5 @@
     if (vertex == NULL) {
         vertex = abac_xmalloc(sizeof(abac_vertex_t));
+        vertex->refcount = 0;
         vertex->role = abac_role_dup(role);
         vertex->name = abac_role_string(vertex->role);
@@ -113,4 +118,5 @@
                 abac_vertex_t *tail_vertex = _get_vertex(graph, prereq);
                 abac_list_add(vertex->prereqs, tail_vertex);
+                printf("XXX add a prereq to vertex\n");
             );
         }
@@ -123,6 +129,94 @@
         HASH_ADD_KEYPTR(hh, graph->vertices, vertex->name, strlen(vertex->name), vertex);
     }
+    vertex->refcount++;
 
     return vertex;
+}
+
+/* forward decl */
+static void _free_edge(abac_edge_t *edge);
+/*
+ * Reduce the vertex reference count and free it if this is the last reference
+ */
+static void _free_vertex(abac_vertex_t *vertex) {
+    abac_edge_t *edge=NULL;
+    abac_vertex_t *pre=NULL;
+
+    --vertex->refcount;
+
+    if ( vertex->refcount > 0) return;
+
+    abac_role_free(vertex->role);
+
+    abac_list_foreach(vertex->edges, edge,
+        _free_edge(edge);
+    );
+    abac_list_free(vertex->edges);
+
+    abac_list_foreach(vertex->reverse_edges, edge,
+        _free_edge(edge);
+    );
+    abac_list_free(vertex->reverse_edges);
+
+    // Free the prereqs
+    if (vertex->prereqs != NULL) {
+        abac_list_foreach(vertex->prereqs, pre,
+            if (pre != NULL) {
+                _free_vertex(pre);
+                printf("YYY free a prereq to vertex\n");
+            }
+        );
+        abac_list_free(vertex->prereqs);
+    }
+
+    free(vertex);
+}
+
+/*
+ * Increment vertex reference count
+ */
+static abac_vertex_t *_dup_vertex(abac_vertex_t *v) {
+    v->refcount++;
+    return v;
+}
+
+
+/*
+ * create a new edge from the given head, tail and credential
+ */
+
+static abac_edge_t *_get_edge(abac_vertex_t *h, abac_vertex_t *t,
+        abac_credential_t *c) {
+
+    /* An edge does not own it's vertices.  Do not delete them from an edge
+     * reference. */
+    abac_edge_t *edge = abac_xmalloc(sizeof(abac_edge_t));
+    edge->refcount = 1;
+    edge->vertex = t;
+    edge->reverse_vertex = h;
+    /* Don't dup a null credential */
+    edge->credential = (c) ? abac_credential_dup(c): NULL;
+
+    return edge;
+}
+
+
+/**
+ * Increment the reference count
+ */
+static abac_edge_t *_dup_edge(abac_edge_t *e) {
+    e->refcount++;
+    return e;
+}
+
+/**
+ * Decerement the refcount and free it if this was the last reference.  NB
+ * edges do not own teh vertices, so they must be deleted elsewhere.
+ */
+static void _free_edge(abac_edge_t *edge) {
+    assert(edge && edge->refcount > 0);
+    if ( --edge->refcount > 0) return;
+    if (edge->credential) abac_credential_free(edge->credential);
+    free(edge);
 }
 
@@ -147,16 +241,16 @@
     // make sure we don't insert the same edge twice (ugh)
     abac_list_foreach(head_vertex->edges, edge,
-        if (edge->vertex == tail_vertex)
+        if (edge->vertex == tail_vertex) {
+            _free_vertex(head_vertex);
+            _free_vertex(tail_vertex);
             return 0;
+        }
     );
 
     // create the edge and add it
-    edge = abac_xmalloc(sizeof(abac_edge_t));
-    edge->vertex = tail_vertex;
-    edge->reverse_vertex = head_vertex;
-    edge->credential = abac_credential_dup(cred);
+    edge = _get_edge(head_vertex, tail_vertex, cred);
 
     abac_list_add(head_vertex->edges, edge);
-    abac_list_add(tail_vertex->reverse_edges, edge);
+    abac_list_add(tail_vertex->reverse_edges, _dup_edge(edge));
 
     // must re-derive edges
@@ -200,5 +294,5 @@
 
         free(current);
-        free(tail);
+        _free_edge(tail);
     }
 }
@@ -216,10 +310,7 @@
     debug_printf("derived edge %s <- %s\n", head->name, tail->name);
 
-    edge = abac_xmalloc(sizeof(abac_edge_t));
-    edge->vertex = tail;
-    edge->reverse_vertex = head;
-    edge->credential = NULL;
+    edge = _get_edge(head, tail, NULL);
     abac_list_add(head->edges, edge);
-    abac_list_add(tail->reverse_edges, edge);
+    abac_list_add(tail->reverse_edges, _dup_edge(edge));
 
     // add to list of derived edges
@@ -607,19 +698,5 @@
     while ((vertex = graph->vertices) != NULL) {
         HASH_DEL(graph->vertices, vertex);
-
-        abac_role_free(vertex->role);
-
-        abac_list_foreach(vertex->edges, edge,
-            if (edge->credential != NULL)
-                abac_credential_free(edge->credential);
-            free(edge);
-        );
-        abac_list_free(vertex->edges);
-
-        // the prereq vertices will be freed by the outer while loop
-        if (vertex->prereqs != NULL)
-            abac_list_free(vertex->prereqs);
-
-        free(vertex);
+        _free_vertex(vertex);
     }
 
