DOAN/OU4/is_connected.c

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <graph.h>
#include <ctype.h>
#include <queue.h>
#include <dlist.h>
#include <string.h>

#define MAXNODENAME 40
#define BUFSIZE 400

/*
 * is:connected.c: The main program for traversing a graph for "Obligatorisk uppgift 4" in the "Datastructures and
 * algorithms" course at the Department of Computing Science, Umea University.
 *
 * Authors: Ellen Horneij tfy22ehj
 *          Jakob Nyström tfy22jnm
 *          Marc Meunier tfy22mmr
 *
 * Version information:
 *   v1.0  2025-05-25: First public version.
 *   v2.0  2025-06-02: Fixed traversing
 *   v3.0  2025-07-29: Fixed error messages 
 *
 */

// ===========HELP FUNCTIONS ============
/**
 * @brief Find position of first non-whitespace character.
 *
 * @param s - string to search.
 * @return int - Returns the position of the first non-whitespace character, or -1 if not found.
 */
int first_non_white_space(const char *s)
{
    int i = 0; // Start at first char.

    // Advance as long as we're loooking at white-space until we hit EOL.
    while (s[i] && isspace(s[i]))
    {
        i++;
    }
    // We found a non-whitespace char.
    if (s[i])
    {
        // It was a proper characted. Return its position.
        return i;
    }
    else
    {
        // It was the null terminator. Return fail.
        return -1;
    }
}

/**
 * @brief Determine if the string is blank.
 *
 * @param s - string to search.
 * @return true if the line contains only whitespace chars.
 * @return false if the line contains at least one non-whitespace char.
 */

bool line_is_blank(const char *s)
{
    // Line is blank if it only contained white-space chars.
    return first_non_white_space(s) < 0;
}

/**
 * @brief Determine if the string is a comment line.
 *
 * @param s - string to search.
 * @return true if the line is a comment line.
 * @return false if the line is not a comment line.
 *
 * A comment line has a hash sign '#' as the first non-whitespace char on the line.
 */
bool line_is_comment(const char *s)
{
    int i = first_non_white_space(s);
    return (i >= 0 && s[i] == '#');
}

/**
 * @brief Extract node names from a line from the map file.
 *
 * @param buf - Input buffer.
 * @param n1 - Output buffer for the first node name. Must be at least MAXNODENAME+1 long.
 * @param n2 - Ditto for the second node name.
 * @return int - Returns the number of correctly parsed node names. If the return value is 2, both n1
 * and n2 contain node names. If the return value is less than 2, parsing of at least one node name
 * failed, in which case the content of n1 and n2 are undefined.
 */
int parse_map_line(const char *buf, char *n1, char *n2)
{
    // Create a format string the will do the work.
    char fmt[20];
    // This will generate the format string " %40s %40s" if MAXNODENAME is 40.
    snprintf(fmt, sizeof(fmt), " %%%ds %%%ds", MAXNODENAME, MAXNODENAME);

    // sscanf does all the necessary parsing.
    // Node names must be separated by whitespace.
    // Whitespace before the first node name is allowed.
    // Anything after the second node name is ignored.
    int n = sscanf(buf, fmt, n1, n2);

    // The return value from sscanf contains the number of properly parsed format codes, i.e. the
    // number of node names.
    return n;
}

/**
 * FUNCTION TO TRAVERSE THE GRAPH
 * @g: pointer to the graph
 * @src: pointer to source node
 * @dest: pointer to destination node
 */
bool find_path(graph *g, node *src, node *dest)
{

    // Mark the starting node as seen
    g = graph_node_set_seen(g, src, true);
    dlist *neighbours = dlist_empty(NULL);
    // Put it in an empty queue
    queue *q = queue_enqueue(queue_empty(NULL), src);
    while (!queue_is_empty(q))
    {
        // pick the first node from queue
        src = queue_front(q);
        q = queue_dequeue(q);

        // if node equals destinatiom node, return true
        if (nodes_are_equal(src, dest))
        {
            // Deallocate the queue and list
            queue_kill(q);
            dlist_kill(neighbours);
            return true;
        }
        // remove list before making new.
        if (neighbours != NULL)
        {
            dlist_kill(neighbours);
        }
        // get the neighbours
        neighbours = graph_neighbours(g, src);
        dlist_pos p = dlist_first(neighbours);

        // Iterate over the lists of neigbours
        while (!dlist_is_end(neighbours, p))
        {

            if (!graph_node_is_seen(g, dlist_inspect(neighbours, p)))
            {
                // Mark unseen node as seen and put in queue
                g = graph_node_set_seen(g, dlist_inspect(neighbours, p), true);
                q = queue_enqueue(q, dlist_inspect(neighbours, p));
            }
            p = dlist_next(neighbours, p);
        }
    }
    // Deallocate the list and the queue
    dlist_kill(neighbours);
    queue_kill(q);
    return false;
}

/**
 * check_node_name - function used to find errors in node name
 *
 * Returns: Exit faliure if error in map file
 */
void check_node_name(char *n1, char *n2, char *data)
{
        int k = parse_map_line(data, n1, n2);

        //Print error if number of correct node names is not 2
        if (k != 2)
        {
            fprintf(stderr, "Error reading the file\n");
            exit(EXIT_FAILURE);
        }
        //Check for non alphanumeric characters
        for (int j = 0; j < strlen(n1); j++)
        {
            if (isalnum(n1[j])==0)
            {
                fprintf(stderr, "Error non alphanumeric\n");
                exit(EXIT_FAILURE);                
            }
        }
        for (int i = 0; i < strlen(n2); i++)
        {
            if (isalnum(n2[i])==0)
            {
                fprintf(stderr, "Error non alphanumeric\n");
                exit(EXIT_FAILURE);                
            }
        }

}

/**
 * insert_nodes - insert the nodes to the graph
 * Returns: A graph with the input nodes inserted
 */
graph *insert_nodes(graph *g, char *n1, char *n2)
{
        g = graph_insert_node(g, n1);
        g = graph_insert_node(g, n2);

        // Get pointers to the nodes from the graph
        node *m1 = graph_find_node(g, n1);
        node *m2 = graph_find_node(g, n2);

        // Check that both nodes exist
        if (m1 == NULL || m2 == NULL)
        {
            fprintf(stderr, "Error: node not found for edge: %s - %s\n", n1, n2);
            exit(EXIT_FAILURE);
        }

        // Insert the edges between the source and destination nodes and between the nodes themselves
        g = graph_insert_edge(g, m1, m1);
        g = graph_insert_edge(g, m2, m2);
        g = graph_insert_edge(g, m1, m2);
    

    return g;
}

/**
 * graph_from_file - reads the file and constructs a graph with it's contents
 * Returns: A pointer to the constructed graph
 */
graph *graph_from_file(int argc, char *argv[])
{
    char data[40];

    // Open the file
    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s <filename>\n", argv[0]);
        return NULL;
    }
    const char *filename = argv[1];

    // Print error message if file did not read correctly an exit program
    FILE *fptr = fopen(filename, "r");
    if (fptr == NULL)
    {
        perror("Error opening file\n");
        return NULL;
    }

    // Read the first line of the map-file
    fgets(data, 40, fptr);

    // Ignore comments and blank rows
    while (line_is_blank(data) || line_is_comment(data))
    {
        fgets(data, 40, fptr);
    }

    //Check that first non blank or coment line is a digit 
    for (int i = 0; i < strlen(data) - 1; i++)
    {
        if (!isdigit(data[i]))
        {
            fprintf(stderr, "Error: first row is not a number\n");
            exit(EXIT_FAILURE);
        }
    }
    // Read the number of edges in the map-file and create an empty graph
    int nr_of_edges = atoi(data);
    graph *g = graph_empty(2 * nr_of_edges);

    // Iterates over the edge imputs
    for (int i = 0; i < nr_of_edges; i++)
    {
        // Read the data, parse the data and insert it into nodes in the graph
        fgets(data, 40, fptr);
        char n1[MAXNODENAME + 1];
        char n2[MAXNODENAME + 1];
        check_node_name(n1,n2,data);
        g = insert_nodes(g,n1,n2);
    }
    // Close the file and return the graph
    fclose(fptr);
    return g;
}

/**
 * main - The main program that handles user inputs and runs all of the help functions
 *
 * Returns: 0 if program exits normally
 *
 */
int main(int argc, char *argv[])
{
    // Read the file and insert it into a graph
    graph *g = graph_from_file(argc, argv);

    // If file opening fails
    if (g == NULL)
    {
        return EXIT_FAILURE;
    }

    char src[MAXNODENAME + 1];
    char dest[MAXNODENAME + 1];
    char fmt[20];
    char buf[100];

    // Print the user interface
    printf("Enter origin and destination (quit to exit): ");

    // This will generate the format string " %40s %40s" if MAXNODENAME is 40.
    snprintf(fmt, sizeof(fmt), " %%%ds %%%ds", MAXNODENAME, MAXNODENAME);

    while (fgets(buf, sizeof(buf), stdin) != NULL)
    {
        // Reads the input from the user
        sscanf(buf, fmt, src, dest);

        // Quit the program if the user enters "quit"
        if (strcmp(src, "quit") == 0)
        {
            break;
        }

        // Check that the nodes exist in the graph
        node *nsrc = graph_find_node(g, src);
        node *ndest = graph_find_node(g, dest);
        if (nsrc == NULL || ndest == NULL)
        {
            printf("One or both nodes not found in the graph.\n");
        }
        // If the nodes exist check if there is a path and print the result
        else if (find_path(g, nsrc, ndest))
        {
            printf("There is a path from %s to %s.\n\n", src, dest);
            g = graph_reset_seen(g);
        }
        else
        {
            printf("There is no path from %s to %s.\n\n", src, dest);
            g = graph_reset_seen(g);
        }
        printf("Enter origin and destination (quit to exit): ");
    }

    // Print exit message and kill the graph
    printf("Normal exit.\n");
    graph_kill(g);
    return 0;
}