问Kosaraju算法在C简单实现中的应用

EN

/**
 * Kosaraju's algorithm implementation which is a linear time algorithm
 * to find the strongly connected components of a directed graph.
 * https://en.wikipedia.org/wiki/kosaraju's_algorithm
 */

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct vertex {
    int value;
    struct vertex* next;
};

typedef struct vertex Vertex;

typedef struct graph {
    int num_vertices;
    Vertex** neighbors;
};

typedef struct graph Graph;

struct stack {
    int value;
    struct stack* next;
};

typedef struct stack Stack;

/**
 * @brief Create stack using endogenous linked list
 * @param stack pointer to a stack pointer
 */
static void stack_create(Stack** stack) {
    *stack = NULL;
}

/**
 * @brief Push method of stack
 * @param stack pointer to a stack pointer
 * @param value value to push to stack
 */
static void stack_push(Stack** stack, int value) {
    Stack* item = malloc(sizeof(Stack));
    item->value = value;
    item->next = *stack;
    *stack = item;
}

/**
 * @brief Pop method of stack
 * @param stack pointer to a stack pointer
 * @param value that has just been popped from the stack
 * @return boolean indicating whether popping from the stack was successful or
 * not
 */
static bool stack_pop(Stack** stack, int* v) {
    Stack* old = *stack;
    if (!old)
        return false;

    *v = old->value;
    *stack = old->next;
    free(old);
    return true;
}

/**
 * @brief Destroy method of stack
 * @param stack pointer to a stack pointer
 */
static void stack_destroy(Stack** stack) {
    int temp;
    while (stack_pop(stack, &temp))
        ;
}

/**
 * @brief Checks whether stack is empty or not
 * @param stack pointer to a stack pointer
 * @return boolean indicating whether stack is empty or not
 */
static bool stack_is_empty(Stack** stack) {
    return *stack == NULL;
}

/**
 * @brief Create graph given number of vertices implemented using adjacency
 * @return pointer to allocated graph
 */
static Graph* graph_create(int num_vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->num_vertices = num_vertices;
    size_t vertices_size = num_vertices * sizeof(Vertex*);
    graph->neighbors = (Vertex**)malloc(vertices_size);
    memset(graph->neighbors, NULL, vertices_size);
    return graph;
}

/**
 * @brief Add edge method of graph
 * @param graph pointer to graph
 * @param source index of source
 * @param sink index of sink
 */
static void graph_add_edge(Graph* graph, int source, int sink) {
    Vertex* item = (Vertex*)malloc(sizeof(Vertex));
    item->value = sink;
    item->next = graph->neighbors[source];
    graph->neighbors[source] = item;
}

/**
 * @brief Deallocate graph vertex
 * @param vertex vertex linked list node
 */
static void graph_destroy_vertex(Vertex* vertex) {
    if (vertex == NULL)
        return;

    if (vertex->next != NULL)
        graph_destroy_vertex(vertex->next);

    free(vertex);
}

/**
 * @brief Deallocate graph
 * @param graph pointer to graph
 */
static void graph_destroy(Graph* graph) {
    int i;
    for (i = 0; i < graph->num_vertices; i++) {
        graph_destroy_vertex(graph->neighbors[i]);
    }

    free(graph);
}

/**
 * @brief DFS traversal of graph
 * @param graph pointer to graph
 * @param stack pointer to stack
 * @param visited visited boolean array
 * @param v vertex
 */
static void dfs(Graph* graph, Stack** stack, bool* visited, int v) {
    visited[v] = true;
    Vertex* neighbors = graph->neighbors[v];
    while (neighbors != NULL) {
        if (!visited[neighbors->value]) {
            dfs(graph, stack, visited, neighbors->value);
        }
        neighbors = neighbors->next;
    }
    stack_push(stack, v);
}

/**
 * @brief Builds reverse of graph
 * @param graph pointer to graph
 * @return reversed graph
 */
static Graph* reverse(Graph* graph) {
    Graph* reversed_graph = graph_create(graph->num_vertices);

    int i;
    Vertex* neighbors;
    for (i = 0; i < graph->num_vertices; i++) {
        neighbors = graph->neighbors[i];
        while (neighbors != NULL) {
            graph_add_edge(reversed_graph, neighbors->value, i);
            neighbors = neighbors->next;
        }
    }
    return reversed_graph;
}

/**
 * @brief Use dfs to list a set of vertices dfs_and_print from a vertex v in
 * reversed grap
 * @param graph pointer to graph
 * @param visited boolean array indicating whether index has been visited or not
 * @param deleted boolean array indicating whether index has been popped or not
 * @param v vertex
 */
void dfs_and_print(Graph* graph, bool* visited, bool* deleted, int v) {
    printf("%d,", v);
    visited[v] = true;
    deleted[v] = true;
    Vertex* arcs = graph->neighbors[v];  // the adjacent list of vertex v
    while (arcs != NULL) {
        int u = arcs->value;
        if (!visited[u] && !deleted[u]) {
            dfs_and_print(graph, visited, deleted, u);
        }
        arcs = arcs->next;
    }
}

/**
 * @brief Collect SCC from the graph
 * @param graph pointer to graph
 * @param stack pointer to a stack pointer
 * @param visited boolean array indicating whether index has been visited or not
 */
void collect_scc(Graph* graph, Stack** stack, bool* visited) {
    bool* deleted = (bool*)alloca(graph->num_vertices * sizeof(bool));
    memset(deleted, false, graph->num_vertices * sizeof(bool));
    int c = 1;
    while (!stack_is_empty(stack)) {
        int v;
        bool any = stack_pop(stack, &v);
        if (any && !deleted[v]) {
            memset(visited, false,
                   graph->num_vertices *
                   sizeof(bool));  // mark all vertices of reverse as not visited
            printf("Strongly Connected Component #%d: ", c);
            dfs_and_print(graph, visited, deleted, v);
            printf("\n");
            c++;
        }
    }
}

/**
 * @brief Kosaraju logic
 * @param graph pointer to graph
 */
static void kosaraju(Graph* graph) {
    Stack* stack;
    stack_create(&stack);

    size_t visited_size = graph->num_vertices * sizeof(bool);
    bool* visited = (bool*)alloca(visited_size);
    memset(visited, false, visited_size);
    int i = 0;
    for (i = 0; i < graph->num_vertices; i++) {
        if (!visited[i]) {
            dfs(graph, &stack, visited, i);
        }
    }

    Graph* reversed_graph = reverse(graph);
    collect_scc(reversed_graph, &stack, visited);

    graph_destroy(graph);
    graph_destroy(reversed_graph);
    stack_destroy(&stack);
}

int main() {
    Graph* graph = graph_create(10);
    graph_add_edge(graph, 1, 2);
    graph_add_edge(graph, 2, 1);

    graph_add_edge(graph, 3, 4);
    graph_add_edge(graph, 4, 5);
    graph_add_edge(graph, 5, 6);
    graph_add_edge(graph, 6, 7);
    graph_add_edge(graph, 7, 3);

    kosaraju(graph);

    return 0;
}