Kosaraju: Difference between revisions

=={{header|C}}==

<lang c>#include <stdio.h>

#include <stdlib.h>

struct stack {

int state;

void *current;

struct stack *next;

};

struct graph {

int value;

int state;

struct stack *incoming;

struct stack *outgoing;

};

void create(struct stack **stack)

{

*stack = NULL;

}

void push(int state, void *value, struct stack **stack)

{

struct stack *new = malloc(sizeof (struct stack));

new->state = state;

new->current = value;

new->next = *stack;

*stack = new;

}

int pop(int *state, void **value, struct stack **stack)

{

struct stack *old = *stack;

if (!old) return 0;

if (state) *state = old->state;

if (value) *value = old->current;

*stack = old->next;

free(old);

return 1;

}

void destroy(struct stack **stack)

{

while (pop(NULL, NULL, stack));

}

void connect(struct graph *source, struct graph *target)

{

push(0, target, &source->outgoing);

push(0, source, &target->incoming);

}

void path(int count, int *offsets, struct graph *nodes)

{

while (count--)

connect(&nodes[offsets[count]], &nodes[offsets[count + 1]]);

}

void visit(struct graph *graph, struct stack **visited)

{

int state;

void *current;

struct stack *schedule;

struct stack *neighbors;

struct stack dummy = { 0, graph, NULL };

create(&schedule);

push(0, &dummy, &schedule);

while (pop(&state, &current, &schedule))

if (!state && current) {

neighbors = current;

graph = neighbors->current;

push(0, neighbors->next, &schedule);

if (!graph->state) {

graph->state = 1;

push(1, graph, &schedule);

push(0, graph->outgoing, &schedule);

}

}

else if (state)

push(0, current, visited);

}

void assign(struct graph *graph, struct stack **assigned)

{

struct stack *schedule;

struct stack *neighbors;

struct stack dummy = { 0, graph, NULL };

create(&schedule);

push(0, &dummy, &schedule);

while (pop(NULL, &neighbors, &schedule))

if (neighbors) {

graph = neighbors->current;

push(0, neighbors->next, &schedule);

if (graph->state) {

graph->state = 0;

push(0, graph->incoming, &schedule);

push(0, graph, assigned);

}

}

}

void kosaraju(struct graph *graph, struct stack **components)

{

struct stack *visited;

struct stack *assigned;

create(&visited);

visit(graph, &visited);

while (pop(NULL, &graph, &visited)) {

create(&assigned);

assign(graph, &assigned);

if (assigned)

push(0, assigned, components);

}

}

int main()

{

struct graph nodes[16];

struct graph *graph;

struct stack *component;

struct stack *components;

int lengths[7] = { 8, 6, 1, 6, 4, 1, 1 };

int offsets[7][9] = {

{ 0, 1, 2, 0, 3, 4, 0, 5, 7 },

{ 0, 9, 10, 11, 12, 9, 11 },

{ 1, 12 },

{ 3, 5, 6, 7, 8, 6, 15 },

{ 5, 13, 14, 13, 15 },

{ 8, 15 },

{ 10, 13 }

};

for (int i = 0; i < 16; i++) {

nodes[i].value = i;

nodes[i].state = 0;

create(&nodes[i].incoming);

create(&nodes[i].outgoing);

}

for (int i = 0; i < 7; i++)

path(lengths[i], offsets[i], nodes);

create(&components);

kosaraju(&nodes[0], &components);

while (pop(NULL, &component, &components)) {

while (pop(NULL, &graph, &component))

printf("%d ", graph->value);

printf("\n");

}

for (int i = 0; i < 16; i++) {

destroy(&nodes[i].incoming);

destroy(&nodes[i].outgoing);

}

}>/lang>

{{out}}

<pre>15

14 13

10 11 12 9

7 8 6

5

3 4 1 2 0

</pre>