doesn NTS implement the short path algorithm

Topics: General Topics, SharpMap v0.9 / v1.x, SharpMap v2.0, Web Controls, WinForms Controls
Sep 5, 2007 at 7:50 AM
who can tell me ?
or i must do it myself ?
Coordinator
Sep 6, 2007 at 9:00 PM
It doesn't appear to. However, I'd use QuickGraph to implement it. Find it here: http://www.codeplex.com/quickgraph.

I can imagine taking an NTS geometry graph and creating an adapter to a QuickGraph model, and running a shortest path search on it.

It might be in the future SharpMap will use QuickGraph, but it's too far out to say for certain. For example, I can see a custom renderer which converts geometry instances into blocks and routed lines - doing algorithmic layout instead of an affine layout - so that conceptual maps can be generated instead of conformal maps. Perhaps your experiences will influence this direction.
Sep 7, 2007 at 6:23 AM
thanks to give QuickGraph project to me.

but if SharpMap and NTS do not use QuickGraph, How to use QuickGraph to do the shortest path algorithm in my shapefile ?

by the way, how to get and store the weight of city roads. Should i calculate all the distance of roads ?
Coordinator
Sep 7, 2007 at 7:54 AM
You'd have to code an adapter from a SharpMap/NTS geometry to a graph structure in order to run the algorithm on it. It probably wouldn't be too hard. I'd love to look into it and come up with an example, but I have to spend all my time on SharpMap v2.0 right now (since I need it to do some mapping for me!).

As for the weight of the roads (I'm assuming you are talking about route weighting in order to influence the path-finding algorithm), you'd have to base it on some attribute data, I suppose. That would be the only way, unless your roads are stored as polygons and have a width which you could compute and use (though that would probably be quite inaccurate).
Sep 10, 2007 at 2:41 AM
code an adapter ? I don't understand the structure of quickgraph. So it probably will be a little hard, and spend much time on it . can you give me a enlightenment ? thanks...

the shapefile attribute do not have weight data. if i want to use the distance of road as weight then store in attribute data. should i write an segment code to write these data to attribute ? any example ?

on the other hand, I'm glad to hear that you have concentrated on SharpMap v2.0. I hope v2.0 releases as early as possible. :-)
Developer
Sep 11, 2007 at 7:48 AM
Edited Sep 11, 2007 at 7:52 AM
Im working in a GIS company. My work is belong to routing team, we use open source to deverlope App and web app. If u have a shapefile database why do u not import it into PostGres+PostGIS data base, u can use pgrouting in PostGIS to find shortest path or some algorithm about path in pgrouting. It is open source.
Hope to u.
Coordinator
Sep 11, 2007 at 8:50 AM
Thanks trieuvy for the insight. It sounds like that could be a good way to go.

For sake of wrapping up the QuickGraph route, I found a small example on running a shortest path on the QuickGraph wiki. The idea would be to create some instance of IVertexListGraph<int,Edge<T>> where T is your feature ID (uint for shapefiles). You'd need to come up with some kind of vertexes to measure between, since measuring between road endpoints wouldn't be too useful, I imagine. These vertexes could come from a point layer of, say, addresses. You'd put the point data into the IVertexListGraph and you'd measure distances between adjacent points on a street and put these into the IDictionary. You'd have to put all street intersections into the graph, too, in order to compute turns. It would take some geoprocessing to get these points, but this could be done with NTS. All in all, it would be more challenging than I initially thought, but doable in a relatively straightforward manner.

trieuvy's suggestion sounds even easier, though.
Developer
Sep 11, 2007 at 9:21 AM
If open source is hard for you about time and sometime is not the same your think. You can create a structure graph on any database:
-one id of record in database of streets table represent: edge
-a colume length: weight of edge ( can use length of street).
-Add into database a colume is like 'soure' (interger) represent: vertex
( -there are a colume : 'target' (interger) is vertex adjacent with edge)
by this way, you can read data base and code shortest path algorithm by yourself.
Coordinator
Sep 11, 2007 at 10:40 AM
trieuvy -

This is pretty much the same scenario I was describing, although I was going further and examining the use of QuickGraph to build the graph from the data. Take a look at the QuickGraph link above - it's pretty clear. It wouldn't matter if vertex information came from memory or from a database. Either way, you'd have to compute intersection points, otherwise you wouldn't get correct routing. The scenario you describe would take someone from the beginning to the end of one street only (or, if the street is stored in segments, which streets often are, from segment to segment, beginning to end). What if the destination was around the corner?
Developer
Sep 13, 2007 at 5:52 AM
Edited Sep 13, 2007 at 7:23 AM
codekaizen!
Yes, streets is saved in database(db) by segments,it is truth in present db. Around or straight segment is not important with above structure(Around segment is like a around edge on graph) . Each segment of streets ( record in db) is a edge link to 2 vertex is point beginning and the end of segment, is represented by the interger number( source and target) . it like to structure a graph G(v,e).
Coordinator
Sep 15, 2007 at 12:51 AM
Ah, I see, you already have a segmented set of data. Well, then, the hard part is done. ;)

Most street data I've come across would need to be geo-processed in order to segment it.

Once that is done, you're correct, running a shortest path algorithm over it would be fairly straighforward. If I were to do it, I'd use QuickGraph, since they have a couple of algorithms to use already, and it's based on the Boost Graph Library which has a fairly popular design, reducing some learning curve.
Developer
Sep 15, 2007 at 4:59 AM
Edited Sep 15, 2007 at 5:05 AM
OK. Your scenario is useful and esealy in case that i want find shortest path on map of Pocket PC, database in poketPC can't use PostgresSQL or MS SQL,....Shapefile is a good db at here. NTS is also a good geoprocessing tools.I can develope map on mobile in next time.
If whos ask me: How to find shortest path on map. I can give a specific intruction.,But I lack experience in QuickGraph.
By your describe:
"I found a small example on running a shortest path on the QuickGraph wiki. The idea would be to create some instance of IVertexListGraph<int,Edge<T>> where T is your feature ID (uint for shapefiles). You'd need to come up with some kind of vertexes to measure between, since measuring between road endpoints wouldn't be too useful, I imagine. These vertexes could come from a point layer of, say, addresses. You'd put the point data into the IVertexListGraph and you'd measure distances between adjacent points on a street and put these into the IDictionary"
if database very large. Algorithm( adapter to chose vertex and weight to insert into IvertexListGrap<int,Edge<T>> and IDictionary) is slow, and it seem only feasible on paper, i though.

May 30, 2008 at 1:53 PM
Ey!

I'm interested to do this. Do you do something on that?

I'm going to learn QuickGraph.


Thanks!