Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Developers! Developers! Developers!

FortKnox (169099) writes | more than 10 years ago

Programming 6

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?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?

cancel ×

6 comments

Sorry! There are no comments related to the filter you selected.

I'm replying to myself! (1)

FortKnox (169099) | more than 10 years ago | (#5565949)

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 graph at all. I just need to apply the coordinates to the object, itself.

Thoughts?

Re:I'm replying to myself! (1)

dthable (163749) | more than 10 years ago | (#5566269)

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 (1)

baldass_newbie (136609) | more than 10 years ago | (#5568631)

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 (1)

AntiFreeze (31247) | more than 10 years ago | (#5566064)

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 (1)

Keith Russell (4440) | more than 11 years ago | (#5571849)

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? (1)

MarkusQ (450076) | more than 11 years ago | (#5577130)


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 node, are the three spots sequential (so that you have one neighbor to the north, which itself has one neighbor to the north, etc.) or do you mean that the spot in question has three (unordered) neighbors to the north?
  • Are the relationships given, and if so, how? If they are computed or assigned by your process, what is the basis for the assignment? It may be that the information you want could be independently derived from the source data.
  • What information do you want?
  • How large is your dataset? Solutions that work fine on small problems may take eons on larger datasets, where as a solution that scales well may be overkill if you are only going to be dealing with a small amount of data (why implement a fancy sort if all you want to do is determine which of three numbers is the largest).
  • What sort of constraints does your program face? Are you more worried about run time, coding time, maintenance time, or...?
One way to answer these questions might be to give more details about your specific problem. Another way might be to sketch out an API that would solve your problem, if you had a way to implement it.

-- MarkusQ

P.S. If you really want to talk graph theory, ./ user "heliocentric" (IIRC) would be a good person to ask.

Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>