Implementation of Dijkstra's Algorithm for Strongly Connected Components.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Copyright 2014 Gagarine Yaikhom (MIT License) | |
* | |
* Implementation of Dijkstra's Algorithm for Strongly Connected Components. | |
*/ | |
#include <stdio.h> | |
#include <stdlib.h> | |
#define MAX_DEGREE 5 | |
#define MAX_NUM_VERTICES 20 | |
#define UNASSIGNED -1 | |
struct vertices_s { | |
int preorder; | |
int scc; | |
int deg; | |
int adj[MAX_DEGREE]; /* < 0 if incoming edge */ | |
} vertices[] = { | |
{-1, -1, 3, {2, -3, 4}}, | |
{-1, -1, 2, {-1, 3}}, | |
{-1, -1, 3, {1, -2, 7}}, | |
{-1, -1, 3, {-1, -5, 6}}, | |
{-1, -1, 2, {4, -7}}, | |
{-1, -1, 3, {-4, 7, -8}}, | |
{-1, -1, 4, {-3, 5, -6, -12}}, | |
{-1, -1, 3, {6, -9, 11}}, | |
{-1, -1, 2, {8, -10}}, | |
{-1, -1, 3, {9, -11, -12}}, | |
{-1, -1, 3, {-8, 10, 12}}, | |
{-1, -1, 3, {7, 10, -11}} | |
}; | |
int num_vertices = sizeof(vertices) / sizeof(vertices[0]); | |
struct stack_s { | |
int top; | |
int items[MAX_NUM_VERTICES]; | |
} s_stack = {-1, {}}, p_stack = {-1, {}}; | |
void stack_push(struct stack_s *stack, 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(struct stack_s *stack) { | |
return stack->top < 0 ? -1 : stack->items[stack->top--]; | |
} | |
int stack_top(struct stack_s *stack) { | |
return stack->top < 0 ? -1 : stack->items[stack->top]; | |
} | |
int preorder = 1; | |
int scc = 1; | |
#define v_preorder(X) vertices[(X)].preorder | |
#define v_deg(X) vertices[(X)].deg | |
#define v_adj(X,Y) vertices[(X)].adj[(Y)] | |
#define v_scc(X) vertices[(X)].scc | |
void dfs(int v) { | |
int i, c, w, scc_found; | |
v_preorder(v) = preorder++; | |
stack_push(&s_stack, v); | |
stack_push(&p_stack, v); | |
for (i = 0, c = v_deg(v); i < c; ++i) { | |
w = v_adj(v, i); | |
if (w > 0) { | |
w = w - 1; /* because vertex index begins at 0 */ | |
if (v_preorder(w) == UNASSIGNED) | |
dfs(w); | |
else if (v_scc(w) == UNASSIGNED) | |
while (v_preorder(stack_top(&p_stack)) > v_preorder(w)) | |
stack_pop(&p_stack); | |
} | |
} | |
if (stack_top(&p_stack) == v) { | |
scc_found = 0; | |
while ((w = stack_pop(&s_stack)) != -1) { | |
if (v_scc(w) == UNASSIGNED) { | |
if (scc_found == 0) { | |
printf("scc %d: ", scc); | |
scc_found = 1; | |
} | |
v_scc(w) = scc; | |
printf("%d ", w + 1); | |
} | |
if (v == w) { | |
if (scc_found) { | |
printf("\n"); | |
++scc; | |
} | |
break; | |
} | |
} | |
stack_pop(&p_stack); | |
} | |
} | |
int main(void) { | |
int i; | |
for (i = 0; i < num_vertices; ++i) { | |
v_scc(i) = UNASSIGNED; | |
v_preorder(i) = UNASSIGNED; | |
} | |
for (i = 0; i < num_vertices; ++i) | |
dfs(i); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment