Kosaraju's algorithm in C simple implementation

Question

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

• greybeard: Does your current structure support vertices with more than one outgoing edge/graph_add_edge(graph, 2, 3);? Doesn't it need to?

Answer 1

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.