tree maps in JUNG (for a shortest path algorithm)

Question

After asking some general advice on shortest path algorithms (2D waypoint pathfinding: combinations of WPs to go from curLocation to targetLocation) and then asking about a more specific implementation (Shortest path algorithm (eg. Dijkstra's) for 500+ waypoints/nodes?) I have decided to use the JUNG library (http://jung.sf.net/).

My goal is now to get the shortest path from point A to point B by using any combination of points from a list of points (size ~1000) where each point is directly connected to all points that are within x distance.

For this, I need to setup a tree map. I believe that this is a list of tree map implementations: http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/class-use/Hypergraph.html#edu.uci.ics.jung.algorithms.shortestpath

Is that correct? Now, all these implementations limit themselves to sparse tree maps, yet I have to create a rather dense tree map.

So, what tree map should I use in JUNG to accomplish my goal?

Answer 1

I think your main goal is achievable with JUNG but IMHO, you need to filter for your given "x" distance (I mean all possible node-to-node combinations). However, I have no experience in using JUNG's shortest path algorithms except in the example it gives below.

JUNG Framework 2.x GUI example uses a shortest-path algorithm from BFSDistanceLabeler that requires a generic Hypergraph. It applies a BFS distance-based calculation rather than edge weight-based distance calculation. It is a Breadth-first search (BFS) algorithm, though.

You can refer to the source code ShortestPathDemo.class under package edu.uci.ics.jung.samples in jung-samples-2.0.1.jar

The best reference I can find for other JUNG's shortest path algorithms can be found here (PDF): www.grotto-networking.com/JUNG/JUNG2-Tutorial.pdf