# C functions to delete edges and nodes from a Graph

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;

};

// A structure to represent an adjacency list node

int dest;

};

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

newNode->dest = dest;

newNode->next = NULL;

return newNode;

// A structure to represent an adjacency list

};

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

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

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

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

// is added at the begining

// Since graph is undirected, add an edge from

// dest to src also

answered Jun 9, 2020 by (15,580 points)
edited Jun 10, 2020 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;
} 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.

answered Jun 10, 2020 by (15,580 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. */
} 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. */
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;

return vertex;
}

{
/* TODO: Improve robustness: check if vertex is not NULL. */
}

/* 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. */

}
}
}

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)

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

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
{
}
}
}

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.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++)
}
}

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);

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;
}```