You really have a big mess on your hands. Contributed to by your typedef'ing of pointers, but primarily because you fail to allocate nv pointers, but instead allocate the same listAdj pointer and then immediately overwrite the pointer with NULL creating 100 memory leaks.
Think about it:
for (i = 0; i < nv; i++) {
graph->listAdj = (TypePointer*) malloc(sizeof(TypePointer));
}
(There is no need to cast the return of malloc, it is unnecessary. See: Do I cast the result of malloc? and... ALWAYS validate EVERY allocation)
graph->listAdj is a single-pointer that holds the address to the newly allocated block of memory each iteration that is then overwritten by each subsequent allocation.
Further, you then attempt to dereference the overwritten pointer and set pointers not in existence to NULL, e.g.:
for (i = 0; i < nv; i++) {
graph->listAdj[i] = NULL;
}
You only attempted to allocate a single graph->listAdj (albeit 100 times), not nv pointers as you intended. You must allocate storage for nv pointers at once.
Now let's start at the beginning and clean things up by remove ALL typedefs, and simply using int for bool, e.g.
#include <stdio.h>
#include <stdlib.h>
typedef struct aux {
int vDest;
int weight;
struct aux *next;
} TypeEdge;
typedef struct {
TypeEdge **listAdj;
int numVertices;
int numEdges;
} TypeGraph;
Now it is plainly clear to anyone looking at your code that listAdj is a pointer-to-pointer to TypeEdge. There is no guessing or having to hunt around later wondering what TypePointer 300 lines later, TypeEdge is TypeEdge, nothing more.
When you initializeGraph, you need to allocate all nv pointers is a single call to malloc, not in a loop. Then you can loop over the pointers setting them all NULL, e.g.
int initializeGraph (TypeGraph *graph, int nv)
{
if (nv < 0)
return 0;
graph->numVertices = nv;
graph->numEdges = 0;
int i;
if ((graph->listAdj = malloc(sizeof *graph->listAdj * nv)) == NULL) {
perror ("malloc-graph->listAdj");
return 0;
}
for (i = 0; i < nv; i++)
(graph->listAdj)[i] = NULL;
return 1;
}
Next when you insertEdge(), you must handle the case where you are inserting the first edge for that vertex, or whether you need to iterate to the end of the list and insert there. You also need to adjust how you iterate to the end to ensure you do not attempt to access actual->next if actual is NULL. Putting that together, you can do:
TypeEdge *insertEdge (int v1, int v2, int weight, TypeGraph *graph)
{
if (v1 < 0 || v1 > graph->numVertices ||
v2 < 0 || v2 > graph->numVertices) {
return NULL;
}
TypeEdge *actual = graph->listAdj[v1];
while (actual && actual->next)
actual = actual->next;
TypeEdge *pNew = malloc(sizeof *pNew);
if (!pNew) {
perror ("malloc-pNew");
return NULL;
}
pNew->vDest = v2;
pNew->weight = weight;
pNew->next = NULL;
if (!actual)
graph->listAdj[v1] = pNew;
else
actual->next = pNew;
return (pNew);
}
(note: how the return type of the function has been changed to TypeEdge * from void so you have a meaningful return that can indicate Success/Failure of your attempt to insert the edge. Never allocate within a void function without a way of indicating to the calling function whether the allocation (and remainder of critical steps) have succeeded or failed)
While your main() attempts to insertEdge(), it doesn't give you any indication of what happened. Unless you have some way of validating you actually inserted the edge, it kind of leaves you wondering. Just write a short set of print functions to handle outputting the list of edges for each vertex that has them, e.g.
void prnedge (const TypeEdge *e)
{
do
printf (" %3d %3d\n", e->vDest, e->weight);
while ((e = e->next));
}
void print_edge (const TypeEdge *e, int edge)
{
printf ("\nedge %d\n", edge);
prnedge (e);
}
void print_graph (const TypeGraph *g)
{
for (int i = 0; i < g->numVertices; i++)
if (g->listAdj[i])
print_edge (g->listAdj[i], i);
}
If you have allocated memory, you need to be able to free that memory as well. A similar short set of functions can handle freeing each list, e.g.
void freelist (TypeEdge *l)
{
while (l) {
TypeEdge *victim = l;
l = l->next;
free (victim);
}
}
void free_graphlists (TypeGraph *g)
{
for (int i = 0; i < g->numVertices; i++)
if (g->listAdj[i])
freelist (g->listAdj[i]);
free (g->listAdj);
}
Which you can call in main() as:
int main (void) {
TypeGraph graph;
int result = initializeGraph (&graph, 100);
if (result) {
insertEdge (2, 3, 1, &graph);
insertEdge (2, 4, 1, &graph);
}
print_graph (&graph);
free_graphlists (&graph);
return 0;
}
Putting it altogether, you could do:
#include <stdio.h>
#include <stdlib.h>
typedef struct aux {
int vDest;
int weight;
struct aux *next;
} TypeEdge;
typedef struct {
TypeEdge **listAdj;
int numVertices;
int numEdges;
} TypeGraph;
int initializeGraph (TypeGraph *graph, int nv)
{
if (nv < 0)
return 0;
graph->numVertices = nv;
graph->numEdges = 0;
int i;
if ((graph->listAdj = malloc(sizeof *graph->listAdj * nv)) == NULL) {
perror ("malloc-graph->listAdj");
return 0;
}
for (i = 0; i < nv; i++)
(graph->listAdj)[i] = NULL;
return 1;
}
TypeEdge *insertEdge (int v1, int v2, int weight, TypeGraph *graph)
{
if (v1 < 0 || v1 > graph->numVertices ||
v2 < 0 || v2 > graph->numVertices) {
return NULL;
}
TypeEdge *actual = graph->listAdj[v1];
while (actual && actual->next)
actual = actual->next;
TypeEdge *pNew = malloc(sizeof *pNew);
if (!pNew) {
perror ("malloc-pNew");
return NULL;
}
pNew->vDest = v2;
pNew->weight = weight;
pNew->next = NULL;
if (!actual)
graph->listAdj[v1] = pNew;
else
actual->next = pNew;
return (pNew);
}
void prnedge (const TypeEdge *e)
{
do
printf (" %3d %3d\n", e->vDest, e->weight);
while ((e = e->next));
}
void print_edge (const TypeEdge *e, int edge)
{
printf ("\nedge %d\n", edge);
prnedge (e);
}
void print_graph (const TypeGraph *g)
{
for (int i = 0; i < g->numVertices; i++)
if (g->listAdj[i])
print_edge (g->listAdj[i], i);
}
void freelist (TypeEdge *l)
{
while (l) {
TypeEdge *victim = l;
l = l->next;
free (victim);
}
}
void free_graphlists (TypeGraph *g)
{
for (int i = 0; i < g->numVertices; i++)
if (g->listAdj[i])
freelist (g->listAdj[i]);
free (g->listAdj);
}
int main (void) {
TypeGraph graph;
int result = initializeGraph (&graph, 100);
if (result) {
insertEdge (2, 3, 1, &graph);
insertEdge (2, 4, 1, &graph);
}
print_graph (&graph);
free_graphlists (&graph);
return 0;
}
Example Use/Output
$ ./bin/edgetype
edge 2
3 1
4 1
Memory Use/Error Check
In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.
It is imperative that you use a memory error checking program to insure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.
For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.
$ valgrind ./bin/edgetype
==21679== Memcheck, a memory error detector
==21679== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==21679== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==21679== Command: ./bin/edgetype
==21679==
edge 2
3 1
4 1
==21679==
==21679== HEAP SUMMARY:
==21679== in use at exit: 0 bytes in 0 blocks
==21679== total heap usage: 3 allocs, 3 frees, 832 bytes allocated
==21679==
==21679== All heap blocks were freed -- no leaks are possible
==21679==
==21679== For counts of detected and suppressed errors, rerun with: -v
==21679== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Always confirm that you have freed all memory you have allocated and that there are no memory errors.
Look things over and let me know if you have further questions.
