DOAN/OU4/graph2.c

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


/*
 * graph2.c: Implementation of a dlist based graph for "Obligatorisk uppgift 4" in the "Datastructures and
 * algorithms" course at the Department of Computing Science, Umea University.
 *
 * Authors: Marc Meunier tfy22mmr
 *          Ellen Horneij tfy22ehj
 *          Jakob Nyström tfy22jnm
 *
 * Version information:
 *   v1.0  2025-05-25: First public version.
 *
 */

// ===========INTERNAL DATA TYPES ============

struct graph
{
    dlist *nodes; // The graph nodes are stored in a directed list
    int max_nodes;
    // int connected;
};

struct node
{
    const char *value;
    bool seen;
    dlist *edge;
};

// ===========INTERNAL FUNCTION IMPLEMENTATIONS ============

/**
 * node_entry_kill() - Return the memory allocated to a node entry.
 * @e: The entry to deallocate.
 *
 * Returns: Nothing.
 */
void node_entry_kill(void *v)
{
    node *n = v;
    free((void*)n->value);  // Cast away const and free the string
    dlist_kill(n->edge); // kills list
    free(n); // frees memory

}

/**
 * graph_entry_create() - Allocate and populate a graph entry.
 * @key: A pointer to a function to be used to compare keys.
 * @value: A pointer to a function (or NULL) to be called to
 *                 de-allocate memory for keys on remove/kill.
 *
 * Returns: A pointer to the newly created graph entry.
 */
node *node_entry_create(const char *value, int max_node)
{
    // Allocate space for a graph entry. Use calloc as a defensive
    node *n = calloc(1, sizeof(*n));

    // Populate the entry.
    char *tmp = malloc(strlen(value) + 1);
    if (tmp != NULL)
    {
        strcpy(tmp, value);
        n->value = tmp;
    }
    else
    {
        // Handle memory allocation failure
        free(n);
        return NULL;
    }

    // Set status to false, and create the list of edges
    n->seen = false;
    n->edge = dlist_empty(NULL); 
    return n;
}

// =================== GRAPH STRUCTURE INTERFACE ======================

/**
 * nodes_are_equal() - Check whether two nodes are equal.
 * @n1: Pointer to node 1.
 * @n2: Pointer to node 2.
 *
 * Returns: true if the nodes are considered equal, otherwise false.
 *
 */
bool nodes_are_equal(const node *n1, const node *n2)
{
    if (n1 == NULL || n2 == NULL)
    {
        return n1 == n2;
    }
    // compares string values of nodes
    return strcmp(n1->value, n2->value) == 0;
}

/**
 * graph_empty() - Create an empty graph.
 * @max_nodes: The maximum number of nodes the graph can hold.
 *
 * Returns: A pointer to the new graph.
 */
graph *graph_empty(int max_nodes)
{
    // Allocate the graph
    graph *g = calloc(1, sizeof(graph));

    // Create the list to hold the graph_entry-ies.
    g->nodes = dlist_empty(node_entry_kill);
    g->max_nodes = max_nodes;
    return g;
}

/*
 * graph_is_empty() - Check if a graph is empty, i.e. has no nodes.
 * @g: Graph to check.
 *
 * Returns: True if graph is empty, otherwise false.
 */
bool graph_is_empty(const graph *g)
{
    return dlist_is_empty(g->nodes);
}

/**
 * graph_insert_node() - Inserts a node with the given name into the graph.
 * @g: Graph to manipulate.
 * @s: Node name.
 *
 * Creates a new node with a copy of the given name and puts it into
 * the graph.
 *
 * Returns: The modified graph.
 */
graph *graph_insert_node(graph *g, const char *s)
{
    // create node
    node *n = node_entry_create(s, g->max_nodes);
    n->seen = false;

    // get start position of list
    dlist_pos pos = dlist_first(g->nodes);
    
    // iterate over list
    while (!dlist_is_end(g->nodes, pos))
    {
        // check node already exists
        node *m = dlist_inspect(g->nodes, pos);
        if (nodes_are_equal(n, m))
        {
            node_entry_kill(n);
            return g;
        }
        // go to next position
        pos = dlist_next(g->nodes, pos);
    }
    // inserts node into list
    dlist_insert(g->nodes, n, dlist_first(g->nodes));
    return g;
}

/**
 * graph_has_edges() - Check if a graph has any edges.
 * @g: Graph to check.
 *
 * Returns: True if graph has any edges, otherwise false.
 */
bool graph_has_edges(const graph *g)
{
    // get start position
    dlist_pos pos = dlist_first(g->nodes);

    // check for edges for every node
    while (!dlist_is_end(g->nodes, pos))
    {
        node *n = dlist_inspect(g->nodes, pos);
        if (!dlist_is_empty(n->edge))
        {
            return true;
        }
        // go to next position
        pos = dlist_next(g->nodes, pos);
    }
    return false;
}

/**
 * graph_find_node() - Find a node stored in the graph.
 * @g: Graph to manipulate.
 * @s: Node identifier, e.g. a char *.
 *
 * Returns: A pointer to the found node, or NULL.
 */
node *graph_find_node(const graph *g, const char *s)
{
    // get start position
    dlist_pos pos = dlist_first(g->nodes);

    while (!dlist_is_end(g->nodes, pos))
    {
        node *n = dlist_inspect(g->nodes, pos);
        // compare value with the one we are looking for
        if (strcmp(n->value, s) == 0)
        {
            return n;
        }
        // go to next position
        pos = dlist_next(g->nodes, pos);
    }
    return NULL;
}
/**
 * graph_node_is_seen() - Return the seen status for a node.
 * @g: Graph storing the node.
 * @n: Node in the graph to return seen status for.
 *
 * Returns: The seen status for the node.
 */
bool graph_node_is_seen(const graph *g, const node *n)
{
    // get start position
    dlist_pos pos = dlist_first(g->nodes);
    while (!dlist_is_end(g->nodes, pos))
    {
        node *e = dlist_inspect(g->nodes, pos);
        // if node is one we are looking for, check seen status
        if (nodes_are_equal(e, n))
        {
            return e->seen;
        }
        // increment position
        pos = dlist_next(g->nodes, pos);
    }
    return false;
}

/**
 * graph_node_set_seen() - Set the seen status for a node.
 * @g: Graph storing the node.
 * @n: Node in the graph to set seen status for.
 * @s: Status to set.
 *
 * Returns: The modified graph.
 */
graph *graph_node_set_seen(graph *g, node *n, bool seen)
{
    // get beginning position
    dlist_pos pos = dlist_first(g->nodes);

    while (!dlist_is_end(g->nodes, pos))
    {
        node *e = dlist_inspect(g->nodes, pos);
        // check if nodes are same as one we look for
        if (nodes_are_equal(e, n))
        {  
            // set node to seen
            e->seen = seen;
            break;
        }
        // increment pos in list
        pos = dlist_next(g->nodes, pos);
    }
    return g;
}

/**
 * graph_reset_seen() - Reset the seen status on all nodes in the graph.
 * @g: Graph to modify.
 *
 * Returns: The modified graph.
 */
graph *graph_reset_seen(graph *g)
{
    // get starting position
    dlist_pos pos = dlist_first(g->nodes);

    while (!dlist_is_end(g->nodes, pos))
    {
        // if node is seen, reset
        node *n = dlist_inspect(g->nodes, pos);
        if (n->seen == true)
        {
            n->seen = false;
        }
        // increment over list
        pos = dlist_next(g->nodes, pos);
    }
    return g;
}

/**
 * graph_insert_edge() - Insert an edge into the graph.
 * @g: Graph to manipulate.
 * @n1: Source node (pointer) for the edge.
 * @n2: Destination node (pointer) for the edge.
 *
 * NOTE: Undefined unless both nodes are already in the graph.
 *
 * Returns: The modified graph.
 */
graph *graph_insert_edge(graph *g, node *n1, node *n2)
{
    // get starting position
    dlist_pos pos = dlist_first(n1->edge);
    while (!dlist_is_end(n1->edge, pos))
    {
        node *n = dlist_inspect(n1->edge, pos);
        // check if node already is in edge list
        if (nodes_are_equal(n2, n))
        {
            return g;
        }
        // increment to next position
        pos = dlist_next(n1->edge, pos);
    }
    // inserts the edge in node list. 
    dlist_insert(n1->edge, n2, dlist_first(n1->edge));
    return g;
}

/**
 * graph_neighbours() - Return a list of neighbour nodes.
 * @g: Graph to inspect.
 * @n: Node to get neighbours for.
 *
 * Returns: A pointer to a list of nodes. Note: The list must be
 * dlist_kill()-ed after use.
 */
dlist *graph_neighbours(const graph *g, const node *n)
{
    // Create a new list
    dlist *copy = dlist_empty(NULL);

    if (n == NULL || n->edge == NULL) {
        return copy;
    }
    
    // Copy nodes to new list, so list can be dlost_kill-ed outside. 
    dlist_pos pos = dlist_first(n->edge);
    while (!dlist_is_end(n->edge, pos)) {
        void *node = dlist_inspect(n->edge, pos);
        dlist_insert(copy, node, dlist_first(copy));
        pos = dlist_next(n->edge, pos);
    }
    
    return copy;
}

/**
 * graph_kill() - Destroy a given graph.
 * @g: Graph to destroy.
 *
 * Return all dynamic memory used by the graph.
 *
 * Returns: Nothing.
 */
void graph_kill(graph *g)
{
    dlist_kill(g->nodes);
    free(g);
}

/**
 * graph_print() - Iterate over the graph elements and print their values.
 * @g: Graph to inspect.
 *
 * Iterates over the graph and prints its contents.
 *
 * Returns: Nothing.
 */
void graph_print(const graph *g)
{
    // get first position
    dlist_pos pos = dlist_first(g->nodes);
    // iterate and prints node
    while (!dlist_is_end(g->nodes, pos))
    {
        node *n = dlist_inspect(g->nodes, pos);
        printf("%s to nodes: ", (char *)n->value);
        
        // get edges pos, and print edges of node.
        dlist_pos pos_edge = dlist_first(n->edge);
        while (!dlist_is_end(n->edge, pos_edge))        
        {
            node *e = dlist_inspect(n->edge, pos_edge);
            printf("%s,", (char *)e->value);

            // goes to next edge in list
            pos_edge = dlist_next(n->edge, pos_edge);
        }
        printf("\n");

        // goes to next node in list.
        pos = dlist_next(g->nodes, pos);
    }
}