RoadGraph

RoadGraph

Java open source code to find paths across a road network.

  • Language: Java
  • Released: Apr 27, 2011
    Last Update: Apr 30, 2014

RoadGraph finds the shortest paths across a road network. Works in up to 3 dimensions. Provides the shortest path as a series of points, along with its length. Originally used with very large networks and many requests for long paths. Built for speed. Does not (yet) handle different types of roads or discontinuities such as worm holes and portals.

RoadGraph is multithreaded--completely thread-safe--allowing the road network to be modified from multiple threads while paths are calculated by many more threads, all with almost no blocking. It is fully Javadoc'ed. It includes ConcreteSet, which is also available independently. Can be combined with ObjectPlot (available separately) to speed locating the closest road segment.

The source code includes a simple (single threaded, 2D) example program.

Hide

Usage Example

package rrc12;
import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.util.*;
import javax.swing.*;
import rrc12.util.*;
import rrc12.util.roadgraph.*;

/** An example of the use of RoadGraph.  RoadGraph is actually intended
 * for much larger road networks with much more traffic.  The network
 * can be updated from several threads simultaneously while a thousand
 * other threads are plotting paths.
 *  This is all done in 2D.  3D for paths between stars or mountainous
 * terrain also works. */
public class RoadExample  extends JFrame  {
    private static final Color  BROWN = new Color( 64, 32, 0 );
    private static final Color  GREEN = new Color( 96, 255, 64 );
    /** Points in the road network. */
    private static final Location[]  crossRoads = new Location[]  {
            new Location(  5,  5, 0 ), new Location( 15, 15, 0 ),   //  0
            new Location(  5, 35, 0 ), new Location( 15, 45, 0 ),   //  2
            new Location(  5, 65, 0 ), new Location( 25, 55, 0 ),   //  4
            new Location( 15, 85, 0 ), new Location( 35, 85, 0 ),   //  6
            new Location( 45, 75, 0 ), new Location( 65, 75, 0 ),   //  8
            new Location( 75, 85, 0 ), new Location( 85, 65, 0 ),   // 10
            new Location( 75, 45, 0 ), new Location( 55, 45, 0 ),   // 12
            new Location( 35, 45, 0 ), new Location( 85, 35, 0 ),   // 14
            new Location( 75, 25, 0 ), new Location( 55, 25, 0 ),   // 16
            new Location( 55,  5, 0 ), new Location( 35, 15, 0 )    // 18
    };
    /** The actual road network. */
    private static final  LineSegLoc[]  roads = new LineSegLoc[]  {
        new LineSegLoc( crossRoads[18], crossRoads[19] ),     //  0
        new LineSegLoc( crossRoads[ 0], crossRoads[ 1] ),     //  1
        new LineSegLoc( crossRoads[ 0], crossRoads[ 2] ),     //  2
        new LineSegLoc( crossRoads[ 1], crossRoads[ 2] ),     //  3
        new LineSegLoc( crossRoads[ 2], crossRoads[19] ),     //  4
        new LineSegLoc( crossRoads[ 1], crossRoads[19] ),     //  5
        new LineSegLoc( crossRoads[ 2], crossRoads[ 3] ),     //  6
        new LineSegLoc( crossRoads[ 3], crossRoads[ 4] ),     //  7
        new LineSegLoc( crossRoads[ 3], crossRoads[ 5] ),     //  8
        new LineSegLoc( crossRoads[ 4], crossRoads[ 6] ),     //  9
        new LineSegLoc( crossRoads[ 5], crossRoads[ 6] ),     // 10
        new LineSegLoc( crossRoads[ 5], crossRoads[ 7] ),     // 11
        new LineSegLoc( crossRoads[ 7], crossRoads[ 8] ),     // 12
        new LineSegLoc( crossRoads[ 8], crossRoads[ 9] ),     // 13
        new LineSegLoc( crossRoads[ 8], crossRoads[14] ),     // 14
        new LineSegLoc( crossRoads[ 9], crossRoads[13] ),     // 15
        new LineSegLoc( crossRoads[ 9], crossRoads[10] ),     // 16
        new LineSegLoc( crossRoads[10], crossRoads[11] ),     // 17
        new LineSegLoc( crossRoads[11], crossRoads[15] ),     // 18
        new LineSegLoc( crossRoads[11], crossRoads[12] ),     // 19
        new LineSegLoc( crossRoads[12], crossRoads[13] ),     // 20
        new LineSegLoc( crossRoads[13], crossRoads[17] ),     // 21
        new LineSegLoc( crossRoads[15], crossRoads[16] ),     // 22
        new LineSegLoc( crossRoads[16], crossRoads[18] ),     // 23
        new LineSegLoc( crossRoads[17], crossRoads[18] ),     // 24
        new LineSegLoc( crossRoads[14], crossRoads[19] ),     // 25
        new LineSegLoc( crossRoads[13], crossRoads[17] ),     // 26
        new LineSegLoc( crossRoads[12], crossRoads[16] ),     // 27
        new LineSegLoc( crossRoads[14], crossRoads[17] )      // 28
    };
    /** The RoadGraph. */
    private static RoadGraph  roadNet;

    private MouseListener  mouseListener;
    /** The current path as a set of points. */
    private Collection     roadPath;
    private Location       endLocation;

    /** Creates a RoadExample window and displays it. */
    public static void main(String[] args)  {
        roadNet = new RoadGraph();
        for (int i = 0; i < roads.length; i++)
            roadNet.addEdge( null, roads[i] );
        new RoadExample().setVisible( true );
    }

    /** Creates a new RoadExample window. */
    public RoadExample()  {
        setBounds( 100, 100, 400, 400 );
        setDefaultCloseOperation( EXIT_ON_CLOSE );
        Container  cp = new JPanel()  {
            public void paintComponent( Graphics g )  {
                Graphics2D  g2 = (Graphics2D)  g;
                g.setColor( GREEN );
                g.fillRect( 0, 0, 1000, 1000 );
                BasicStroke  stroke = new BasicStroke( 4.0f,
                            BasicStroke.CAP_ROUND,
                            BasicStroke.JOIN_ROUND );
                Line2D.Double  line = new Line2D.Double();
                g2.setStroke( stroke );
                g.setColor( BROWN );
                for (int i = 0; i < roads.length; i++)  {
                    Location  loc1 = roads[i].location1;
                    Location  loc2 = roads[i].location2;
                    line.setLine( 4 * loc1.x, 4 * loc1.y, 4 * loc2.x,
                                4 * loc2.y );
                    g2.draw( line );
                }
                plotPath:  {
                    if (roadPath == null)  break plotPath;
                    Iterator i = roadPath.iterator();
                    if (!i.hasNext())  break plotPath;
                    Location  loc1 = (Location) i.next();
                    if (!i.hasNext())  break plotPath;
                    stroke = new BasicStroke( 3.0f, BasicStroke.CAP_ROUND,
                                BasicStroke.JOIN_ROUND );
                    g2.setStroke( stroke );
                    g.setColor( Color.YELLOW );
                    for (;;)  {
                        Location  loc2 = (Location) i.next();
                        line.setLine( 4 * loc1.x, 4 * loc1.y, 4 * loc2.x,
                                    4 * loc2.y );
                        g2.draw( line );
                        if (!i.hasNext())  break;
                        loc1 = loc2;
                    }
                }
                g.setColor( Color.BLACK );
                g.drawString( "Click on intersections.", 120, 360 );
            }
        };
        setContentPane( cp );
        mouseListener = new MouseListener()  {
            private boolean  anyClick = false;

            public void mouseClicked( MouseEvent e )  {}
            public void mousePressed( MouseEvent e )  {
                anyClick = false;
                if (e.isConsumed())  return;
                anyClick = true;
                e.consume();
            }
            public void mouseReleased( MouseEvent e )  {
                if (!anyClick)  return;
                anyClick = false;
                int  x = ((((e.getX() + 2) / 4) / 10) * 10) + 5;
                int  y = ((((e.getY() + 2) / 4) / 10) * 10) + 5;
                Location  temp = new Location( x, y, 0 );
                if (endLocation != null)  {
                    RoadPath  npath = roadNet.getNodePath( endLocation,
                                temp, 0, Long.MAX_VALUE );
                    if (npath.getType() == 2)  return;
                    endLocation = temp;
                    roadPath = npath.getPoints();
                    repaint();
                }
                else
                    endLocation = temp;
            }
            public void mouseEntered( MouseEvent e )  {}
            public void mouseExited( MouseEvent e )  { anyClick = false; }
        };
        cp.addMouseListener( mouseListener );
    }
}
Hide

Javadoc for RoadGraph

Javadoc for RoadMap in plain text:

rrc12.util.roadgraph Class RoadGraph

java.lang.Object rrc12.util.roadgraph.RoadGraph

public class RoadGraphextends java.lang.Object

A road network. A network is built up adding roads, or edges via addEdge. Each edge is just a line segment with two end points. When two edges have the same end point, they are considered to be connected there. (Coordinates are rounded to the nearest integer when figuring out if two points are equal. When dealing with points midway between two whole numbers, care should be taken that all coordinates of the point are precisely equal lest they get rounded in different directions.) Edges can be removed using removeEdge(java.lang.Long).

Paths through the road network can be found with getPath and getNodePath, whichever is more convenient.

RoadGraph is intended for multi-threaded use. Multiple threads may add edges, remove edges, and seek paths without need for synchronization.

Method Detail

clear()

public void clear()

Removes all data from this RoadGraph. After this call, it is just like new and can be reused.

addEdge()

public boolean addEdge(java.lang.Long id,
                       Positionposition)

Adds a new edge to this RoadGraph.

Parameters:

  • id - the identifying number for this edge, so it can be identified later. May be null if caller does not need to identify edges.
  • position - the position of this edge on a map of some sort. Only the value is used from the passed object; it retains its independence. The passed object really ought to be a LineSegLoc.

Returns: true if this edge was added, false if it was not because it was already there or because the position was not usable (was not a LineSegLoc, or convertible to one with a non-zero length).

removeEdge()

public void removeEdge(java.lang.Long id)

Removes an edge from this RoadGraph. This method will simply do nothing if the edge does not exist in this RoadGraph.

Parameters:

  • id - the edge object's id number. May be null ( in which case the method will do nothing.)

closestEdge()

public java.lang.Long closestEdge(Location loc)

Returns the identifying number of the added Edge that is closest to the specified location. May return null in odd cases.

getPath()

public RoadPath getPath(java.lang.Long firstEdge,
                        Location firstLoc,
                        java.lang.Long lastEdge,
                        Location lastLoc,
                        double minDistance,
                        double maxDistance)

Sets up a path between two locations and two specified edges.

Parameters:

  • firstEdge - the nearest edge to the first location. One of its endpoints will serve as an entry to the road graph from firstLoc.
  • firstLoc - the location at which the path should start. Ideally it should be somewhere on firstEdge, but this is not necessary.
  • lastEdge - the nearest edge to the last location. One of its endpoints will serve as the path point before lastLoc.
  • lastLoc - the location at which the path should end. Ideally it should be somewhere on lastEdge, but this is not necessary.
  • minDistance - the shortest the path needs to be. Once a path this short or shorter is found, it is the one kept. It may or may not be the shortest path. To get the shortest path, set this value to 0.0. Used to minimize effort.
  • maxDistance - the longest path we are interested in. Anything longer would be the same as no connecting path at all. To get a path no matter how long it needs to be, set this value to something like Long.MAX_VALUE. Used to minimize effort.

Returns: the path.

getNodePath()

public RoadPath getNodePath(Location firstLoc,
                            Location lastLoc,
                            double minDistance,
                            double maxDistance)

Sets up a path between two locations based on two existing nodes. Note that if either of the locations is not at a node, the method returns an empty path (RoadPath.pathType returns 2).

Parameters:

  • firstLoc - the location at which the path should start. Must be a node, or method will return an empty path.
  • lastLoc - the location at which the path should end. Must be a node, or method will return an empty path.
  • minDistance - the shortest the path needs to be. Once a path this short or shorter is found, it is the one kept. It may or may not be the shortest path. To get the shortest path, set this value to 0.0. Used to minimize effort.
  • maxDistance - the longest path we are interested in. Anything longer would be the same as no connecting path at all. To get a path no matter how long it needs to be, set this value to something like Long.MAX_VALUE. Used to minimize effort.

Returns: the path.

You need to log-in or create an account
  • Create an account
  • Log-in
Please use your real name.
Activation link will be sent to this address.
Minimum 8 characters
Enter your password again

Clicking this button confirms you read and agreed to the terms of use and privacy policy.

X

Save your watchlist

Fill your details below to receive project updates from your watch list - including new versions, price changes and discounts.

I agree to the terms of use and privacy policy.

2 licenses, starting from From » FREE 14 day money-back guarantee View Licenses
or Get a quote

for customization or integration services

Post a comment

Or enter your name and Email
No comments have been posted yet.