Making a graph data structure from an array

I think the problem I described yesterday is indeed a struggle with a graph data type. I’ve broken down the problem into something simple that demonstrates my larger test program’s problem. It’s all about knowing where you’ve been. I’ll illustrate the issue, and then go through some solutions I’ll attempt.

I have a 2d array that I want to represent as a graph data type. Each element of the array will be a vertex of the graph, and every connection between elements will be an edge of the graph. Since it’s a 2d array I know that each vertex will have at least 2 edges, and at the most 4. Each vertex of the graph is a structure I’ll allocate in memory. This structure stores the row and column position of the vertex, and it has four pointers to the potential four edges it can have (which are pointers to other vertex data structures) that I initialize to 0. I initialize them to 0 so that I know that those edges haven’t been visited yet. For clarity I refer to the edges as North, East, South, and West which are indexed in an array as (respectively) 0,1,2,3.


struct Node
{
     int row;
     int col;
     struct Node* direction[4];
};

So, direction[0] is North, direction[1] is East, direction[2] is South, direction[3] is West.

Here is a 2×2 array for my demonstration, with the numbers in the array being the “row,column” locations.

2d arrayHere’s how my test program works so far. I create a new vertex and pre-fill the location at (0,0) so that it starts at the top left of the array. My test program “scans” for legit potential edges in each element of the array, starting with the North edge and going clockwise. The top-left element of the array has no edge to the North, but it does have an edge to the East. This vertex doesn’t have an allocated East edge yet, so a new vertex is initialized and I set the East edge of the vertex at 0,0 to the memory location of the new vertex. I set the new vertex’s location to 0,1 and set the new vertex’s West edge to the memory location of the vertex at 0,0.

newvertex1

I won’t yet go into details about how the next parts happen (since I’m not super confident that it’s a good idea). In short, I recursively call the function that scans for legit edges, but set the starting point to the newly created vertex.

Now we have a new vertex and we’ll start scanning. There is no edge to the North or East, but there is a valid edge to the South. A new vertex at 1,1 is created and the respective edges of the current and new vertex are set.

newvertex2Now the same thing is done with the vertex at 1,1. The North edge has been visited (which it knows because its pointer to direction[0] is not set to 0) and there is no East or South edge, but there is a legit and unvisited edge to the West. A new vertex at 0,1 is created and the respective edges of the current and new vertex are set.

newvertex3Here is where the problematic behavior begins. We’re at the vertex at location 1,0 and the “find legit and un-visited edges” function starts. The vertex at 1,0 already has its East edge set (from when it was initialized), but that’s it. The function starts looking North, and sees a legit edge. It does not however, see an un-visited edge. A new vertex is created for a location in the 2d array that’s already been accounted for.

newvertex4This new duplicate vertex at 0,0 then goes through the same process as the original, and a duplicate vertex at 0,1 is created (then 1,1 and 1,0 and so on).

So, that’s the problem I’m having right now. Here are the two best ideas I have of fixing this and the potential new problems they might create.

1) Separately keep a table of visited locations and pointers to the vertexes at those locations. When checking potential edges, figure out what location those edges point to and look in the table to see of that location already has a vertex. If so, use that vertex, if not, create one and update the table. The potential problem here is that I’m not sure if that will gel right with my current recursive way of doing things.

2) At each vertex I’m testing, back-track the already-created paths to see if I’ve been to the array location I’m about to create a vertex to. The problem here is that this seems overly complicated.

The end goal here, once all these vertices and edges are created, is to then try a few path-finding strategies to see if I can solve the third Colossal Cue puzzle. I think I can do it without all this fuss, but I might as well learn something new while I’m at it, right?

This entry was posted in Hobbies, Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s