initial commit

diff --git a/.gitignore b/.gitignore
new file mode 100644 (file)
index 0000000..cb4ead0
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+.*.swp
+*.o

diff --git a/graph/adj.c b/graph/adj.c
new file mode 100644 (file)
index 0000000..ec9cd0c
--- /dev/null
+++ b/graph/adj.c
@@ -0,0 +1,57 @@
+#include "adj.h"
+#include <stdlib.h>
+#include <errno.h>
+
+struct graph *
+new_graph (unsigned int nv)
+{
+  struct graph *g;  
+
+  if (!nv)
+    return NULL;
+
+  if (!(g = malloc (sizeof *g)))
+    return NULL;
+
+  g->nv = nv;
+
+  if (!(g->v = calloc (nv, sizeof *g->v)))
+    {
+      free (g);
+      return NULL;
+    }
+
+  return g;
+}
+
+int
+new_arc (struct graph *g, unsigned int vi, unsigned int vj)
+{
+  struct edge *e;
+
+  if (vi >= g->nv || vj >= g->nv)
+    return -EINVAL;
+
+  if (!(e = malloc (sizeof *e)))
+    return -ENOMEM;
+
+  e->to = &g->v[vj];
+  e->next = g->v[vi].adj;
+  g->v[vi].adj = e;
+
+  return 0;
+}
+
+int
+new_edge (struct graph *g, unsigned int vi, unsigned int vj)
+{
+  int err;
+
+  if ((err = new_arc (g, vi, vj)))
+    return err;
+
+  if (vi != vj && (err = new_arc (g, vj, vi)))
+    return err; /* should delete the other arc but fuck it we ball */
+
+  return 0;
+}

diff --git a/graph/adj.h b/graph/adj.h
new file mode 100644 (file)
index 0000000..680d6b0
--- /dev/null
+++ b/graph/adj.h
@@ -0,0 +1,33 @@
+#ifndef GRAPH_H
+#define GRAPH_H
+
+/* adjacency list implementation */
+
+struct vertex;
+struct edge;
+struct graph;
+
+struct edge
+{
+  struct vertex *to;
+  struct edge *next;
+};
+
+struct vertex
+{
+  struct edge *adj;
+};
+
+struct graph
+{
+  struct vertex *v;
+  unsigned int nv;
+};
+
+struct graph *
+new_graph (unsigned int nv);
+
+int
+new_edge (struct graph *g, unsigned int vi, unsigned int vj);
+
+#endif /* GRAPH_H  */