#include #include // #define NDEBUG #include "graph.h" #include "c.h" struct graph_node { BitSet parents; BitSet children; void* data; }; typedef struct graph_node* GraphNode; struct edge { int from; int to; }; typedef struct edge* Edge; struct graph { GraphNode* nodes; int capacity; int size; int set_size; ArrayList edges; int closed; }; int graph_size(Graph graph) { assert(graph->closed); return graph->size; } BitSet graph_newNodeSet(Graph graph, int arena) { assert(graph->closed); return set_new(graph->set_size); } BitSet graph_children(Graph graph, int parent) { assert(graph->closed); assert(graph->size > parent); assert(parent >= 0); assert(graph->nodes[parent]); assert(graph->nodes[parent]->children); return graph->nodes[parent]->children; } BitSet graph_parents(Graph graph, int child) { assert(graph->closed); assert(graph->size > child); assert(child >= 0); assert(graph->nodes[child]); assert(graph->nodes[child]->parents); return graph->nodes[child]->parents; } void integrity(Graph graph) { int i, j; assert(graph->closed); for(i = 0; i < graph->size; i++) { assert(graph->nodes[i]); } for(i = 0; i < graph->size; i++) { for (j = 0; j < graph->size; j++) { int p, c; c = set_contains(graph->nodes[i]->children, j) ? 1 : 0; p = set_contains(graph->nodes[j]->parents, i) ? 1 : 0; if (p ^ c) { fprintf(stderr, "Integrity failed:\nNode %d child %d is %s\n", i, j, c ? "true" : "false"); fprintf(stderr, "Node %d parent %d is %s\n", j, i, p ? "true" : "false"); assert(0); } } } } static GraphNode createNode(void* data) { GraphNode node = allocate(sizeof(struct graph_node), FUNC); node->parents = NULL; node->children = NULL; node->data = data; return node; } static void growCapacity(Graph graph) { int i; int newCapacity = graph->capacity * 2; GraphNode* newNodes = allocate(sizeof(GraphNode) * newCapacity, FUNC); write_log("Grow capacity to %d\n", newCapacity); for (i = 0; i < graph->size; i++) { newNodes[i] = graph->nodes[i]; } graph->nodes = newNodes; graph->capacity = newCapacity; } int graph_addNode(Graph graph, void* data) { int id = graph->size; GraphNode node = createNode(data); assert(data); assert(!graph->closed); if (graph->size == graph->capacity) { growCapacity(graph); } graph->nodes[id] = node; graph->size++; return id; } void graph_addEdge(Graph graph, int from, int to) { Edge edge = allocate(sizeof(struct edge), FUNC); assert(!graph->closed); assert(graph->size > from); assert(graph->size > to); assert(from >= 0); assert(to >= 0); LOG(("Adding edge %d to %d\n", from, to)); edge->from = from; edge->to = to; list_add(graph->edges, edge); } Graph graph_new() { Graph graph = allocate(sizeof(struct graph), FUNC); graph->size = 0; graph->capacity = 8; graph->nodes = allocate(sizeof(GraphNode) * 8, FUNC); graph->edges = list_new(16); graph->closed = 0; return graph; } static void moveNode(Graph graph, int from, int to) { int i; for(i = 0; i < graph->size; i++) { if (i != to) { GraphNode node = graph->nodes[i]; set_moveBit(node->children, to, from); set_moveBit(node->parents, to, from); } } graph->nodes[to] = graph->nodes[from]; } static void removeDeadNodes(Graph graph) { int i; for(i = 1; i < graph->size; i++) { // Check for isolated nodes. if (set_empty(graph_children(graph, i)) && set_empty(graph_parents(graph, i))) { moveNode(graph, graph->size - 1, i); graph->nodes[graph->size - 1] = NULL; graph->size--; } } } static void mergePair(Graph graph, int parent, int child, void* (* merge)(void* node1, void* node2)) { int i; LOG(("Merging nodes %d %d\n", parent, child)); graph->nodes[parent]->children = graph->nodes[child]->children; graph->nodes[parent]->data = merge(graph->nodes[parent]->data, graph->nodes[child]->data); for(i = 0; i < graph->size; i++) { set_moveBit(graph->nodes[i]->parents, parent, child); } if (child != graph->size - 1) { moveNode(graph, graph->size - 1, child); } graph->nodes[graph->size - 1] = NULL; graph->size--; } static void mergeNodes(Graph graph, void* (* merge)(void* node1, void* node2)) { int merged, i; LOG(("Looking for nodes to merge...\n")); do { merged = 0; for (i = 0; i < graph->size; i++) { assert(graph->nodes[i]); if (set_size(graph->nodes[i]->children) == 1) { int child = FIRST_IN(graph->nodes[i]->children); if (set_size(graph->nodes[child]->parents) == 1) { int parent = FIRST_IN(graph->nodes[child]->parents); mergePair(graph, parent, child, merge); merged = 1; } } } } while (merged); } void graph_close(Graph graph, void* (* merge)(void* node1, void* node2)) { int i, size; graph->set_size = graph->size; for (i = 0; i < graph->size; i++) { graph->nodes[i]->parents = set_new(graph->set_size); graph->nodes[i]->children = set_new(graph->set_size); } for(i = 0, size = list_size(graph->edges); i < size; i++) { Edge edge = (Edge)list_get(graph->edges, i); int to, from; from = edge->from; to = edge->to; set_add(graph->nodes[to]->parents, from); set_add(graph->nodes[from]->children, to); } if (merge != NULL) mergeNodes(graph, merge); graph->closed = 1; removeDeadNodes(graph); integrity(graph); } void* graph_node(Graph graph, int index) { return graph->nodes[index]->data; }