1 files changed, 338 insertions, 0 deletions
diff --git a/girepository/cmph/graph.c b/girepository/cmph/graph.c
new file mode 100644
index 00000000..c29fd8b9
--- /dev/null
+++ b/girepository/cmph/graph.c
@@ -0,0 +1,338 @@
+#include "graph.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <assert.h>
+#include <string.h>
+#include "vstack.h"
+#include "bitbool.h"
+
+//#define DEBUG
+#include "debug.h"
+
+/* static const cmph_uint8 bitmask[8] = { 1, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7 }; */
+/* #define GETBIT(array, i) (array[(i) / 8] & bitmask[(i) % 8]) */
+/* #define SETBIT(array, i) (array[(i) / 8] |= bitmask[(i) % 8]) */
+/* #define UNSETBIT(array, i) (array[(i) / 8] &= (~(bitmask[(i) % 8]))) */
+
+#define abs_edge(e, i) (e % g->nedges + i * g->nedges)
+
+struct __graph_t
+{
+	cmph_uint32 nnodes;
+	cmph_uint32 nedges;
+	cmph_uint32 *edges;
+	cmph_uint32 *first;
+	cmph_uint32 *next;
+        cmph_uint8  *critical_nodes;   /* included -- Fabiano*/
+        cmph_uint32 ncritical_nodes;   /* included -- Fabiano*/
+	cmph_uint32 cedges;
+	int shrinking;
+};
+
+static cmph_uint32 EMPTY = UINT_MAX;
+
+graph_t *graph_new(cmph_uint32 nnodes, cmph_uint32 nedges)
+{
+	graph_t *graph = (graph_t *)malloc(sizeof(graph_t));
+	if (!graph) return NULL;
+
+	graph->edges = (cmph_uint32 *)malloc(sizeof(cmph_uint32) * 2 * nedges);
+	graph->next =  (cmph_uint32 *)malloc(sizeof(cmph_uint32) * 2 * nedges);
+	graph->first = (cmph_uint32 *)malloc(sizeof(cmph_uint32) * nnodes);
+        graph->critical_nodes = NULL; /* included -- Fabiano*/
+	graph->ncritical_nodes = 0;   /* included -- Fabiano*/
+	graph->nnodes = nnodes;
+	graph->nedges = nedges;
+
+	graph_clear_edges(graph);
+	return graph;
+}
+
+
+void graph_destroy(graph_t *graph)
+{
+	DEBUGP("Destroying graph\n");
+	free(graph->edges);
+	free(graph->first);
+	free(graph->next);
+        free(graph->critical_nodes); /* included -- Fabiano*/
+	free(graph);
+	return;
+}
+
+void graph_print(graph_t *g)
+{
+	cmph_uint32 i, e;
+	for (i = 0; i < g->nnodes; ++i)
+	{
+		DEBUGP("Printing edges connected to %u\n", i);
+		e = g->first[i];
+		if (e != EMPTY)
+		{
+			printf("%u -> %u\n", g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)]);
+			while ((e = g->next[e]) != EMPTY)
+			{
+				printf("%u -> %u\n", g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)]);
+			}
+		}
+			
+	}
+	return;
+}
+
+void graph_add_edge(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
+{
+	cmph_uint32 e = g->cedges;
+
+	assert(v1 < g->nnodes);
+	assert(v2 < g->nnodes);
+	assert(e < g->nedges);
+	assert(!g->shrinking);
+
+	g->next[e] = g->first[v1];
+	g->first[v1] = e;
+	g->edges[e] = v2;
+
+	g->next[e + g->nedges] = g->first[v2];
+	g->first[v2] = e + g->nedges;
+	g->edges[e + g->nedges] = v1;
+
+	++(g->cedges);
+}
+
+static int check_edge(graph_t *g, cmph_uint32 e, cmph_uint32 v1, cmph_uint32 v2)
+{
+	DEBUGP("Checking edge %u %u looking for %u %u\n", g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)], v1, v2);
+	if (g->edges[abs_edge(e, 0)] == v1 && g->edges[abs_edge(e, 1)] == v2) return 1;
+	if (g->edges[abs_edge(e, 0)] == v2 && g->edges[abs_edge(e, 1)] == v1) return 1;
+	return 0;
+}
+
+cmph_uint32 graph_edge_id(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
+{
+	cmph_uint32 e;
+	e = g->first[v1];
+	assert(e != EMPTY);
+	if (check_edge(g, e, v1, v2)) return abs_edge(e, 0);
+	do
+	{
+		e = g->next[e];
+		assert(e != EMPTY);
+	}
+	while (!check_edge(g, e, v1, v2));
+	return abs_edge(e, 0);
+}
+static void del_edge_point(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
+{
+	cmph_uint32 e, prev;
+
+	DEBUGP("Deleting edge point %u %u\n", v1, v2);
+	e = g->first[v1];
+	if (check_edge(g, e, v1, v2)) 
+	{
+		g->first[v1] = g->next[e];
+		//g->edges[e] = EMPTY;
+		DEBUGP("Deleted\n");
+		return;
+	}
+	DEBUGP("Checking linked list\n");
+	do
+	{
+		prev = e;
+		e = g->next[e];
+		assert(e != EMPTY);
+	}
+	while (!check_edge(g, e, v1, v2));
+
+	g->next[prev] = g->next[e];
+	//g->edges[e] = EMPTY;
+	DEBUGP("Deleted\n");
+}
+
+	
+void graph_del_edge(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
+{
+	g->shrinking = 1;
+	del_edge_point(g, v1, v2);
+	del_edge_point(g, v2, v1);
+}
+
+void graph_clear_edges(graph_t *g)
+{
+	cmph_uint32 i;
+	for (i = 0; i < g->nnodes; ++i) g->first[i] = EMPTY;
+	for (i = 0; i < g->nedges*2; ++i) 
+	{
+		g->edges[i] = EMPTY;
+		g->next[i] = EMPTY;
+	}
+	g->cedges = 0;
+	g->shrinking = 0;
+}
+
+static cmph_uint8 find_degree1_edge(graph_t *g, cmph_uint32 v, cmph_uint8 *deleted, cmph_uint32 *e)
+{
+	cmph_uint32 edge = g->first[v];
+	cmph_uint8 found = 0;
+	DEBUGP("Checking degree of vertex %u\n", v);
+	if (edge == EMPTY) return 0;
+	else if (!(GETBIT(deleted, abs_edge(edge, 0)))) 
+	{
+		found = 1;
+		*e = edge;
+	}
+	while(1)
+	{
+		edge = g->next[edge];
+		if (edge == EMPTY) break;
+		if (GETBIT(deleted, abs_edge(edge, 0))) continue;
+		if (found) return 0;
+		DEBUGP("Found first edge\n");
+		*e = edge;
+		found = 1;
+	}
+	return found;
+}
+
+static void cyclic_del_edge(graph_t *g, cmph_uint32 v, cmph_uint8 *deleted)
+{
+
+	cmph_uint32 e = 0;
+	cmph_uint8 degree1;
+	cmph_uint32 v1 = v;
+	cmph_uint32 v2 = 0;
+
+	degree1 = find_degree1_edge(g, v1, deleted, &e);
+	if (!degree1) return;
+	while(1) 
+	{
+		DEBUGP("Deleting edge %u (%u->%u)\n", e, g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)]);
+		SETBIT(deleted, abs_edge(e, 0));
+		
+		v2 = g->edges[abs_edge(e, 0)];
+		if (v2 == v1) v2 = g->edges[abs_edge(e, 1)];
+
+		DEBUGP("Checking if second endpoint %u has degree 1\n", v2); 
+		degree1 = find_degree1_edge(g, v2, deleted, &e);
+		if (degree1) 
+		{
+			DEBUGP("Inspecting vertex %u\n", v2);
+			v1 = v2;
+		}
+		else break;
+	}
+}
+
+int graph_is_cyclic(graph_t *g)
+{
+	cmph_uint32 i;
+	cmph_uint32 v;
+	cmph_uint8 *deleted = (cmph_uint8 *)malloc((g->nedges*sizeof(cmph_uint8))/8 + 1);
+	size_t deleted_len = g->nedges/8 + 1;
+	memset(deleted, 0, deleted_len);
+
+	DEBUGP("Looking for cycles in graph with %u vertices and %u edges\n", g->nnodes, g->nedges);
+	for (v = 0; v < g->nnodes; ++v)
+	{
+		cyclic_del_edge(g, v, deleted);
+	}
+	for (i = 0; i < g->nedges; ++i)
+	{
+		if (!(GETBIT(deleted, i))) 
+		{
+			DEBUGP("Edge %u %u->%u was not deleted\n", i, g->edges[i], g->edges[i + g->nedges]);
+			free(deleted);
+			return 1;
+		}
+	}
+	free(deleted);
+	return 0;
+}
+
+cmph_uint8 graph_node_is_critical(graph_t * g, cmph_uint32 v) /* included -- Fabiano */
+{
+        return (cmph_uint8)GETBIT(g->critical_nodes,v);
+}
+
+void graph_obtain_critical_nodes(graph_t *g) /* included -- Fabiano*/
+{
+        cmph_uint32 i;
+	cmph_uint32 v;
+	cmph_uint8 *deleted = (cmph_uint8 *)malloc((g->nedges*sizeof(cmph_uint8))/8+1);
+	size_t deleted_len = g->nedges/8 + 1;
+	memset(deleted, 0, deleted_len);
+	free(g->critical_nodes);
+	g->critical_nodes = (cmph_uint8 *)malloc((g->nnodes*sizeof(cmph_uint8))/8 + 1);
+	g->ncritical_nodes = 0;
+	memset(g->critical_nodes, 0, (g->nnodes*sizeof(cmph_uint8))/8 + 1);
+	DEBUGP("Looking for the 2-core in graph with %u vertices and %u edges\n", g->nnodes, g->nedges);
+	for (v = 0; v < g->nnodes; ++v)
+	{
+		cyclic_del_edge(g, v, deleted);
+	}
+
+	for (i = 0; i < g->nedges; ++i)
+	{
+		if (!(GETBIT(deleted,i))) 
+		{
+			DEBUGP("Edge %u %u->%u belongs to the 2-core\n", i, g->edges[i], g->edges[i + g->nedges]);
+			if(!(GETBIT(g->critical_nodes,g->edges[i]))) 
+			{
+			  g->ncritical_nodes ++;
+			  SETBIT(g->critical_nodes,g->edges[i]);
+			}
+			if(!(GETBIT(g->critical_nodes,g->edges[i + g->nedges]))) 
+			{
+			  g->ncritical_nodes ++;
+			  SETBIT(g->critical_nodes,g->edges[i + g->nedges]);
+			}
+		}
+	}
+	free(deleted);
+}
+
+cmph_uint8 graph_contains_edge(graph_t *g, cmph_uint32 v1, cmph_uint32 v2) /* included -- Fabiano*/
+{
+	cmph_uint32 e;
+	e = g->first[v1];
+	if(e == EMPTY) return 0;
+	if (check_edge(g, e, v1, v2)) return 1;
+	do
+	{
+		e = g->next[e];
+		if(e == EMPTY) return 0;
+	}
+	while (!check_edge(g, e, v1, v2));
+	return 1;
+}
+
+cmph_uint32 graph_vertex_id(graph_t *g, cmph_uint32 e, cmph_uint32 id) /* included -- Fabiano*/
+{
+  return (g->edges[e + id*g->nedges]);
+}
+
+cmph_uint32 graph_ncritical_nodes(graph_t *g) /* included -- Fabiano*/
+{
+  return g->ncritical_nodes;
+}
+
+graph_iterator_t graph_neighbors_it(graph_t *g, cmph_uint32 v)
+{
+	graph_iterator_t it;
+	it.vertex = v;
+	it.edge = g->first[v];
+	return it;
+}
+cmph_uint32 graph_next_neighbor(graph_t *g, graph_iterator_t* it)
+{
+	cmph_uint32 ret;
+	if(it->edge == EMPTY) return GRAPH_NO_NEIGHBOR; 
+	if (g->edges[it->edge] == it->vertex) ret = g->edges[it->edge + g->nedges];
+	else ret = g->edges[it->edge];
+	it->edge = g->next[it->edge];
+	return ret;
+}
+	
+