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