167 lines
3.5 KiB
C
167 lines
3.5 KiB
C
#include <stddef.h>
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
|
|
#ifndef min
|
|
#define min(x, y) ((x)<(y) ? (x) : (y))
|
|
#endif
|
|
|
|
struct edge {
|
|
void *from;
|
|
void *to;
|
|
};
|
|
|
|
struct components {
|
|
int nnodes;
|
|
void **nodes;
|
|
struct components *next;
|
|
};
|
|
|
|
struct node {
|
|
int index;
|
|
int lowlink;
|
|
bool onStack;
|
|
void *data;
|
|
};
|
|
|
|
struct tjstate {
|
|
int index;
|
|
int sp;
|
|
int nedges;
|
|
struct edge *edges;
|
|
struct node **stack;
|
|
struct components *head;
|
|
struct components *tail;
|
|
};
|
|
|
|
static int nodecmp(const void *l, const void *r)
|
|
{
|
|
return (ptrdiff_t)l -(ptrdiff_t)((struct node *)r)->data;
|
|
}
|
|
|
|
static int strongconnect(struct node *v, struct tjstate *tj)
|
|
{
|
|
struct node *w;
|
|
|
|
/* Set the depth index for v to the smallest unused index */
|
|
v->index = tj->index;
|
|
v->lowlink = tj->index;
|
|
tj->index++;
|
|
tj->stack[tj->sp] = v;
|
|
tj->sp++;
|
|
v->onStack = true;
|
|
|
|
for (int i = 0; i<tj->nedges; i++) {
|
|
/* Only consider nodes reachable from v */
|
|
if (tj->edges[i].from != v) {
|
|
continue;
|
|
}
|
|
w = tj->edges[i].to;
|
|
/* Successor w has not yet been visited; recurse on it */
|
|
if (w->index == -1) {
|
|
int r = strongconnect(w, tj);
|
|
if (r != 0)
|
|
return r;
|
|
v->lowlink = min(v->lowlink, w->lowlink);
|
|
/* Successor w is in stack S and hence in the current SCC */
|
|
} else if (w->onStack) {
|
|
v->lowlink = min(v->lowlink, w->index);
|
|
}
|
|
}
|
|
|
|
/* If v is a root node, pop the stack and generate an SCC */
|
|
if (v->lowlink == v->index) {
|
|
struct components *ng = malloc(sizeof(struct components));
|
|
if (ng == NULL) {
|
|
return 2;
|
|
}
|
|
if (tj->tail == NULL) {
|
|
tj->head = ng;
|
|
} else {
|
|
tj->tail->next = ng;
|
|
}
|
|
tj->tail = ng;
|
|
ng->next = NULL;
|
|
ng->nnodes = 0;
|
|
do {
|
|
tj->sp--;
|
|
w = tj->stack[tj->sp];
|
|
w->onStack = false;
|
|
ng->nnodes++;
|
|
} while (w != v);
|
|
ng->nodes = malloc(ng->nnodes*sizeof(void *));
|
|
if (ng == NULL) {
|
|
return 2;
|
|
}
|
|
for (int i = 0; i<ng->nnodes; i++) {
|
|
ng->nodes[i] = tj->stack[tj->sp+i]->data;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
static int ptrcmp(const void *l, const void *r)
|
|
{
|
|
return (ptrdiff_t)((struct node *)l)->data
|
|
- (ptrdiff_t)((struct node *)r)->data;
|
|
}
|
|
|
|
/**
|
|
* 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 and sets the error to:
|
|
* 1 if there was a malformed edge
|
|
* 2 if malloc failed
|
|
*
|
|
* @param number of nodes
|
|
* @param data of the nodes (assumed to be unique)
|
|
* @param number of edges
|
|
* @param data of edges
|
|
* @param pointer to error code
|
|
*/
|
|
struct components *tarjans(
|
|
int nnodes, void *nodedata[],
|
|
int nedges, struct edge *edgedata[],
|
|
int *error)
|
|
{
|
|
struct node nodes[nnodes];
|
|
struct edge edges[nedges];
|
|
struct node *stack[nnodes];
|
|
struct node *from, *to;
|
|
struct tjstate tj = {0, 0, nedges, edges, stack, NULL, .tail=NULL};
|
|
|
|
// Populate the nodes
|
|
for (int i = 0; i<nnodes; i++) {
|
|
nodes[i] = (struct node){-1, -1, false, nodedata[i]};
|
|
}
|
|
qsort(nodes, nnodes, sizeof(struct node), ptrcmp);
|
|
|
|
// Populate the edges
|
|
for (int i = 0; i<nedges; i++) {
|
|
from = bsearch(edgedata[i]->from, nodes, nnodes,
|
|
sizeof(struct node), nodecmp);
|
|
if (from == NULL) {
|
|
*error = 1;
|
|
return NULL;
|
|
}
|
|
to = bsearch(edgedata[i]->to, nodes, nnodes,
|
|
sizeof(struct node), nodecmp);
|
|
if (to == NULL) {
|
|
*error = 1;
|
|
return NULL;
|
|
}
|
|
edges[i] = (struct edge){.from=from, .to=to};
|
|
}
|
|
|
|
//Tarjan's
|
|
for (int i = 0; i < nnodes; i++) {
|
|
if (nodes[i].index == -1) {
|
|
*error = strongconnect(&nodes[i], &tj);
|
|
if (*error != 0)
|
|
return NULL;
|
|
}
|
|
}
|
|
return tj.head;
|
|
}
|