delete a specific node in a grapgh adjacency list -directed graph

Question

hi there I have this struct info

struct Node
{
  int dest, weight;
  struct Node *next;
};

I want to build a function that removes a specific node distance value my main function for calling the delete function will look like this>>

int main()
{
       .
       .
       .
      struct Graph *graph;
      Node_delete(graph,x);

       .
       .
       .
}

if (x==4) then the function will delete every node that contain the distance value of 4
if the node in the middle of the previous node will be connected to the next node
and if the node in the last node will be deleted and the previous node will point to null and so on...
so our graph result will look like this >>

any suggestions on how can I build the delete_node function?

Answer 1

LOOP L over head[]
   Step p through L
      IF "distance" ( however you decide to spell it ) = x
          IF this is first p of a l
              set head[] to p->next
          ELSE
              set previous next to current p->next
          delete p

Answer 2

Let's say you have a global graph with your graph (as you don't have it as argument).

The function will return the number of deleted nodes.

You have to loop on all list with a simple for:

for (int i = 0; i < graph.nodes; i++)

Then, if the first element should be removed you need to change the Node * into the head array. This is done with the while loop while (first && first->distance == distance)

Once you have delete the leading head, you can delete the other node with a while (n->next)

This will give something like:

static int Node_delete(Graph *graph, int distance) {
    int res = 0;
    for (int i = 0; i < graph->nodes; i++) {
        Node *first = graph->head[i];
        Node *n = first;
        while (first && first->distance == distance) {
            first = first->next;
            free(n);
            res++;
            n = first;
        }
        while (n && n->next) {
            Node *next= n->next;
            if (next->distance == distance) {
                n->next = next->next;
                free(next);
                res++;
            }
            n = n->next;
        }
        graph->head[i] = first;
    }
    return res;
}

You will the full and the graph with elements removed

0 -> d: 2, w: 3 -> d: 2, w: 3 -> d: 4, w: 5 -> Null
1 -> d: 7, w: 6 -> d: 4, w: 6 -> d: 5, w: 4 -> Null
2 -> d: 2, w: 7 -> d: 2, w: 7 -> d: 8, w: 9 -> Null
3 -> d: 10, w: 13 -> d: 10, w: 13 -> d: 11, w: 7 -> Null
0 -> d: 2, w: 3 -> d: 2, w: 3 -> Null
1 -> d: 7, w: 6 -> d: 5, w: 4 -> Null
2 -> d: 2, w: 7 -> d: 2, w: 7 -> d: 8, w: 9 -> Null
3 -> d: 10, w: 13 -> d: 10, w: 13 -> d: 11, w: 7 -> Null

Full code with your schema, create, print and delete were done for test purpose:

#include <stdio.h>
#include <stdlib.h>
typedef struct Node Node;

typedef struct Graph
{
  // An array of pointers to Node to represent an adjacency list
  size_t nodes;
  Node *head[];
} Graph;

// Data structure to store adjacency list nodes of the graph
struct Node
{
  int   distance;
  int   weight;
  Node *next;
};

static void graph_print(Graph *graph) {
    for (int i = 0; i < graph->nodes; i++) {
        printf("%d -> ", i);
        for (Node *n = graph->head[i]; n; n = n->next) {
            printf("d: %d, w: %d -> ", n->distance, n->weight);
        }
        printf("Null\n");
    }

}

static int Node_delete(Graph *graph, int distance) {
    int res = 0;
    for (int i = 0; i < graph->nodes; i++) {
        Node *first = graph->head[i];
        Node *n = first;
        while (first && first->distance == distance) {
            first = first->next;
            free(n);
            res++;
            n = first;
        }
        while (n && n->next) {
            Node *next= n->next;
            if (next->distance == distance) {
                n->next = next->next;
                free(next);
                res++;
            }
            n = n->next;
        }
        graph->head[i] = first;
    }
    return res;
}

static Node* node_create(int distance, int weight, Node *next) {
    Node *n = malloc(sizeof(Node));
    n->distance = distance;
    n->weight = weight;
    n->next = next;
    return n;
}
static void node_delete(Node *n) {
    if (n) {
        node_delete(n->next);
        free(n);
    }
}
static Graph* graph_create(int nodes) {
    Graph *g = malloc(sizeof(size_t) + nodes * sizeof(Node));
    g->nodes = nodes;
    return g;
}

static void graph_delete(Graph *graph) {
    for (int i = 0; i < graph->nodes; i++) {
        node_delete(graph->head[i]);
    }
    free(graph);
}

int main(void)
{
    Graph *graph = graph_create(4);
    Node *n;

    n = node_create(4, 5, NULL);
    n = node_create(2, 3, n);
    n = node_create(2, 3, n);
    graph->head[0] = n;

    n = node_create(5, 4, NULL);
    n = node_create(4, 6, n);
    n = node_create(7, 6, n);
    graph->head[1] = n;

    n = node_create(8, 9, NULL);
    n = node_create(2, 7, n);
    n = node_create(2, 7, n);
    graph->head[2] = n;

    n = node_create(11, 7, NULL);
    n = node_create(10, 13, n);
    n = node_create(10, 13, n);
    graph->head[3] = n;

    graph_print(graph);
    Node_delete(graph, 4);
    graph_print(graph);
    graph_delete(graph);

    return 0;
}