I am having trouble figuring out how to do this correctly. I have a linked list of nodes then those nodes have pointers put into an array contained in that node. These nodes make up a sort of one-way graph between the nodes. I must then traverse the nodes randomly until the node "Home" is reached.
The main issue I'm having is assigning the graph nodes into the list nodes. I want the function to take in the head of the list, the names of the nodes and the weight (cost to travel between nodes). I'm not sure how to do this correctly and I don't know what I did but I think there's an infinite loop somehow. Any help is greatly appreciated.
The input file is structured as such:
Applebees
GroundRound
BlueMoose
DrunkenNoodle
Home
STOP
Applebees BlueMoose 10
Applebees DrunkenNoodle 13
GroundRound Applebees 2
GroundRound DrunkenNoodle 7
GroundRound Home 52
STOP STOP 0
GroundRound
Ignore the print statements in graphInsert() those are me trying to debug the loops.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
struct graphNode {
char name[100]; // Establishment name
int arcCnt; // Number of outgoing arc from this node
int weights[10]; // Weights of each outgoing arc from this node
struct graphNode* arcs[10]; // Holds other graph nodes that are connected to this node (this node is source)
};
struct listNode {
char name[100]; // Establishment name
struct listNode* next;
struct graphNode* graph; // Pointer into graph
};
void listInsert(struct listNode **head, char name[100]) {
// setup new nodes
struct graphNode* newGraph = (struct graphNode*)malloc(sizeof(struct graphNode));
for (int i = 0; i < 100; i++) {
newGraph->name[i] = name[i];
}
for (int i = 0; i < 10; i++) {
newGraph->arcs[i] = NULL;
}
newGraph->arcCnt = 0;
struct listNode* newNode = (struct listNode*)malloc(sizeof(struct listNode));
for (int i = 0; i < 100; i++) {
newNode->name[i] = name[i];
}
newNode->next = NULL;
newNode->graph = newGraph;
// check if head is NULL
if (*head == NULL) {
*head = newNode;
return;
}
// if the list is populated then add the node to the end
struct listNode* current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
void graphInsert(struct listNode** head, char src[100], char dst[100], int weight) {
struct listNode* srcNode = *head;
printf("CALL:");
while (srcNode->next != NULL) { // loop through list to find src
printf("%s %s", srcNode->name, src);
if (strcmp(srcNode->name, src) == 0) { // when it finds the name, find the dst update the graph node data
printf("FOUND");
struct listNode* dstNode = *head;
while (dstNode->next != NULL) { // this loop is to find the pointer to the dst node
printf(" %s %s", dstNode->name, dst);
if (strcmp(dstNode->name, src) == 0) { // when it finds name finally update all the info
printf("FOUND");
// assign the new arc to the right spot based on arcCnt (how many arcs there are), then return to exit the loops
srcNode->graph->arcs[srcNode->graph->arcCnt] = dstNode->graph;
srcNode->graph->weights[srcNode->graph->arcCnt] = weight;
srcNode->graph->arcCnt++;
return;
}
dstNode = dstNode->next;
}
}
srcNode = srcNode->next;
}
}
int main(){
srand(2021);
// setup variables
struct listNode* head = NULL;
struct graphNode* sourceNode = NULL;
FILE* data = fopen("./hw10.data", "r");
int i = 0;
int section = 1; // flag to read the file correctly
// this loop reads the file
while (1) {
char name[100];
char name2[100];
int weight = 0;
if (section == 1) { // reads the first section
fscanf(data, "%100s", name);
if (strcmp(name, "STOP") == 0) { // if end of section then increment section counter
section++;
} else { // if its not the end of the section then add the name to the linked list
listInsert(&head, name);
}
} else if (section == 2) { // reads the first section and builds the graph
fscanf(data, "%100s %100s %d", name, name2, &weight);
if (strcmp(name, "STOP") == 0) { // if end of section then increment section counter
section++;
} else {
//graphInsert(&head, name, name2, weight);
}
} else if (section == 3) { // this section only reads one line and gets the
char tmp[100];
fscanf(data, "%100s", tmp);
struct listNode* current = head;
while (current->next != NULL) { // loop through to find the right node for the name
if (strcmp(current->name, tmp) == 0) { // if names are equal update the node
sourceNode = current->graph;
break;
}
current = current->next;
}
}
if (feof(data)) break;
i++;
}
// debug print data
printf("\n");
struct listNode* current = head;
while (current != NULL) {
printf("%s\n", current->name);
current = current->next;
}
printf("\n");
// starting node
printf("%s ", sourceNode->name);
// now walk through the graph from sourceNode until we reach the node "Home"
int totalWeight = 0;
i = 0;
while (i < 100) {
char* tmp = sourceNode->name;
if (strcmp(tmp, "Home") == 0) { // if were home then exit program
// ending node and cost
printf("%s %d", sourceNode->name, totalWeight);
return 0;
} else { // if were not home then keep looping
int index = (rand() % sourceNode->arcCnt); // Generates random number between 0 and sourceNode->arcCnt
sourceNode = sourceNode->arcs[index];
//printf("Going to: %s, Index: %d", sourceNode->name, totalWeight);
}
i++;
}
return 0;
}