Implementation of Dijkstra's Algorithm for Strongly Connected Components.

dijkstra_scc.c

/**
 * 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;
}

scc.png