0

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;
}
FunkyMunky
  • 21
  • 5
  • When you do: `int index = (rand() % sourceNode->arcCnt);`, under `gdb`, I get a `SIGFPE` for integer division by zero, because `sourceNode->arcCnt` is zero. Note that `name` is `GroundRound` – Craig Estey Dec 10 '22 at 20:30
  • @FunkyMunky, Tip: simply `newGraph = (struct graphNode*)malloc(sizeof(struct graphNode));` with `newGraph = malloc(sizeof *newGraph);`. – chux - Reinstate Monica Dec 11 '22 at 02:51
  • Off-by-one `char name[100]; ... fscanf(data, "%100s", name);` --> `char name[100+1]; ... fscanf(data, "%100s", name);` . – chux - Reinstate Monica Dec 11 '22 at 02:53
  • `if (feof(data)) break;` --> [Why is “while( !feof(file) )” always wrong?](https://stackoverflow.com/q/5431941/2410359). I suspect this is OP's key problem: not checking the return value of the various `fscanf()` calls. – chux - Reinstate Monica Dec 11 '22 at 02:54
  • chux - Reinstate Monica thank you, for fixing my divide by 0 error but it still give a memory exception when I compare tmp and "Home" in Main. – FunkyMunky Dec 12 '22 at 03:27

0 Answers0