<div dir="ltr"><div><div><div>Thanks Steve for clearly mentioning the two proposals. <br><br></div>For Item 1 , upgrading all the algorithms will certainly require a lot of work and since i will be having my summer vacation i don't have any issue with it :).<br>
<br><br></div>For item 2 , i am looking into the idea that you have proposed , It is very much doable , there are however some concerns of mine like <br><br></div><div>- how do we decide what should be the grid size . this can vary for suburban area and urban area based on netwrok density.<br>
</div><div>- how do we classify the nodes lying on the junction of two or more grids . should it be assigned to all the grids??<br></div><div>- how do we decide the grid that needs to be loaded in the memory , connectivity with the previous grid seems legit here but i guess we need to discuss some corner cases too.<br>
<br><br></div><div>Thanks.<br></div><div><br></div> <br></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Apr 13, 2013 at 6:20 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On 4/11/2013 3:24 PM, Mukul priya wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Steve and Daniel,<br>
<br>
<br>
You suggested extending the present algorithms such that its<br>
input can take more points and not only the source and destination . i<br>
think this can be implemented and i will soon come up with<br>
implementation details( kind of more technical ) .<br>
<br>
Can you be a liitle bit more elaborate about partioning data<br>
into spatial chunks or even suggest some readings . I can then come up<br>
with some better ideas about implementing it.<br>
</blockquote>
<br></div>
This is just me thinking out loud :)<br>
<br>
Lets say we construct a grid of one degree squares, you can visualize it by drawing a grid over your map.<br>
<br>
Then you can associate all the nodes with the grid they fall in. We might also need to associate edges to the grids also and an edge the crosses over a grid boundary might need to be associated with two grids. This could be done with some simple relational tables like:<br>
<br>
node_id|grid_id or edge_d|grid_id<br>
<br>
So my idea would be to do the routing like this:<br>
<br>
1. get the start node or edge<br>
2. build the graph based on loading the items in the related grid<br>
3. mark the boundary nodes (we might want to do this when we grid them)<br>
4. run the algorithm until we find the target node or hit a boundary node<br>
5. on hitting a boundary:<br>
a. we check if the connected grid is loaded and continue if it is<br>
b. or we extent the graph with the new grid<br>
6. continue with the routing<br>
<br>
We might want to be able to dynamically change the size of the grid cell based on the number of items in it. This would give us better performance when transitioning from rural areas into urban areas where there is a greater density of road segments. Think of a quadtree where we split it based on number of entities.<div class="im">
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Daniel , i took a look at the oracle link that you provided but<br>
there was no details about how it has been implemented , it was more<br>
about how one can use it. May be a bit more search and luck might<br>
take me to its implementation document :) .<br>
</blockquote>
<br></div>
Right, it is useful if you look at the documentation and ask why did they do it that way and what does it imply about how it works behind the scenes.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
The other thing that you mentioned was about contraction<br>
Hierarchy . Still the nodes have to be ordered based on some criteria or<br>
according to their importance . We can use natural hierarchy present in<br>
the network for doing that .<br>
</blockquote>
<br></div>
This is not related to what you proposed. It is an algorithm that does a lot of precompuation, that is LOTS in capitals, but it can get results in milliseconds for cross country routes.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
i will be really grateful if anyone can correct me in case if<br>
my thought process in not on the right lane and sorry for the late reply<br>
as my academic session is in progress too .Meanwhile i am trying to<br>
get fluent with git ,cmake and other tools.<br>
</blockquote>
<br></div>
So read over our wiki:<br>
<br>
<a href="https://github.com/pgRouting/pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>pgrouting/wiki</a><br>
<br>
The way I see it at the moment there are two unrelated proposals on the table (I'm leaving out the contraction hierarchy):<br>
<br>
1. multi point routing<br>
2. partition JIT graph building while routing<br>
<br>
Item 1 is fairly trivial technically, I think, but if you were to upgrade all the algorithms to do this it would be a lot of work and a useful contribution to pgrouting.<br>
<br>
Item 2 is more of a design and code a new algorithm and you would probably want to focus on using astar or trsp algorithm to do this with. This one is more technically challenging and has more unknowns in it but I think it should be doable.<br>
<br>
If you are interested in reading about contraction hierarchies:<br>
<a href="https://www.google.com/#q=contraction" target="_blank">https://www.google.com/#q=<u></u>contraction</a> hierarchies<br>
<br>
Thanks,<br>
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
Thanks .<br>
<br>
Mukul<br>
<br>
<br>
<br>
<br>
On Thu, Apr 11, 2013 at 6:47 PM, Stephen Woodbridge<br></div><div><div class="h5">
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>> wrote:<br>
<br>
With pgRouting, we do most things dynamically, here is the basic flow:<br>
<br>
1. Given a collection of input, points, nodes, or edges<br>
map these to nodes or edges depending on algorithm.<br>
<br>
2. Select the edges we need to build the graph<br>
<br>
3. build the graph and solve it<br>
<br>
4. return the results<br>
<br>
All our algorithms today only take start and end points. They could<br>
be extended to take points. Each "point" (I use "point" as a generic<br>
term because it might be a lat/lon, node id, edge id and offset,<br>
etc) would need to be mapped to the appropriate input need for any<br>
given algorithm.<br>
<br>
So for node based algorithms like Dijkstra,and astar it would get<br>
resolved to a node. For TRSP it would get mapped to the nearest edge<br>
and offset along that edge. Postgis has lots of handy tools for<br>
doing this.<br>
<br>
-Steve<br>
<br>
<br>
On 4/10/2013 10:50 PM, Mukul priya wrote:<br>
<br>
Thanks for the reply steve . i have already cloned the github<br>
repository<br>
and looking into various aspects of it .<br>
<br>
For IRNN querry implementation i think it is a good idea to sub<br>
divide<br>
the whole route and generate n+1 routes separately , say from S<br>
to F1 ,<br>
F1-F2 ,..... F(n-1)-Fn , Fn to D . i wanted to know if we have<br>
that kind<br>
of a data where each and every facility is mentioned on the map as a<br>
point (node ) . even if it is not directly connected to the road<br>
network<br>
we can basically treat it a pseudo node and then call the router<br>
. The<br>
other thing about optimization yes we can do that using spatial<br>
range<br>
querries suppose there are several instances of the same<br>
facility that a<br>
user wants to access then we can use spatial range querries to<br>
locate<br>
that facility which is the nearest.<br>
<br>
<br>
On Thu, Apr 11, 2013 at 1:42 AM, Stephen Woodbridge<br>
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>><br></div></div>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<div><div class="h5"><br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>> wrote:<br>
<br>
On 4/10/2013 3:23 PM, Mukul priya wrote:<br>
<br>
<br>
Hi ,<br>
<br>
<br>
Hi Mukul,<br>
<br>
Thank you for your interest in pgRouting.<br>
<br>
I am a B.tech fourth year student at<br>
IIIT-Hyderabad<br>
pursuing a degree in computer science and engineering<br>
and i will<br>
be soon<br>
pursuing a Masters Degree in the field of Spatial<br>
Informatics<br>
and the<br>
research topic that i have been working on is *"In<br>
route nearest<br>
neighbour querries".*<br>
<br>
<br>
Last year i worked on a project that was<br>
funded by<br>
Honeywell technology solutions and it gave me a lot of<br>
insight about<br>
open source programming and industrial work culture.<br>
<br>
I was introduced to pgrouting by *Prof. Venkatesh<br>
Raghavan* who<br>
visited<br>
<br>
our college last summer. i have also used pgrouting for<br>
implementing one<br>
of my Honors project.<br>
<br>
i have gone through the updated ideas page and i am<br>
listing out<br>
a topic<br>
that i feel i can contribute to.<br>
<br>
*Idea *<br>
<br>
Network Partitioning<br>
<br>
A very simple method using which it can be done is :<br>
<br>
* *Existence of a natural Hierarchy*<br>
<br>
<br>
Generally road networks are organized such<br>
that there<br>
is some<br>
natural hierarchy for example if we look at the road<br>
network of<br>
USA we<br>
observe that there are national highways which connect<br>
multiple<br>
large<br>
regions , inter state roads connect places within these<br>
regions<br>
, multi<br>
lane roads connect city areas and then there are small<br>
roads to<br>
connect<br>
individual houses.<br>
<br>
so what we can do is first rank these<br>
classes that<br>
constitute the road network and then use the highest<br>
level roads to<br>
divide the road network into large regions enclosed by<br>
these<br>
roads. each<br>
of the divided regions can further be divided again<br>
using next lower<br>
level road.<br>
<br>
so suppose we have a road network which n<br>
classes of<br>
different roads then we can create a tree of depth n-1<br>
where the<br>
root of<br>
the tree will represent the entire road network and<br>
children of<br>
the the<br>
root node will represent the area formed by<br>
partitioning the<br>
root using<br>
the level 1 ( highest ) edges and so on . the nodes<br>
will basically<br>
represent a smaller part of the road network.<br>
<br>
The idea seems to be very naive right now<br>
but if<br>
anyone can<br>
give some feedback whether it is achievable or not or<br>
may be suggest<br>
some modifications.<br>
<br>
<br>
Yes this is the basics of how this could work. Because we<br>
build our<br>
graphs dynamically for each route request, we can do<br>
something like<br>
this today. Typically you have to feed the route request<br>
and SQL<br>
query that provides the edges needed to build the graph and<br>
this can<br>
be simply the bounding box of the start and end point of<br>
the route<br>
expanded slightly to allow the route move outside that<br>
bounds by a<br>
little if needed. A case in point are start and end points<br>
that form<br>
a vertical of horizontal line.<br>
<br>
So for the natural hierarchy, you can for a SQL query like:<br>
<br>
select * from edges where st_dwithin(the_geom, start_pnt,<br>
radius)<br>
union<br>
select * from edges where st_dwithin(the_geom, end_pnt, radius)<br>
union<br>
select * from edges<br></div></div>
where st_expand(st_makeline(start___<u></u>__pnt, end_pnt), pct)<div><div class="h5"><br>
<br>
and road_class < 4;<br>
<br>
So this gets all edges regardless of class at the start and<br>
end and<br>
then gets all the major roads and highways between the<br>
start and end<br>
points. We can dynamically select the edges that we want<br>
when we<br>
build the graph.<br>
<br>
Regardless of how you implement the routing, the problem is all<br>
about the data. If you have a road segment the is<br>
misqualified, you<br>
might end up with a network that is broken between start<br>
and end.<br>
This can alsoo happen if ramps are not coded correctly.<br>
<br>
One of the challenges we have today is that we have to be<br>
able to<br>
construct the whole graph in memory before we can start<br>
routing.<br>
This is ok for small areas but it is a problem if you want to<br>
generate a route between say Miami, Florida and Seattle,<br>
Washington.<br>
An interesting problem would be the ability to partition<br>
the data in<br>
spatial chucks and only load them as the solver needed them.<br>
<br>
If you think about your edges sorted into say 1 degree grid<br>
partitions,<br>
then you load the partition for the start point and start<br>
routing<br>
using A* search, when you frontier get to an edge of the<br>
grid you<br>
are in, then you load the adjacent grid and continue, if<br>
you bump<br>
into another grid boundary that is not loaded yet, you<br>
load, if it<br>
is already loaded you continue. Anyway food for thought! :)<br>
<br>
<br>
In route nearest neighbour querries(<br>
IRNN) which<br>
handle<br>
querries like computation of shortest path , provided<br>
that the user<br>
wants to visit facilities F1 , F2 ,.....FN while he/she<br>
drives<br>
or walks<br>
from source to destination. Network partitioning can<br>
optimize these<br>
computations too as the search space reduces<br>
significantly once<br>
we have<br>
the partitions. Handling such querries have not been<br>
implemented<br>
yet. It<br>
will be very helpful if we can have some discussion<br>
about whether<br>
implementing it is feasible or not.<br>
<br>
<br>
What is we just added via support to routing? Then we could do<br>
something like say generate a route: Start, F1, F2, ... Fn, End<br>
This would allow us to build a graph one time and then generate<br>
multiple sub-routes with in the graph. Today if you want to<br>
do that<br>
you have to generate n+1 routes and build the graph n+1<br>
times. We<br>
could also do some preliminary optimization of the via<br>
points based<br>
on Euclidean distance using something like TSP before<br>
calling the<br>
router.<br>
<br>
<br>
<br>
It would be great if someone could give<br>
a general<br>
idea<br>
how to go about learning more about the areas<br>
mentioned with<br>
respect<br>
to the organization's projects.Specially suggest those<br>
ideas<br>
which the<br>
developers think are achievable for now . I will also<br>
be grateful if<br>
somebody can guide me regarding the development<br>
framework of<br>
pgrouting<br>
so that i get familiar with the whole framework in the<br>
coming days.<br>
<br>
<br>
I would clone the github repository and look at branch<br>
sew-devel-2_0<br>
this is our new tree structure and it has code, doc, and<br>
test all<br>
organized in a nice way that makes it easy to multiple<br>
contributors<br>
work with the tree.<br>
<br>
Ask questions, There is a tutorial floating around and lots of<br>
people that are will to help.<br>
<br>
-Steve<br>
<br>
Thank you .<br>
<br>
Mukul Priya<br>
Lab for spatial Informatics<br>
IIIT-Hyderabad<br>
<br>
<br></div></div>
______________________________<u></u>_____________________<div class="im"><br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br></div>
<mailto:<a href="mailto:pgrouting-dev@lists." target="_blank">pgrouting-dev@lists.</a>__<a href="http://osgeo.org" target="_blank"><u></u>osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>>><br>
<a href="http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/____<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>>__><br>
<br>
<br>
______________________________<u></u>_____________________<div class="im"><br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br></div>
<mailto:<a href="mailto:pgrouting-dev@lists." target="_blank">pgrouting-dev@lists.</a>__<a href="http://osgeo.org" target="_blank"><u></u>osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>>><br>
<a href="http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/____<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>>__><div class="im"><br>
<br>
<br>
<br>
<br>
______________________________<u></u>___________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br>
<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<br>
______________________________<u></u>___________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br>
<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
</div></blockquote><div class="HOEnZb"><div class="h5">
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br></div>