3
\$\begingroup\$

I am wondering can I please get some feedback for my simple implementation of the Kosaraju algorithm. More specifically how I de-allocate the things I allocated using malloc and method names.

/**
 * 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;
}
\$\endgroup\$
1
  • \$\begingroup\$ Does your current structure support vertices with more than one outgoing edge/graph_add_edge(graph, 2, 3);? Doesn't it need to? \$\endgroup\$
    – greybeard
    May 24 at 8:13

1 Answer 1

3
\$\begingroup\$

Allocate by referenced type

Consider reviewing below code. Is the type right? To be certain, one needs to search elsewhere (~ 70 lines earlier) to see Vertex* is OK.

size_t vertices_size = num_vertices * sizeof(Vertex*);
graph->neighbors = (Vertex**)malloc(vertices_size);

Now try type-less code. This is correct without that search. It is easier to code right, review and maintain.

size_t vertices_size = num_vertices * sizeof graph->neighbors[0];
graph->neighbors = malloc(vertices_size);

Code assumes *alloc() never fails

malloc() and friends may fail. Robust code checks for a NULL return.

num_vertices <= 0

Code fails without detection when num_vertices <= 0. Consider size_t num_vertices or detect and handle out-of-range inputs.

memset() is for bytes

Strictly NULL does not have to be 0 and below then only uses the LSByte for each byte of the pointers. Instead uses a loop and iterate over each pointer or research calloc() to zero fill an allocation.

memset(graph->neighbors, NULL, vertices_size);  // Iffy code.

memset(graph->neighbors, 0, vertices_size);  // better

memset(deleted, false, graph->num_vertices * sizeof(bool)); is also conceptually amiss. Although false is 0 - so we are functionally OK here, bool may be more than 1 byte.

static

I'd rather see the graph functions in a separate *.h, *.c files and then use static for the functions that need it.

Formatting

Rather than manually formatting, consider using an auto-formatter. It is more productive.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.