2

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?

Community
  • 1
  • 1
Tom
  • 8,536
  • 31
  • 133
  • 232

1 Answers1

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

eee
  • 1,043
  • 7
  • 5
  • Sorry if I am missing something but how does this answer what JUNG tree map implementation is applicable for dense rather than sparse tree maps? – Tom Mar 10 '11 at 12:57
  • A list of point about 1000 nodes is not an issue in JUNG as long as the hardware and the JVM are capable to handle the size. I do notice this constraint in my JUNG implementations. Why a tree when you can use a graph considering that your intention is for 2-D waypoint data? You can specify your own data types in JUNG generic Graph, Hyper-graph or Tree class. Though, it has a limited support for trees ((directed, rooted) tree) which I haven't tried. See JUNG FAQ if you haven't: http://jung.sourceforge.net/faq.html – eee Mar 11 '11 at 02:12
  • I thought a graph is a tree. But you're right it's a 2D environment. I looked at this sample before, but it really doesn't make much sense to me. For example, where do they actually construct and populate the graph? If you could give a small example in code here for a non-gui shortest path implementation in jung that'd be great. – Tom Mar 11 '11 at 10:43