2

I have created a graph datastructure using linked lists. With this code:

typedef struct vertexNode *vertexPointer; typedef struct edgeNode *edgePointer; void freeGraph(vertexPointer); /* announce function */ struct edgeNode{ vertexPointer connectsTo; edgePointer next; }; struct vertexNode{ int vertex; edgePointer next; };

Then I create a graph in which I have 4 nodes, lets say A, B, C and D, where: A connects to D via B and A connects to D via C. With linked lists I imagine it looks like this:

what the graph looks like

Finally, I try to free the graph with freeGraph(graph).

void freeEdge(edgePointer e){ if (e != NULL) { freeEdge(e->next); freeGraph(e->connectsTo); free(e); e = NULL; } } void freeGraph(vertexPointer v){ if (v != NULL) { freeEdge(v->next); free(v); v = NULL; } }

That's where valgrind starts complaining with "Invalid read of size 4", "Address 0x41fb0d4 is 4 bytes inside a block of size 8 free'd" and "Invalid free()". Also it says it did 8 mallocs and 9 frees.

I think the problem is that the memory for node D is already freed and then I'm trying to free it again. But I don't see any way to do this right without having to alter the datastructure.

What is the best way to prevent these errors and free the graph correctly, if possible without having to alter the datastructure? Also if there are any other problems with this code, please tell. Thanks!

greets, semicolon

Improve this question
0

5 Answers 5

Reset to default
2

The lack of knowing all the references makes this a bit difficult. A bit of a hack, but faced with the same issue I would likely use a pointer set (a list of unique values, in this case pointers).

  • Walk the entire graph, pushing nodes pointers into the set only if not already present (this the definition of 'set')
  • Walk the set, freeing each pointer (since they're unique, no issue of a double-free)
  • Set graph to NULL.

I'm sure there is an elegant recursive solution to this, but faced with the task as stated, this seems doable and not overtly complicated.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I added a vertexPointer nextNode to the vertexNode struct to keep track of a unique set of nodes. Now I free all edges of the first node and go to the nextNode. So far it is the simplest solution I think.
@semicolon That will work nicely. In that you're effectively keeping the queue in the graph, which is even more awesomeness. gj.
2

Instead of allocating the nodes and edges on a global heap, maybe you can allocate them in a memory pool. To free the graph, free the whole pool.

Improve this answer

Comments

1

I would approach this problem by designing a way to first cleanly remove each node from the graph before freeing it. To do this cleanly you will have to figure out what other nodes are referencing the node you are about to delete and remove those edges. Once the edges are removed, if you happen to come around to another node that had previously referenced the deleted node, the edge will already be gone and you won't be able to try to delete it again.

The easiest way would be to modify your data structure to hold a reference to "incoming" edges. That way you could do something like:

v->incoming[i]->next = null; // do this for each edge in incoming freeEdge(v->next); free(v); v = NULL;

If you didn't want to update the data structure you are left with a hard problem of searching your graph for nodes that have edges to the node you want to delete.

Improve this answer

1 Comment

Or to generalize, preserve the invariants. For each insert operation there should be a corresponding remove operation that preserves the integrity of the data structure. For example, to remove an element in a doubly linked list the two adjacent elements are connected. This wouldn't be necessary when trashing the whole list, but that's a special case that lists have. In general, this special case wont exist. Find the remove operation and iterate on that to delete a graph.
0

It's because you've got two recursions going on here, and they're stepping on each other. freeGraph is called once to free D (say, from B) and then when the initial call to freeGraph comes back from freeEdge, you try freeing v -- which was already taken care of deeper down. That's a poor explanation without an illustration, but there ya go.

You can get rid of one recursions so they're not "crossing over", or you can check before each free to see if that node has already been taken care of by the other branch of the recursion.

Improve this answer

Comments

0

Yes, the problem is that D can be reached over two paths and freed twice.

You can do it in 2 phases: Phase 1: Insert the nodes you reached into a "set" datastructure. Phase 2: free the nodes in the "set" datastructure.

A possible implementation of that set datastructure, which requires extending your datastructure: Mark all nodes in the datastructure with a boolean flag, so you don't insert them twice. Use another "next"-pointer for a second linked list of all the nodes. A simple one.

Another implementation, without extending your datastructure: SOmething like C++ std::set<>

Another problem: Are you sure that all nodes can be reached, when you start from A? To avoid this problem, insert all nodes into the "set" datastructure at creation time (you won't need the marking, then).

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.