Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Undirected Weighted Graphs

by OverlordQ (Hermit)
on Apr 07, 2009 at 05:02 UTC ( [id://755922] : perlquestion . print w/replies, xml ) Need Help??

OverlordQ has asked for the wisdom of the Perl Monks concerning the following question:

Imperial Crossroads	#Gate 1
Great Pillars		#Zone
Octavius		#Faction
Great Pillars		#Zone
Great Pillars Station	#Gate 2
13282			#Distance from Gate 1 to Gate 2 in Zone
Dark Fork		#G1
Imperial Crossroads	#Zone
Octavius		#Faction
Imperial Crossroads	#Zone
Great Pillars		#G2
32660			...
Distance between Imperial Crossroads in Great Pillars and Great Pillars in Imperial Crossroads is 0 (Wormhole,Jumpgate,Magic,etc).

Eventual target is to create a weighted undirected graph for creation and application of shortest path algorithm on an undirected graph.

Are there any suggestions on a temporary storage structure or just read/slurp and shove it into Graph as it gets the data?

The idea I envisioned would it would create nodes based on a concatenation of Zone and Gate so as to handle the zero distance condition I mentioned above as then all combinations of FooBar and BarFoo would have a distance of zero.

Or would you suggest a different module/idea all together?

Replies are listed 'Best First'.
Re: Undirected Weighted Graphs
by Corion (Patriarch) on Apr 07, 2009 at 10:19 UTC

    I'm currently implementing such an undirected graph. I haven't gone towards adding weights to the connections, but my approach so far has been to have the gates as "places" in the current zone, with a distance between the current player position and the gate. Each gate connects to its own arrival place in another zone. These connections can have zero or a minimal weight, and should work well enough with A* once I get to add routing through the mesh.

    I'm not sure if having two unidirectional connections instead of one bidirectional connection adds problems further down the path. So far, I haven't found any problem with this approach and for me it makes things like zone wide events easier, as these events can be tied to the arrival place.

      That sounds almost exactly what I'm looking at. Each zone has a series of jumpgates in 3D space that link to another jumpgate in another zone. On first glance you'd think that you'd just represent each zone as a node in the graph but then you'd come to realize there's no way to calculate the non-zero distance between gates in the same zone.

      You doing yours for a game of sorts or something completely different.

        Well, it's a "game", except that it's a game framework that I've implemented in several incarnations already. This time it is to familiarize myself with Moose. As I know how I've implemented the graph in the past, I know that the differences/problems I encounter this time are most likely caused by Moose or my lack of understanding of Moose.

Re: Undirected Weighted Graphs
by dHarry (Abbot) on Apr 07, 2009 at 09:38 UTC

    Take a look at the Graph modules. Chances are you're reinventing wheels;)

    Oops, missed that you already knew about Graph. It is definitely the place to look. Even if it does fully not solve your problem, you will have useful building blocks, i.e. data structures, common algorithms etc.