Kosaraju's algorithm in C simple implementation

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) {
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);

kosaraju(graph);

return 0;
}

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

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.