strongly connected components

[ccc.git] / tarjan.h

diff --git a/tarjan.h b/tarjan.h
new file mode 100644 (file)
index 0000000..b2a8fbb
--- /dev/null
+++ b/tarjan.h
@@ -0,0 +1,38 @@
+#ifndef SCC_H
+#define SCC_H
+
+struct edge {
+       void *from;
+       void *to;
+};
+
+struct components {
+       int nnodes;
+       void **nodes;
+       struct components *next;
+};
+
+#define FOREACHCOMP(x, l) for(struct components *x = l; x != NULL; x = x->next)
+
+/**
+ * Calculate the strongly connected components using Tarjan's algorithm:
+ * en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
+ *
+ * Returns NULL when there are invalid edges
+ *
+ * @param number of nodes
+ * @param data of the nodes
+ * @param number of edges
+ * @param data of edges
+ */
+struct components *scc(int nn, void **nodes, int ne, struct edge **edges);
+
+/**
+ * Free a list of components
+ *
+ * @param cs components
+ * @param freefun function to free the data with, if NULL, data isn't freed
+ */
+void components_free(struct components *cs, void (*freefun)(void *));
+
+#endif