Simple optimal route application

[PhuNguyen3]

I want to code a simple application using java that read data from street shapefile, calculate the shortest path between two vertices using an algorithm and display the route in MapBean of my app. What is want is a custom and simple route solver, for algorithm demo purpose only.

It might be simple task but the problem is that I am new with ArcGIS, and new with geographic field too. So I found many difficults in implementing the demo. I think the trouble is how to determine the adjacent edges of a vertex in the network. Is there any kind of junction connectivity table stored in shapefile  and how to read these data, using java.

Any help would be greatly appreciated !

[JaySandhu]

A road dataset such as in shapefile format does not store any adjaceny (network topology information) with it. In fact there are no junctions. A road line feature class contains only roads. The actual road topology needs to be built from a set of rules that govern how roads connect, model bridge, tunnels, turn restrictions, etc. This is what the Network Analyst provides. It contains ways to make a network dataset from input line feature classes. The network dataset contains junctions and connectivity information and that can be queried. Network Analyst also provides the shortest path solver. So is your goal to write the shortest path solver or use an existing one?

Jay Sandhu

[PhuNguyen3]

Thanks for your reply !

Actually, i want to write a new shortest path solver that used an algorithm like A* algorithm. So what I need is the connectivity information of the network, like knowing adjacent vertices of a junction. Do you mean the dataset that I used must contain those information in its attribute table ?

I take a look at sample data for network analyst in my ArcGIS dir, it contains road feature class and junction feature class, but in the attribute table of street junction, there is only FID, Shapefile and ZELEV, no information about connectivities. So, how the shortest path solver of NetworkAnalyst obtain those information?

Sorry for my bad English.

[JaySandhu]

The first part of using a shapefile for routing is to create the connectivity graph. As I explained in my previous post, first part is to create a network dataset that goes along with the shape file and then you can use that to query the adjacencies and write your own algorithm.

Here is how you can create the network dataset:
http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Creating_a_network_dataset/00470000000...

If you have seen the network sample data and you see shapefiles for streets and junctions then there will also be another folder with a .ND extension that contains the adjaceny information in a binary format.

You can take a look at the INetworkJunction object in this sample:
http://help.arcgis.com/en/sdk/10.0/java_ao_adf/conceptualhelp/engine/index.html#//0001000004t0000000

Basically once you have a networkjunction then you can call its QueryEdge method to find the adjacengt edges.
Some more help here:

http://help.arcgis.com/en/sdk/10.0/java_ao_adf/api/arcobjects/com/esri/arcgis/geodatabase/inetworkju...

Jay Sandhu

[PhuNguyen3]

Thank you Jay !

This field is really new to me and I've got stuck by this problem for some days. Thanks alot for your help.:D

Phu Nguyen.

[PatrickStevens]

Just to further the help that Jay has already given...

There are a couple of resources to help you code a custom solver.  Using .NET, there is some code that uses our API to create a breadth-first solver algorithm here.

There is also a custom solver written in C++ that helps determine connectivity within a network here.

There is always the chance, too, that we provide the functionality that you are looking for, without the use of a custom solver.  Are you writing one for the experience?  Or are there specific capabilities that we don't provide yet?

[PhuNguyen3]

Hi Patrick,

This product is great. I just want to write a piece of code to get optimal path bw 2 points in the network using a kind of heuristic algorithm. Its for my project in the university.

I have one more question. How to get the distance between two junctions in a street network in meter. I've tried several ways but all of them give the same result as using Pythagorean theorem for x, y coordinates of the two Point. This result make no sense when compare with the result from Measure tool in ArcMap. Is there any thing that need to be converted or processed before we can get real distance ? (I want to get the distance using java).

Thanks in advance for your help!

[PatrickStevens]

Thanks for your kind words.

As to your questions, what network are you using?  Does it have a length cost attribute?  If so, you can query each edge directly to find out what its cost is using AttributeValueByName.  To do this programmatically, follow these steps:

Create a edge using INetworkQuery.CreateNetworkElement.
Populate the edge your are interested in using its EID in INetworkQuery.QueryEdge.
Then call AttributeValueByName, passing in the name of the length attribute.

If the length attribute on your network is not in the right units, and your network is not readonly, you can change the units to the ones you desire.  If you network is read-only, then you'll need to do some manual conversion.

[PatrickStevens]

Sorry, I misunderstood your last post.  You are looking for distance estimates to use as input to your A* algorithm?

I'm not sure exactly how the measure tool works, but perhaps the results from there are using geodesic distance around the globe, rather than true straight lines from your pythagorean estimates.  That could explain the discrepancy.

[MichaelRice]

If you just wish to get a straight-line Euclidean distance between two junctions in your street network, then using the Pythagorean theorem for your x/y coordinates is fine. However, keep in mind that the x/y coordinates you are using are based on the dataset's associated coordinate system. Therefore, any "distances" you get from using these coordinates will be based on the units of the coordinate system (which may explain why your values are different than what you are seeing from the measure tool).

In order to obtain useful distance values using this approach without having to do more complex calculations, I would suggest that you make sure that your dataset is in a projected coordinate system (PCS). You can then figure out the distance-measure-of-choice per unit in your PCS, based on your desired distance measure (e.g., you can determine "meters per unit", "miles per unit", etc.).

You can then translate the length of the hypotenuse into the appropriate distance measure using this value. However, you should also make sure that any length attribute you are using in the network dataset for your solves is also based on the same unit of measure, for consistency. Additionally, if your impedance attribute is time-based and not length-based, then you would have to further translate this distance into a valid time estimate instead (e.g., using a maximum expected speed limit).

Does this make sense? Please let us know if you have any further questions.