FortKnox's Journal: Developers! Developers! Developers!

Question:
Have you ever had to deal with graphs? I am assembling a structure as a hashmap. But in some instances I may want to build (at runtime) a graph from objects within this hashmap.
The words "graph theory" sends chills up my spine. But is there anyway to assemble graphs (think 3d) that are attached at any 4 points (think north, south, east, west, up, and down. They can use 1..* of the directions), and establish two points next to each other but not attached?

In other words, start at a spot. You can either go up or down. If you go up, you can go three spots north. If you go down you can go two spots north. I want to see the relationship between those two spots north (on the 'down' track) and the 2 spots north (on the 'up' track); eg - they should be 'above' and 'below' themselves. The extra spot north (on the 'up' track) should understand that nothing is 'below' it.
So, any ideas on how this could be done? Any good books on graph theory to talk me outta attempting this?

I'm replying to myself!

[FortKnox]

I just thought of something.

What seems most intelligent to use (to me) would be a 3D array structure. That way, I can just use the numbers to my advantage (if something exists in the say X,Y, but has a different Z, its just up/down level different, etc...). But, in java, you can't resize arrays, so I could fall into trouble.
Instead, I should apply an x,y,z coordinate to the area. That way, I just have to check the coordinates against one another.

In fact, I don't need to assemble the structure into a

Re:I'm replying to myself!

[dthable]

True, but why use a single array? You could give each object it's own position vector. The only problem with that is finding relationships becomes an O(n^n) operation. Of course, creating a hashmap to represent the 2D representation would limit the number of nodes to walk with the 3D algo.

Java Arrays

[baldass_newbie]

I know you can't resize arrays in Java, however, there are methods to create a new duplicate array and move over to the newer one, replace the old and move back.
Arggh. Can't think of the book right now, I think it's Core Java Fundamentals Vol. I has an actual example of this in like Chapter II.
Doesn't help with your representation, though.
Sorry.

The best graph algorithms book out there

[AntiFreeze]

Algorithms in C++ Part 5 : Graph Algorithms, Vol. 5 [barnesandnoble.com] by Robert Sedgewick. Sedgewick was a student of Knuth, and is now (I believe) a Professor at Princeton.

He's rewritten Parts 1-4 as an Algorithms in Java [barnesandnoble.com] book, I'm assuming part 5 will come out as a Java book soon as welll.

I'm sick now, and don't have the brain power to look over your problem, but if I think of anything I'll be sure to post it.

Good luck.

Just a thought

[Keith Russell]

What about a BSP tree? Your description reminded me of visibility calculations in Doom.

(Disclaimer: My graph theory muscles have atrophied from disuse since college.)

More details?

[MarkusQ]

There are any number of potential solutions, but it's hard to say which is best from your description. So, a few questions:

• When you say "are attached at any 4 points (think north, south, east, west, up, and down. " did you mean that there are six types of connections, comprising three pairs of opposites, or did you mean to say just north, south, east, west, or did you mean that each node can only have four neighbors, in any of six directions, or...?
• When you say you can go "three spots north" from a nod