Skip to content

Instantly share code, notes, and snippets.

@gyaikhom
Last active May 20, 2017 00:36
Show Gist options
  • Save gyaikhom/d71205bae062a8dd81de to your computer and use it in GitHub Desktop.
Save gyaikhom/d71205bae062a8dd81de to your computer and use it in GitHub Desktop.
Implementation of Kosaraju's Algorithm for Strongly Connected Components.
/**
* Copyright 2014 Gagarine Yaikhom (MIT License)
*
* Implementation of Kosaraju's Algorithm for Strongly Connected Components.
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_DEGREE 5
#define MAX_NUM_VERTICES 20
struct vertices_s {
int visited;
int deg;
int adj[MAX_DEGREE]; /* < 0 if incoming edge */
} vertices[] = {
{0, 3, {2, -3, 4}},
{0, 2, {-1, 3}},
{0, 3, {1, -2, 7}},
{0, 3, {-1, -5, 6}},
{0, 2, {4, -7}},
{0, 3, {-4, 7, -8}},
{0, 4, {-3, 5, -6, -12}},
{0, 3, {6, -9, 11}},
{0, 2, {8, -10}},
{0, 3, {9, -11, -12}},
{0, 3, {-8, 10, 12}},
{0, 3, {7, 10, -11}}
};
int num_vertices = sizeof(vertices) / sizeof(vertices[0]);
struct stack_s {
int top;
int items[MAX_NUM_VERTICES];
} stack = {-1, {}};
void stack_push(int v) {
stack.top++;
if (stack.top < MAX_NUM_VERTICES)
stack.items[stack.top] = v;
else {
printf("Stack is full!\n");
exit(1);
}
}
int stack_pop() {
return stack.top < 0 ? -1 : stack.items[stack.top--];
}
void dfs(int v, int transpose) {
int i, c, n;
vertices[v].visited = 1;
for (i = 0, c = vertices[v].deg; i < c; ++i) {
n = vertices[v].adj[i] * transpose;
if (n > 0)
/* n - 1 because vertex indexing begins at 0 */
if (!vertices[n - 1].visited)
dfs(n - 1, transpose);
}
if (transpose < 0)
stack_push(v);
else
printf("%d ", v + 1);
}
void reset_visited() {
int i;
for (i = 0; i < num_vertices; ++i)
vertices[i].visited = 0;
}
void order_pass() {
int i;
for (i = 0; i < num_vertices; ++i)
if (!vertices[i].visited)
dfs(i, -1);
}
void scc_pass() {
int i = 0, v;
while((v = stack_pop()) != -1) {
if (!vertices[v].visited) {
printf("scc %d: ", ++i);
dfs(v, 1);
printf("\n");
}
}
}
int main(void) {
order_pass();
reset_visited();
scc_pass();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment