I'm trying to create a program that makes a bfs in graphs. I have created the adjacency matrix and the bfs function. The program works if I enter a small input (like 4 nodes), but if I enter bigger inputs I start getting segmentation fault.
Thing is, I don't get it always in the same place. Everytime I run it, it may crash on a different iteration, but certainly in the same loop. Here is my code:(I'm just posting the functions that I think are relevant to the problem, but if you think you need more code, just ask).
void matrixBfs(int n, int matrix[n][n], Node nodeLocker[n], int source)
{
int aux;
Box* head =(Box*) malloc(sizeof(Box*));
if (head == NULL)
{
printf("Memory failure\n");
}
head->next = NULL;
add(head, source);
nodeLocker[source].checked = 1;
while (len(head) > 0)
{
aux = pop(head);
for(int i=0; i<n; i++)
{
if ((matrix[aux][i]) && !(nodeLocker[i].checked))
{
add(head, i);
nodeLocker[i].checked = 1;
}
}
}
head = NULL;
free(head);
}
This is the function that crashes, and by printing I have determined that crashes either on the
while (len(head) > 0)
and the
add(head, i);
statements.
Those functions are:
// Returns the length of the list.
int len(Box* head)
{
int i = 0;
Box* current = head;
for(i; current->next != NULL; i++)
{
current = current-> next;
}
return i;
}
// Adds an element at the end of the list
void add(Box* head, int value)
{
Box* current = head;
while((current->next) != NULL)
{
current = (current->next);
}
Box* auxNode = (Box*) malloc(sizeof(Box*));
if (auxNode == NULL)
{
printf("Memory failure\n");
}
auxNode->id = value;
auxNode->next = NULL;
current->next = auxNode;
}
Again, by printing, I have determined that both of them crash when checking the next node of the linked list. That is, in
for(i; current->next != NULL; i++)
and
while((current->next) != NULL)
I'm sorry for the extension of my question, and would greatly appreciate any help on this matter. So thanks in advance.
EDIT: Here is the entire code in case is needed:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Lists.c"
typedef struct Nodo
{
int id; // Representative value
int checked; // 0 if the node wasn't visited; and 1 if it was.
} Node;
void initializeLocker(int n, Node nodeLocker[n])
{
for (int i=0; i < n; i++)
{
nodeLocker[i].id = i;
nodeLocker[i].checked = 0;
}
}
void matrixBfs(int n, int matrix[n][n], Node nodeLocker[n], int source)
{
int aux;
Box* head =(Box*) malloc(sizeof(Box*));
if (head == NULL)
{
printf("Memory failure\n");
}
head->next = NULL;
add(head, source);
nodeLocker[source].checked = 1;
while (len(head) > 0)
{
aux = pop(head);
for(int i=0; i<n; i++)
{
if ((matrix[aux][i]) && !(nodeLocker[i].checked))
{
add(head, i);
nodeLocker[i].checked = 1;
}
}
}
head = NULL;
free(head);
}
int main()
{
FILE* file = fopen("Input.in","r");
char c[5];
char* pch;
int n;
int num;
int num2;
fgets(c, 5, file);
n = atoi(c); // Number of nodes.
if (n < 0)
{
printf("Must input at least one node");
exit(1);
}
int matrix[n][n];
// Initialization loop
for (int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
matrix[i][j] = 0;
}
}
// Insertion loop.
while(fgets(c, 5, file))
{
pch = strtok(c, " ");
num = atoi(pch) - 1;
pch = strtok(NULL, " ");
num2 = atoi(pch) - 1;
matrix[num][num2] = 1;
matrix[num2][num] = 1;
}
fclose(file); // No further use of the file.
pch = NULL;
free(pch);
Node nodeLocker[n];
initializeLocker(n, nodeLocker);
matrixBfs(n, matrix, nodeLocker, 0);
for (int i=0; i<n; i++)
{
if(nodeLocker[i].checked == 0)
{
printf("The entered graph has at least 1 node aislated. Please enter
a new graph.");
exit(1);
}
}
initializeLocker(n, nodeLocker);
nodeLocker[0].checked = 1;
matrixBfs(n, matrix, nodeLocker, 1);
for (int i=1; i<n; i++)
{
if (nodeLocker[i].checked == 0)
{
printf("%d is a linker agent.\n", 1);
break;
}
}
for (int i=1; i<n; i++)
{
initializeLocker(n, nodeLocker);
nodeLocker[i].checked = 1;
matrixBfs(n, matrix, nodeLocker, 0);
for (int j=0; j<n; j++)
{
if (nodeLocker[j].checked == 0)
{
printf("%d is a linker agent.\n", i+1);
break;
}
}
}
return 0;
}
The "Box" structure is defined in this file:
#include <stdio.h>
#include <stdlib.h>
typedef struct Box
{
int id;
struct Box* next;
} Box;
// Adds an element at the end of the list.
void add(Box* head, int value)
{
Box* current = head;
Box* next = NULL;
if (current != NULL)
{
next = current->next;
}
while(next != NULL)
{
current = next;
next = current->next;
}
Box* auxNode = (Box*) malloc(sizeof(Box*));
if (auxNode == NULL)
{
printf("Memory failure\n");
}
auxNode->id = value;
auxNode->next = NULL;
current->next = auxNode;
}
// Returns the length of the list
int len(Box* head)
{
int i = 0;
Box* current = head;
Box* next = NULL;
if (current != NULL)
{
next = current->next;
}
for(i; next != NULL; i++)
{
current = next;
next = current-> next;
}
return i;
}
// Prints the entire list
void printLine(Box* head)
{
if (head->next == NULL)
{
printf("The list is empty\n");
return;
}
Box* current = head;
current = current->next;
printf("[%d", (current->id) + 1);
while (current->next != NULL)
{
current = current->next;
printf(", %d", (current->id) + 1);
}
printf("]\n");
}
// Deletes and returns the last element of the list
int pop(Box* head)
{
Box* auxNode;
int value;
if (len(head) == 1)
{
auxNode = head->next;
head->next = NULL;
value = auxNode->id;
auxNode = NULL;
free(auxNode);
return value;
}
Box* current = head;
while (current->next->next != NULL)
{
current = current->next;
}
auxNode = current->next;
value = current->next->id;
current->next = NULL;
auxNode = NULL;
free(auxNode);
return value;
}
Finally, the input is entered using the "Input.txt" file. Here, the first line shows the number of nodes of the graph, and the rest shows the connections between them:
9
1 2
1 3
1 5
2 3
2 5
3 5
4 7
5 6
5 7
5 9
6 7
6 9
7 8
7 9
8 9
