C functions to delete edges and nodes from a Graph

0 votes
asked May 17 by Ken Kaneki (130 points)

Hi guys, I would like help with writing two functions: one to delete an edge from a Graph and one to delete a node from a Graph. The implementation I am currently using is the following: 

struct Graph{

  int V;

  struct AdjList* array;

 };

 // A structure to represent an adjacency list node 

struct AdjListNode 

    int dest; 

    struct AdjListNode* next; 

}; 

// A utility function to create a new adjacency list node 

struct AdjListNode* newAdjListNode(int dest) 

    struct AdjListNode* newNode = 

     (struct AdjListNode*) malloc(sizeof(struct AdjListNode)); 

    newNode->dest = dest; 

    newNode->next = NULL; 

    return newNode; 

  

// A structure to represent an adjacency list 

struct AdjList 

    struct AdjListNode *head;  

}; 

struct Graph* createGraph(int V) 

    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); 

    graph->V = V; 

  

    // Create an array of adjacency lists.  Size of array will be V 

    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList)); 

  

    // Initialize each adjacency list as empty by making head as NULL 

    for (int i = 0; i < V; ++i) 

        graph->array[i].head = NULL; 

  

    return graph; 

// Adds an edge to an undirected graph 

void addEdge(struct Graph* graph, int src, int dest) 

    // Add an edge from src to dest.  A new node is  

    // added to the adjacency list of src.  The node 

    // is added at the begining 

    struct AdjListNode* newNode = newAdjListNode(dest); 

    newNode->next = graph->array[src].head; 

    graph->array[src].head = newNode; 

  

    // Since graph is undirected, add an edge from 

    // dest to src also 

    newNode = newAdjListNode(src); 

    newNode->next = graph->array[dest].head; 

    graph->array[dest].head = newNode; 

Thank you in advance!

2 Answers

0 votes
answered Jun 9 by Peter Minarik (4,890 points)
edited Jun 10 by Peter Minarik

Preparation

There isn't a simple few line solution for the problem.

The main thing here, I believe is that one has to make a decision on the data structure: how do you want to store a graph? Also, what is a graph?

It's always a good idea to comment your code so others can easily understand what the fields are, what the methods do, etc. Use descriptive names. E.g. I look at the code and am not sure what Graph.V is when I see it. (After looking at how it's used it seems to me it's the number of adjacency lists in the graph.)

Some other notes. It's often useful to define a type so you don't have to say "struct Graph" all the time, just can refer to it as "Graph".

typedef struct
{
    int V;
    struct AdjList* array;
} Graph;

What the above line does is that it creates an anonymous structure and it's combined with typedef to create a new type.

Why I am saying that this is a lengthy task is:

  • You need to store things dynamically, as you may want to add and remove nodes and edges. This means using linked lists or "dynamic arrays" (using realloc)
  • This is C, not C++ (right?!) so you cannot use existing C++ containers, such as std::vector.
  • Generics do not exist in C, so you have to duplicate the list modification methods (add, remove) for all the lists you have. Alternatively, you can use a typeless structure to store your data (void *) so you don't need to duplicate methods. But then you'll have to cast your pointers every time you try to access them in the list.
  • Deleting nodes from the graph means deleting edges as well.

So yeah, this problem is not a few minutes' work. :)

Implementation

‚ÄčI've spend some sweet time doing this. Originally I went with a linked list, but that's so much more pain (especially in C without generics) than using an array and dynamically reallocating it.

So here's my solution. I've spend quite a few hours with it.

I've done some basic testing (see the main method). Due to lack of time, I didn't have time to test everything thoroughly. So go ahead, yank it left and right. Break it. Have some fun fixing it and improving it.

0 votes
answered Jun 10 by Peter Minarik (4,890 points)

Implementation (Cont'd)

Due to the 8000 chars limit (and comments not supporting formatting) I've posted the implementation in a second "answer" of mine.
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int id;                   /* The ID of the vertex. */
    size_t nAdjacentVertices; /* How many adjecent vertices this vertex has. */
    int * adjecentVertexIds;  /* The ID of the adjecent vertices. */
} Vertex;

typedef struct
{
    size_t nVertices;         /* How many vertices the graph has. */
    Vertex * vertices;        /* The array of the vertices in the graph. */
} Graph;

Graph * CreateNewGraph()
{
    return (Graph*)calloc(1, sizeof(Graph)); /* Creates an empty graph. nVertices = 0, vertices = NULL */;
}

void DestroyGraph(Graph ** graph)
{
    if (!*graph) /* If the graph does not exist, then there's nothing to do */
        return;
        
    for (int i = 0; i < (*graph)->nVertices; i++)   /* Repeat through all the vertices. */
    {
        Vertex * vertex = &((*graph)->vertices[i]); /* Get the pointer of the Vertex inside the vertices array. */
        if (vertex->adjecentVertexIds)              /* If there are adjecent vertex IDs... */
            free(vertex->adjecentVertexIds);        /* ... release the memory allocated for the adjecent vertex IDs. */
    }

    free((*graph)->vertices);   /* Release the memory allocated for the vertices. */
    free(*graph);               /* Release the memory allocated for the graph. */
    *graph = NULL;              /* This is not necessary, but setting the value to NULL allows easier debugging if you try to dereference it by accident. */
}

Vertex * AddNewVertex(Graph * graph, int vertexId)
{
    /* TODO: Improve robustness: check if graph is not NULL. */
    graph->nVertices++;
    graph->vertices = (Vertex*)realloc(graph->vertices, sizeof(Vertex) * graph->nVertices);

    Vertex * vertex = &graph->vertices[graph->nVertices - 1];
    vertex->id = vertexId;
    vertex->nAdjacentVertices = 0;
    vertex->adjecentVertexIds = NULL;

    return vertex;
}

void AddAdjecentVertex(Vertex * vertex, int adjecentVertexId)
{
    /* TODO: Improve robustness: check if vertex is not NULL. */
    vertex->nAdjacentVertices++;
    vertex->adjecentVertexIds = (int*)realloc(vertex->adjecentVertexIds, sizeof(int) * vertex->nAdjacentVertices);
    vertex->adjecentVertexIds[vertex->nAdjacentVertices - 1] = adjecentVertexId;
}

/* Helper function, not exposed outside of this compulation unit. Hence the `static` modifier. */
/* This is a simple solution, assuming we do not care about the order of the adjecent vertex IDs.
   Thus, we can just put the last element in the vertor to the place where we are deleting from.
   If we would care about the order, then we need to shift every element left starting from the
   position, where we delete `vertexId` from. */
static void RemoveAdjacentVertex(Vertex * vertex, int vertexId)
{
    for (int j = 0; j < vertex->nAdjacentVertices; j++)
    {
        /* This is based on the assumption, that one vertex ID is not listed here multiple times.*/
        if (vertex->adjecentVertexIds[j] == vertexId) /* Edge detected */
        {
            if (j != vertex->nAdjacentVertices - 1) /* No need to swap if we want to delete the last item. */
                vertex->adjecentVertexIds[j] = vertex->adjecentVertexIds[vertex->nAdjacentVertices - 1]; /* Move the last adjecent vertex ID to the position where we would delete from. After this, all we need to do is just reduce the size of the array. */

            vertex->nAdjacentVertices--; /* Decrease the number of adjecent vertices. */
            vertex->adjecentVertexIds = (int*)realloc(vertex->adjecentVertexIds, sizeof(int) * vertex->nAdjacentVertices); /* Resize the adjecency array. */
        }
    }
}

static Vertex * FindVertex(Graph * graph, int vertexId)
{
    for (int i = 0; i < graph->nVertices; i++)
        if (graph->vertices[i].id == vertexId)
            return &graph->vertices[i];

    return NULL;
}

void RemoveEdge(Graph * graph, int vertexId1, int vertexId2)
{
    if (!graph) /* Trying to remove from a non-existing graph. */
        return; /* Nothing to do here. */

    Vertex * vertex1 = FindVertex(graph, vertexId1);
    if (vertex1)
        RemoveAdjacentVertex(vertex1, vertexId2);

    Vertex * vertex2 = FindVertex(graph, vertexId2);
    if (vertex2)
        RemoveAdjacentVertex(vertex1, vertexId1);
}

void RemoveVertex(Graph * graph, int vertexId)
{
    if (!graph) /* Trying to remove from a non-existing graph. */
        return; /* Nothing to do here. */
    
    for (int i = 0; i < graph->nVertices; i++)
    {
        Vertex * vertex = &graph->vertices[i];
        if (vertex->id == vertexId)
        {
            /* Similarly to `RemoveAdjacentVertex`, for simplicity the last vertex will be moved to this location and the size of the vertices array will be reduced. */
            if (i != graph->nVertices - 1)
            {
                graph->vertices[i] = graph->vertices[graph->nVertices - 1]; /* Copy the last element from the vertex array to the point where we want to delete. Overwrite it. */
                i--; /* Let's try again the vertex at this position (this will be the vertex originally being in the last position) when the next loop iteration starts. */
            }
            graph->nVertices--; /* Decrease the number of vertices. */
            graph->vertices = (Vertex*)realloc(graph->vertices, sizeof(Vertex) * graph->nVertices); /* Resize the vertex array. */
        }
        else
        {
            RemoveAdjacentVertex(vertex, vertexId);
        }
    }
}

void PrintGraph(Graph * graph)
{
    if (!graph)
    {
        printf("Graph does not exist.\n");
        return;
    }
    
    printf("Graph with %lu vertices: [", graph->nVertices);
    if (graph->nVertices > 0)
    {
        printf("%d", graph->vertices[0].id);
        for (int i = 1; i < graph->nVertices; i++)
        {
            printf(", %d", graph->vertices[i].id);
        }
    }
    printf("]\n");
    printf("Edges:\n");
    for (int i = 0; i < graph->nVertices; i++)
    {
        Vertex * vertex = &graph->vertices[i];
        for (int j = 0; j < vertex->nAdjacentVertices; j++)
            printf("\t%d -- %d\n", vertex->id, vertex->adjecentVertexIds[j]);
    }
}

int main()
{
    /* Let's create a full graph with 5 vertices, all connected. Hail the pentagram! :) */
    Graph * graph = CreateNewGraph();
    
    Vertex * vertex0 = AddNewVertex(graph, 0);
    Vertex * vertex1 = AddNewVertex(graph, 1);
    Vertex * vertex2 = AddNewVertex(graph, 2);
    Vertex * vertex3 = AddNewVertex(graph, 3);
    Vertex * vertex4 = AddNewVertex(graph, 4);
    
    AddAdjecentVertex(vertex0, 1);
    AddAdjecentVertex(vertex0, 2);
    AddAdjecentVertex(vertex0, 3);
    AddAdjecentVertex(vertex0, 4);
    
    AddAdjecentVertex(vertex1, 2);
    AddAdjecentVertex(vertex1, 3);
    AddAdjecentVertex(vertex1, 4);
    
    AddAdjecentVertex(vertex2, 3);
    AddAdjecentVertex(vertex2, 4);

    AddAdjecentVertex(vertex3, 4);
    
    printf("The full graph:\n");
    printf("---------------\n");
    PrintGraph(graph);
    
    /* Let's remove an edge. */
    RemoveEdge(graph, 0, 3);
    printf("\n\nAfter removing edge 0 -- 3:\n");
    printf("---------------------------\n");
    PrintGraph(graph);

    /* Let's remove a vertex. */    
    RemoveVertex(graph, 2);
    printf("\n\nAfter removing vertex 2:\n");
    printf("------------------------\n");
    PrintGraph(graph);
    
    DestroyGraph(&graph);
    return 0;
}
Welcome to OnlineGDB Q&A, where you can ask questions related to programming and OnlineGDB IDE and and receive answers from other members of the community.
...