Lord of the Pointers
I’ve been coding a lot the last two days. It’s been pointer-mania. I have an array of linked lists, which, while it doesn’t sound bad, actually has all sorts of dereferencing issues.
struct Node
{
int data;
enum color_t {white, gray, black} color;
int pred;
int time;
Node *prev;
Node *next;
};
One Pointer to rule them all,
Node *AdjacencyList = new Node[num_vertices];
I have a pointer of nodes set up as an array after some computations that gets set up as an array. I use dynamic arrays as opposed to actually declaring the array of size num_vertices because this is how I was taught it was the proper way to declare an array that is not of a constant size. Either works, but it seems right. AdjacencyList represents all of the different vertices in a graph and each list tells which vertices the current vertex has edges to.
One Pointer to find them,
Node *TransposedAdjacencyList = new Node[num_vertices];
This pointer points to the same data structure that AdjacencyList points to. However, this pointer represents a completely transposed graph. All places where someting in AdjacencyList is pointing to something get pointed back at instead. With these two graphs the strongly connected components of Adjacency List can be computed.
One Pointer to bring them all and in the darkness bind them
Node *ptr;
ptr serves a special purpose. It points at any given element of any given vertex in either graph. This allows access to things like the color of a graph with ptr->color as opposed to using a function named color in the fashion color(&AdjacencyList[this_vertex]). Recursion over individual vertices is much easier as well because there are no questions if the address of operator (operator&) needs to be used or whether at some given time the dereferencing operator * must be used in order to use the member selection operator ->.
In the land of the Heap where the Segmentation Faults lie.
delete AdjacencyList;
Currently I do not return memory to the heap when I am finished. I can only hope that the kernel is cleaning up after me. As far as I know removing the head of a linked list does not work in my toolkit. I can only hope that when this project is complete and the code is graded that such issues are not noticed.