Adjacency list from scratch

Question

Here is my code for implementing an adjacency list from scratch. I would like to get feedback from the experts for optimization.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 /*a single node of an adjacency list*/
typedef struct adjList{
 int dest;
 struct adjList *next;
} adjList;
/*Image of a graph...*/
typedef struct Image{
 int source;
 adjList *head;
} Image;
void initialize_graph(Image *graph, int vertices);
void print_graph(Image graph[], int vertices);
void add_adj_node(Image *graph, int source, int destiny, bool directed);
void free_graph(Image graph[], int vertices);
int main() {
 int vertices;
 scanf("%d", &vertices);
 Image graph[vertices];
 printf("size of graph: %d bytes\n", sizeof graph);
 initialize_graph(graph, vertices);
 printf("initialized image of graph\n");
 print_graph(graph, vertices);
 printf(" \n");
 //is the graph directed ? ans: false
 add_adj_node(graph, 1, 7, false);
 add_adj_node(graph, 1, 3, false);
 add_adj_node(graph, 4, 6, false);
 add_adj_node(graph, 4, 1, false);
 add_adj_node(graph, 5, 2, false);
 add_adj_node(graph, 1, 5, false);
 add_adj_node(graph, 1, 2, false);
 print_graph(graph, vertices);
 free_graph(graph, vertices);
 /*if this print produces segmentation fault then the memory is fully freed*/
 printf("graph[1].head->dest%d\n", graph[1].head->dest);
 return 0;
}
void initialize_graph(Image graph[], int vertices) {
 for(int i = 1; i<= vertices; i++){
 graph[i].source = i;
 graph[i].head = NULL;
 }
 return;
}
void add_adj_node(Image *graph, int src, int dest, bool directed){
 adjList *cache = malloc(sizeof(adjList));
 /*create a single node*/
 cache->dest = dest;
 cache->next = NULL;
 if(graph[src].head == NULL){
 graph[src].head = cache;
 }
 else{
 /*put the head address on the crawler*/
 adjList *crawler = graph[src].head;
 while( crawler->next != NULL){
 crawler = crawler->next;
 }
 /*update head value and address. head will point to new adj node
 this will also link src -> dest*/
 crawler->next = cache;
 }
 if (directed == false) {
 directed = true; 
 /*notice we've changed the sequence. dest and src*/
 add_adj_node( graph, dest, src, directed);
 }
 return;
}
void print_graph(Image *graph, int vertices){
 for(int i = 1; i<= vertices; i++){
 adjList *crawl = graph[i].head;
 printf("node: %d ", graph[i].source);
 while(crawl){
 printf("%d ", crawl->dest);
 crawl = crawl->next;
 }
 printf("\n");
 }
 return;
}
/*just a reverse version of crawling a graph*/
void free_graph(Image *graph, int vertices){
 for(int i = 1; i<= vertices; i++){
 adjList *cache;
 printf("releasing elements of node: %d ", graph[i].source);
 while(graph[i].head){
 /*put the next adjacency node in the cache*/
 cache = graph[i].head->next;
 /*free the present adjacencey node*/
 free(graph[i].head);
 graph[i].head = cache;
 }
 printf("\n");
 }
 return;
}

Answer 1

• Out-of-bounds access: an array

  Image graph[vertices];
  

  has vertices entries, starting with index 0, with the largest valid index being vertices - 1. The loop

  for(int i = 1; i<= vertices; i++)
  

  touches graph[vertices], which is illegal. A correct (and idiamatic) loop is

  for(int i = 0; i < vertices; i++)
  

• Testing for memory correctly released via inducing a segfault is, to put it mildly, unconventional. You are not even guaranteed to get one.

• Crawling the list is a waste of time. It is much simpler to prepend the newly created node at the head of the list:

  void add_adj_node(Image *graph, int src, int dest, bool directed)
  {
   adjList * node = create_node(dest);
   node->next = graph[src].head;
   graph[src]head = node;
  }
  

• Recursive invocation of add_adj_node is confusing. I recommend to have a helper function do_add_adj_node and invoke it like this:

  void add_adj_node(Image *graph, int src, int dest) {
   do_add_adj_node(graph, src, dst);
   do_add_adj_node(graph, dst, src);
  }
  

• ph03n1x: So, how can I confirm that the memory is cleared perfectly ?
• vnp: @ph03n1x Nothing you can do from inside the program, at least portably. Use external tools like valgrind.
• ph03n1x: Hmm heard about the tool. I'll try it

Answer 2

There are so many blank lines, look at how you have to scroll so much in order to read the code!

It is fine to have the occasional blank line in order to separate groups of statements within a function, or to separate functions by one or two blank lines. But gaps of more than two lines are just unnecessary in my opinion.

Here is how I would render the code. I've changed nothing except deleting 46 blank lines, which were about a quarter of all the original lines!

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 /*a single node of an adjacency list*/
typedef struct adjList{
 int dest;
 struct adjList *next;
} adjList;
/*Image of a graph...*/
typedef struct Image{
 int source;
 adjList *head;
} Image;
void initialize_graph(Image *graph, int vertices);
void print_graph(Image graph[], int vertices);
void add_adj_node(Image *graph, int source, int destiny, bool directed);
void free_graph(Image graph[], int vertices);
int main() {
 int vertices;
 scanf("%d", &vertices);
 Image graph[vertices];
 printf("size of graph: %d bytes\n", sizeof graph);
 initialize_graph(graph, vertices);
 printf("initialized image of graph\n");
 print_graph(graph, vertices);
 printf(" \n");
 //is the graph directed ? ans: false
 add_adj_node(graph, 1, 7, false);
 add_adj_node(graph, 1, 3, false);
 add_adj_node(graph, 4, 6, false);
 add_adj_node(graph, 4, 1, false);
 add_adj_node(graph, 5, 2, false);
 add_adj_node(graph, 1, 5, false);
 add_adj_node(graph, 1, 2, false);
 print_graph(graph, vertices);
 free_graph(graph, vertices);
 /*if this print produces segmentation fault then the memory is fully freed*/
 printf("graph[1].head->dest%d\n", graph[1].head->dest);
 return 0;
}
void initialize_graph(Image graph[], int vertices) {
 for(int i = 1; i<= vertices; i++){
 graph[i].source = i;
 graph[i].head = NULL;
 }
 return;
}
void add_adj_node(Image *graph, int src, int dest, bool directed){
 adjList *cache = malloc(sizeof(adjList));
 /*create a single node*/
 cache->dest = dest;
 cache->next = NULL;
 if(graph[src].head == NULL){
 graph[src].head = cache;
 }
 else{
 /*put the head address on the crawler*/
 adjList *crawler = graph[src].head;
 while( crawler->next != NULL){
 crawler = crawler->next;
 }
 /*update head value and address. head will point to new adj node
 this will also link src -> dest*/
 crawler->next = cache;
 }
 if (directed == false) {
 directed = true; 
 /*notice we've changed the sequence. dest and src*/
 add_adj_node( graph, dest, src, directed);
 }
 return;
}
void print_graph(Image *graph, int vertices){
 for(int i = 1; i<= vertices; i++){
 adjList *crawl = graph[i].head;
 printf("node: %d ", graph[i].source);
 while(crawl){
 printf("%d ", crawl->dest);
 crawl = crawl->next;
 }
 printf("\n");
 }
 return;
}
/*just a reverse version of crawling a graph*/
void free_graph(Image *graph, int vertices){
 for(int i = 1; i<= vertices; i++){
 adjList *cache;
 printf("releasing elements of node: %d ", graph[i].source);
 while(graph[i].head){
 /*put the next adjacency node in the cache*/
 cache = graph[i].head->next;
 /*free the present adjacencey node*/
 free(graph[i].head);
 graph[i].head = cache;
 }
 printf("\n");
 }
 return;
}