Highlighting Shortest Path?

[Sean]

Greetings.

First of all, a big THANK YOU!! to the creators of JUNG, I'm doing a masters project in university and JUNG has knocked a significant amount of time from some software development that is part of it. You rock!

I do have a question though, my apologies if it's been covered somewhere else.

My project requires me to provide a software solution to a generic problem of shortest distance (in time) between two things, and though JUNG has effectively done that for me with its implementation of Dijkstra's algorithm, the program also displays a graph and I need to highlight the shortest path on it, preferably by changing the colors of nodes (vertices) and arcs (edges) on the path.

There is a demonstration of that here: http://jung.sourceforge.net/applet/shortestpath.html

But I can't find the code anywhere.

Thanks in advance for any assistance.
- Sean

[Sean]

If it helps any, I am using a DirectedSparseMultigraph with an FRLayout.

[Joshua O'Madadhain]

Glad you've found JUNG to be useful.  :)

The source code for all of the demos is in the (source) distribution.

Joshua

[Sean]

Thanks for the reply,

Unfortunately, I've been less than successful at emulating it in my program, primarily because I don't really know what I'm doing WRT jung, and also because I had already built substantial amounts of custom code derived from Greg's Jung2 tutorial: http://www.grotto-networking.com/JUNG/JUNG2-Tutorial.pdf

I was wondering if someone could give me the idiots guide to the code in ShortestPathDemo.java, a walkthrough if you will, so that I can have a hope of figuring out how it works.

The 2nd problem is that of the data structures in my existing code - I have customised Node and Vertex classes and the my graph is a DirectedSparseMultigaph, while the code in the demo seems to expect a HyperGraph.
I also already have a shortest path algorithm in there, a DijkstraShortestPath algorithm thing again copied from the tutorial.

Here's my custom vertex/edge class code:

class MyNode
{
    int id;
    String jobname;
    public MyNode(int id, String title)
    {
        this.id = id;
        this.jobname = title;
    }
    public String toString()
    {
        return jobname;
    }        
}
class MyLink {
    double capacity;
    double weight;
    static int ids = 0;
    String name;
    int id;
    
    public MyLink(double weight, double capacity, String name) {
        ids++;
        this.id = ids; //Not much use
        this.weight = weight;
        this.capacity = capacity; //Not used
        this.name = name; //Main edge identification and most heavily used.
    } 
    public String toString() {
        //return "E"+id;
        return name;
    }

[Sean]

(Can't edit my last post but) MyLink.weight is the basis for Dijkstra shortest path calculations in my existing code.

[Joshua O'Madadhain]

Sean:

All Graphs are Hypergraphs.  Take a look at the class hierarchy.

I'm not sure what problems you're actually having. 

If the tutorial, Javadoc, and sample code aren't enough, I'm afraid that I personally don't have time to walk you through it.  You might look at some of the other demos to see if you can distinguish some patterns.

Good luck!

Joshua

[Sean]

Fair enough, I'll try to figure it out some more.