Tarjan: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: 'feature' pragmas more up-to-date) |
(Add's my C (c99) implementation of Tarjan's algorithm) |
||
Line 7: | Line 7: | ||
;References: |
;References: |
||
* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]]. |
* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]]. |
||
=={{header|C|C}}== |
|||
<lang 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; |
|||
} |
|||
</lang> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |