tags:

views:

48

answers:

1

I have done some in 3D computer graphics but am somewhat new to graph theory. In particular I have been looking at and trying to solve my problem using a depth first search (DFS) as described in Mastering Algors w/ Perl (Jarkko Hietaniemi). So far I have not been able to get it :-( but I am pretty-sure a DFS is what I want.

It does not have to be in Perl (just trying to learn the language), but Java or C++ would be good.

I have 53 position vectors, ie (x,y,z), which I represent as (x1,y1,z1) (x2,y2,z2) . . . (x53,y53,z53)

I then run a Perl program that I wrote to generate random links between nodes, assigning some max no. of hops, say 6. So the topology may look like this 5 <-- node 1 has 5 links to 18 4 23 6 48, <-- node 18, node 4, node 23, node 6, node 48 2 <-- node 2 has 2 links to 14 5, <-- node 14, node 5 0 <-- node 3 is a leaf since it has no links . . . 2 <-- node 18 has 2 links to 3 17 <-- node 3, node 17
. . . 4 <-- node 53 has 4 links to 10 46 49 22 <-- node 10, node 46, node 49, node 22

I would like to determine the path "run" till I hit a sink, ie a 0. e.g. node 1 to node 18 to node 3, ... This path is completed already. . . .

I think I want DFS; it seems like a recursive exercise.

If someone understands and could give me code, that would be great. I am not a student but am 51! Maybe that has something to do with me not getting this :-)

Thank you for your time.

Andrew M. Neiderer US Army Research Laboratory

BTW I am a computer graphics programmer who has done much in X3D. Maybe I could repay one by returning help in this.

A: 

I looked at my q and for some reason (probably me :-( it was "garbled"

Topology should look like 5 <-- node 1 has 5 links; 18 4 23 6 48 <-- node 18, node 4, node 23, node 6, node 48 2 <-- node 2 has 2 links; 14 5, <-- node 14, node 5 0 <-- node 3 is a leaf since it has no links . . . 2 <-- node 18 has 2 links; 3 17 <-- node 3, node 17 . . . 4 <-- node 53 has 4 links; 10 46 49 22 <-- node 10, node 46, node 49, node 22

Just want to be clear in case someone can provide code (Perl, Java, c++/C ...)

Thanks.

You should modify your question instead of providing an answer as a clarification.
Adrian Regan