<div dir="ltr"><div>Thanks steve , i an drafting the proposal for now , i will post it on this list once i am done . you can then suggest some changes if required .<br><br><br><br><br></div>Mukul.<br></div><div class="gmail_extra">
<br><br><div class="gmail_quote">On Tue, Apr 23, 2013 at 7:55 PM, 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">
On 4/23/2013 10:12 AM, Mukul priya wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi steve ,<br>
<br>
can you suggest an apt title for the project we discussed ??<br>
<br>
You once refered it as "Partition JIT graph building while routing"<br>
Whats JIT here ??<br>
</blockquote>
<br>
Just In Time<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Or can we refer it as " Routing after Graph/Network partitioning "<br>
</blockquote>
<br>
You could use something like: "On demand incremental graph building"<br>
<br>
You can swap words like: "incremental" with "dynamic" and "building" with "loading" or "assembly". So maybe something like:<br>
"A partitioned approach to on demand increment graph assembly"<br>
<br>
You only need to get the idea across and for it to be interesting so other people reading the title might want to read more about it.<br>
<br>
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Thanks.<br>
<br>
<br>
On Tue, Apr 23, 2013 at 6:32 PM, 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>>> wrote:<br>
<br>
Hi Dave,<br>
<br>
All algorithm should have tests as part of the new 2.0 release<br>
branch. While the current tests are pretty trivial, I would hope<br>
over time that we add to the existing tests to improve on out test<br>
coverage. One of the reasons that shooting star got so broken was<br>
because we did not have any tests to verify that changes made to it<br>
did not break it.<br>
<br>
The new directory structure is:<br>
<br>
src/<algorithm>/<src|sql|doc|_<u></u>_test>/<br>
<br>
in the test sub-directory there are:<br>
<br>
test.conf<br>
*.data<br>
*.test<br>
*.rest<br>
<br>
Where the test.conf file identifies what what data files to load and<br>
what test to run and it the control file that the <a href="http://test-runner.pl" target="_blank">test-runner.pl</a><br>
<<a href="http://test-runner.pl" target="_blank">http://test-runner.pl</a>> script looks for.<br>
<br>
*.data - sql ascii dump or sql statements to create data tables<br>
needed for any of the given tests.<br>
<br>
*.test - a sql query that the results of will be diff'd against a<br>
corresponding *.rest file. Any differences are reported as test<br>
failures.<br>
<br>
I would expect all new code to have tests installed in the future.<br>
What were you referring to by a 'test grid'?<br>
<br>
Thanks,<br>
-Steve<br>
<br>
<br>
On 4/23/2013 2:41 AM, Mukul priya wrote:<br>
<br>
Hi Dave ,<br>
<br>
Can I suggest that a 'test grid' be created for this project and<br>
be made<br>
part of pgroute package.<br>
<br>
In that way, when somebody is having a problem, they can be<br>
asked to run<br>
a problem basied on the 'test gird' and it can be discovered very<br>
quickly if there is problem with the pgroute package or<br>
something else.<br>
Can you be a bit more elaborate about this??<br>
<br>
Sorry for replying late.<br>
<br>
<br>
Mukul<br>
<br>
<br>
<br>
<br>
On Tue, Apr 16, 2013 at 9:00 PM, 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>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>> wrote:<br>
<br>
On 4/15/2013 6:36 AM, Mukul priya wrote:<br>
<br>
Hi Steve ,<br>
Just to clear things i would prefer<br>
item 2 (<br>
partitioning<br>
graph and then routing ) over item1 ( multi point<br>
routing ) .Its<br>
kind of<br>
exciting and challenging too. what are your thoughts<br>
regarding<br>
this??<br>
<br>
<br>
I am fine with this preference. I think it is more<br>
important that<br>
whatever you work on will be exciting and keep you interested<br>
through out the course of the project.<br>
<br>
<br>
I went through the mail archive of<br>
previous years<br>
and it was<br>
quite useful . For now i am trying to get familiar<br>
with the<br>
development<br>
framework whenever i get time using this link<br>
<br>
(<a href="https://github.com/pgRouting/____pgrouting/wiki/Developer---____Getting-Started" target="_blank">https://github.com/pgRouting/<u></u>____pgrouting/wiki/Developer--<u></u>-____Getting-Started</a><br>
<<a href="https://github.com/pgRouting/__pgrouting/wiki/Developer---__Getting-Started" target="_blank">https://github.com/pgRouting/<u></u>__pgrouting/wiki/Developer---_<u></u>_Getting-Started</a>><br>
<br>
<<a href="https://github.com/pgRouting/__pgrouting/wiki/Developer---__Getting-Started" target="_blank">https://github.com/pgRouting/<u></u>__pgrouting/wiki/Developer---_<u></u>_Getting-Started</a><br>
<<a href="https://github.com/pgRouting/pgrouting/wiki/Developer---Getting-Started" target="_blank">https://github.com/pgRouting/<u></u>pgrouting/wiki/Developer---<u></u>Getting-Started</a>>>).<br>
<br>
Once i am done with my semester by 23rd of this month i<br>
will<br>
speed up<br>
significantly.<br>
<br>
Meanwhile feedbacks and suggestions are<br>
welcome.<br>
<br>
<br>
As you have time learning the development environment and<br>
github are<br>
critical so you can focus on your project and not the<br>
infrastructure.<br>
<br>
You should also look over:<br>
<a href="https://github.com/pgRouting/____pgrouting/wiki/2.0-____Development-Guidelines-and-____Standards" target="_blank">https://github.com/pgRouting/_<u></u>___pgrouting/wiki/2.0-____<u></u>Development-Guidelines-and-___<u></u>_Standards</a><br>
<<a href="https://github.com/pgRouting/__pgrouting/wiki/2.0-__Development-Guidelines-and-__Standards" target="_blank">https://github.com/pgRouting/<u></u>__pgrouting/wiki/2.0-__<u></u>Development-Guidelines-and-__<u></u>Standards</a>><br>
<br>
<br>
<<a href="https://github.com/pgRouting/__pgrouting/wiki/2.0-__Development-Guidelines-and-__Standards" target="_blank">https://github.com/pgRouting/<u></u>__pgrouting/wiki/2.0-__<u></u>Development-Guidelines-and-__<u></u>Standards</a><br>
<<a href="https://github.com/pgRouting/pgrouting/wiki/2.0-Development-Guidelines-and-Standards" target="_blank">https://github.com/pgRouting/<u></u>pgrouting/wiki/2.0-<u></u>Development-Guidelines-and-<u></u>Standards</a>>><br>
<br>
Thanks,<br>
-Steve<br>
<br>
Thanks<br>
<br>
Mukul<br>
<br>
<br>
<br>
<br>
On Sun, Apr 14, 2013 at 7:11 PM, Mukul priya<br>
<<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a> <mailto:<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a>><br>
<mailto:<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a> <mailto:<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a>>><br>
<mailto:<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a><br>
<mailto:<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a>> <mailto:<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a><br>
<mailto:<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a>>>><u></u>> wrote:<br>
<br>
Thanks for the reply Steve , clarifies all the<br>
issues that<br>
i raised<br>
, Proposed data structures cover what we need ,<br>
quad tree<br>
should<br>
work too , I am right now looking into the last<br>
part which<br>
describes the method of appending our graph with<br>
new cells<br>
, seems<br>
fine and very much implementable , will post<br>
something in<br>
case some<br>
new ideas strike me . :)<br>
<br>
<br>
Thanks.<br>
<br>
<br>
On Sun, Apr 14, 2013 at 10:59 AM, Stephen Woodbridge<br>
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.>_<u></u>___com<br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>>> wrote:<br>
<br>
On 4/13/2013 11:12 PM, Mukul priya wrote:<br>
<br>
Thanks Steve for clearly mentioning the<br>
two proposals.<br>
<br>
For Item 1 , upgrading all the algorithms will<br>
certainly<br>
require a lot<br>
of work and since i will be having my<br>
summer vacation i<br>
don't have any<br>
issue with it :).<br>
<br>
<br>
For item 2 , i am looking into the idea<br>
that you have<br>
proposed , It is<br>
very much doable , there are however some<br>
concerns<br>
of mine like<br>
<br>
- how do we decide what should be the grid<br>
size .<br>
this can<br>
vary for<br>
suburban area and urban area based on<br>
netwrok density.<br>
<br>
<br>
This might be done with a quad tree approach.<br>
You start<br>
with a<br>
square and some condition like maximum number<br>
of node.<br>
If you<br>
exceed that number you quarter it into 4<br>
squares and<br>
divide the<br>
point into each of them.<br>
<br>
<br>
- how do we classify the nodes lying on the<br>
junction of two<br>
or more<br>
grids . should it be assigned to all the<br>
grids??<br>
<br>
<br>
A node can only lie in one square or the edge<br>
boundary of a<br>
square it does not matter which one it is put<br>
in. Edges<br>
need to<br>
be flagged if the cross a square boundary.<br>
<br>
<br>
- how do we decide the grid that needs to<br>
be loaded<br>
in the<br>
memory ,<br>
connectivity with the previous grid seems<br>
legit<br>
here but i<br>
guess we need<br>
to discuss some corner cases too.<br>
<br>
<br>
We could probably do something like<br>
<br>
typedef struct pair {<br>
int a;<br>
int b;<br>
} PAIR;<br>
<br>
typedef struct edge_type {<br>
int node_a;<br>
int node_b;<br>
PAIR *squares; // NULL if it does not cross<br>
square edge<br>
float cost;<br>
float rcost;<br>
} EDGE;<br>
<br>
Where PAIR can be assign the gridcell for the<br>
a and b ends.<br>
<br>
If we number the grid cells by their quadtree<br>
numbers like:<br>
<br>
+---+---+<br>
| 1 | 2 |<br>
+---+---+<br>
| 3 | 4 |<br>
+---+---+<br>
<br>
So you start, with the above for your coverage<br>
area. So all<br>
nodes would fall into cells 1-4. If you had to<br>
split cell 1<br>
above, then those 4 new cells would be number<br>
11, 12,<br>
13, 14 and<br>
the remaining unsplit cells would still be 2,<br>
3, 4. If<br>
you had<br>
to further split cell 14, then the new cells<br>
would be<br>
numbered<br>
141, 142, 143, 144. So each time a cell gets<br>
subdivided, it gets<br>
another digit added.<br>
<br>
This is the challenge of design good<br>
algorithms, if we have<br>
millions of edges and node, we need to be<br>
efficient<br>
memory wise<br>
with our data structures but still be fast. In the<br>
database, you<br>
need to think about where the data is coming<br>
from (ie:<br>
tables<br>
using queries) and when it gets moved into<br>
memory. You<br>
can't<br>
think just C code or database code, you have<br>
to use both.<br>
<br>
The idea being that we want to prepare our data in<br>
tables, then<br>
issue queries from C to get the new edges we<br>
need to append<br>
cell(s) to our graph. So I'm thinking that we<br>
have a<br>
recursive<br>
plpgsql procedure that splits the nodes into the<br>
appropriate<br>
quadtree cells based on some rules. So for<br>
example we<br>
have a<br>
vertices_tmp table that we use to assign node<br>
numbers<br>
to nodes,<br>
we could add a cell column like this:<br>
<br>
CREATE TABLE vertices_tmp<br>
(<br>
id serial NOT NULL,<br>
cell bigint,<br>
the_geom geometry,<br>
);<br>
<br>
and after we run the quadtree analysis each<br>
node is<br>
assigned a<br>
cell number. The edge table has node_a and node_b<br>
assigned to it<br>
also.<br>
<br>
If we want all edges related to cell 114 then<br>
we can do<br>
a query<br>
like:<br>
<br>
select b.*<br>
from vertices_tmp a, edges b<br>
where a.cell=114 and (<a href="http://a.id" target="_blank">a.id</a> <<a href="http://a.id" target="_blank">http://a.id</a>><br>
<<a href="http://a.id" target="_blank">http://a.id</a>><br>
<<a href="http://a.id" target="_blank">http://a.id</a>>=b.node_a or <a href="http://a.id" target="_blank">a.id</a> <<a href="http://a.id" target="_blank">http://a.id</a>> <<a href="http://a.id" target="_blank">http://a.id</a>><br>
<<a href="http://a.id" target="_blank">http://a.id</a>>=b.node.b);<br>
<br>
<br>
Thoughts?<br>
<br>
-Steve<br>
<br>
<br>
Thanks.<br>
<br>
<br>
<br>
<br>
On Sat, Apr 13, 2013 at 6:20 AM, Stephen<br>
Woodbridge<br>
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.>_<u></u>___com<br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.><u></u>______com<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.>_<u></u>___com<br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>>>> wrote:<br>
<br>
On 4/11/2013 3:24 PM, Mukul priya wrote:<br>
<br>
Hi Steve and Daniel,<br>
<br>
<br>
You suggested extending<br>
the present<br>
algorithms such<br>
that its<br>
input can take more points and<br>
not only<br>
the source and<br>
destination . i<br>
think this can be implemented and<br>
i will<br>
soon come<br>
up with<br>
implementation details( kind of more<br>
technical ) .<br>
<br>
Can you be a liitle bit<br>
more<br>
elaborate about<br>
partioning data<br>
into spatial chunks or even<br>
suggest some<br>
readings .<br>
I can then<br>
come up<br>
with some better ideas about<br>
implementing it.<br>
<br>
<br>
This is just me thinking out loud :)<br>
<br>
Lets say we construct a grid of one<br>
degree<br>
squares, you can<br>
visualize it by drawing a grid over<br>
your map.<br>
<br>
Then you can associate all the nodes<br>
with the<br>
grid they<br>
fall in. We<br>
might also need to associate edges to the<br>
grids also<br>
and an edge the<br>
crosses over a grid boundary might<br>
need to be<br>
associated with two<br>
grids. This could be done with some<br>
simple<br>
relational<br>
tables like:<br>
<br>
node_id|grid_id or edge_d|grid_id<br>
<br>
So my idea would be to do the routing<br>
like this:<br>
<br>
1. get the start node or edge<br>
2. build the graph based on loading<br>
the items<br>
in the<br>
related grid<br>
3. mark the boundary nodes (we might<br>
want to<br>
do this<br>
when we grid them)<br>
4. run the algorithm until we find<br>
the target<br>
node or<br>
hit a boundary<br>
node<br>
5. on hitting a boundary:<br>
a. we check if the connected grid<br>
is loaded and<br>
continue if it is<br>
b. or we extent the graph with the<br>
new grid<br>
6. continue with the routing<br>
<br>
We might want to be able to<br>
dynamically change<br>
the size<br>
of the grid<br>
cell based on the number of items in<br>
it. This<br>
would<br>
give us better<br>
performance when transitioning from rural<br>
areas into<br>
urban areas<br>
where there is a greater density of<br>
road segments.<br>
Think of a<br>
quadtree where we split it based on<br>
number of<br>
entities.<br>
<br>
<br>
Daniel , i took a look<br>
at the<br>
oracle link<br>
that you<br>
provided but<br>
there was no details about how it<br>
has been<br>
implemented , it was more<br>
about how one can use it. May be<br>
a bit<br>
more search<br>
and luck might<br>
take me to its implementation<br>
document :) .<br>
<br>
<br>
Right, it is useful if you look at the<br>
documentation<br>
and ask why did<br>
they do it that way and what does it<br>
imply<br>
about how it<br>
works behind<br>
the scenes.<br>
<br>
<br>
The other thing that you<br>
mentioned was<br>
about contraction<br>
Hierarchy . Still the nodes have<br>
to be ordered<br>
based on some<br>
criteria or<br>
according to their importance .<br>
We can<br>
use natural<br>
hierarchy<br>
present in<br>
the network for doing that .<br>
<br>
<br>
This is not related to what you<br>
proposed. It is an<br>
algorithm that<br>
does a lot of precompuation, that is<br>
LOTS in<br>
capitals,<br>
but it can<br>
get results in milliseconds for cross<br>
country<br>
routes.<br>
<br>
<br>
i will be really<br>
grateful if<br>
anyone can<br>
correct me<br>
in case if<br>
my thought process in not on the<br>
right<br>
lane and<br>
sorry for the<br>
late reply<br>
as my academic session is in<br>
progress too<br>
.Meanwhile i am<br>
trying to<br>
get fluent with git ,cmake and<br>
other tools.<br>
<br>
<br>
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>
<<a href="https://github.com/pgRouting/______pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>______pgrouting/wiki</a>><br>
<<a href="https://github.com/pgRouting/______pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>______pgrouting/wiki</a><br>
<<a href="https://github.com/pgRouting/____pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>____pgrouting/wiki</a>>><br>
<br>
<br>
<<a href="https://github.com/pgRouting/______pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>______pgrouting/wiki</a><br>
<<a href="https://github.com/pgRouting/____pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>____pgrouting/wiki</a>><br>
<<a href="https://github.com/pgRouting/____pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>____pgrouting/wiki</a><br>
<<a href="https://github.com/pgRouting/__pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>__pgrouting/wiki</a>>>><br>
<br>
<br>
<br>
<<a href="https://github.com/pgRouting/______pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>______pgrouting/wiki</a><br>
<<a href="https://github.com/pgRouting/____pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>____pgrouting/wiki</a>><br>
<<a href="https://github.com/pgRouting/____pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>____pgrouting/wiki</a><br>
<<a href="https://github.com/pgRouting/__pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>__pgrouting/wiki</a>>><br>
<br>
<<a href="https://github.com/pgRouting/____pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>____pgrouting/wiki</a><br>
<<a href="https://github.com/pgRouting/__pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>__pgrouting/wiki</a>><br>
<<a href="https://github.com/pgRouting/__pgrouting/wiki" target="_blank">https://github.com/pgRouting/<u></u>__pgrouting/wiki</a><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<br>
are two<br>
unrelated<br>
proposals on<br>
the table (I'm leaving out the<br>
contraction<br>
hierarchy):<br>
<br>
1. multi point routing<br>
2. partition JIT graph building while<br>
routing<br>
<br>
Item 1 is fairly trivial technically,<br>
I think,<br>
but if<br>
you were to<br>
upgrade all the algorithms to do this<br>
it would<br>
be a lot<br>
of work and<br>
a useful contribution to pgrouting.<br>
<br>
Item 2 is more of a design and code a new<br>
algorithm and<br>
you would<br>
probably want to focus on using astar<br>
or trsp<br>
algorithm<br>
to do this<br>
with. This one is more technically<br>
challenging<br>
and has<br>
more unknowns<br>
in it but I think it should be doable.<br>
<br>
If you are interested in reading<br>
about contraction<br>
hierarchies:<br>
<a href="https://www.google.com/#q=________contraction" target="_blank">https://www.google.com/#q=____<u></u>____contraction</a><br>
<<a href="https://www.google.com/#q=______contraction" target="_blank">https://www.google.com/#q=___<u></u>___contraction</a>><br>
<<a href="https://www.google.com/#q=______contraction" target="_blank">https://www.google.com/#q=___<u></u>___contraction</a><br>
<<a href="https://www.google.com/#q=____contraction" target="_blank">https://www.google.com/#q=___<u></u>_contraction</a>>><br>
<br>
<br>
<<a href="https://www.google.com/#q=______contraction" target="_blank">https://www.google.com/#q=___<u></u>___contraction</a><br>
<<a href="https://www.google.com/#q=____contraction" target="_blank">https://www.google.com/#q=___<u></u>_contraction</a>><br>
<<a href="https://www.google.com/#q=____contraction" target="_blank">https://www.google.com/#q=___<u></u>_contraction</a><br>
<<a href="https://www.google.com/#q=__contraction" target="_blank">https://www.google.com/#q=__<u></u>contraction</a>>>><br>
<br>
<br>
<br>
<<a href="https://www.google.com/#q=______contraction" target="_blank">https://www.google.com/#q=___<u></u>___contraction</a><br>
<<a href="https://www.google.com/#q=____contraction" target="_blank">https://www.google.com/#q=___<u></u>_contraction</a>><br>
<<a href="https://www.google.com/#q=____contraction" target="_blank">https://www.google.com/#q=___<u></u>_contraction</a><br>
<<a href="https://www.google.com/#q=__contraction" target="_blank">https://www.google.com/#q=__<u></u>contraction</a>>><br>
<<a href="https://www.google.com/#q=____contraction" target="_blank">https://www.google.com/#q=___<u></u>_contraction</a><br>
<<a href="https://www.google.com/#q=__contraction" target="_blank">https://www.google.com/#q=__<u></u>contraction</a>><br>
<<a href="https://www.google.com/#q=__contraction" target="_blank">https://www.google.com/#q=__<u></u>contraction</a><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>
Thanks .<br>
<br>
Mukul<br>
<br>
<br>
<br>
<br>
On Thu, Apr 11, 2013 at 6:47 PM,<br>
Stephen<br>
Woodbridge<br>
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.>_<u></u>___com<br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.><u></u>______com<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.>_<u></u>___com<br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a> <mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>>.<u></u>>________com<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.><u></u>______com<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.>_<u></u>___com<br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>>>>> wrote:<br>
<br>
With pgRouting, we do most<br>
things<br>
dynamically,<br>
here is the<br>
basic flow:<br>
<br>
1. Given a collection of input,<br>
points, nodes,<br>
or edges<br>
map these to nodes or edges<br>
depending on<br>
algorithm.<br>
<br>
2. Select the edges we need<br>
to build<br>
the graph<br>
<br>
3. build the graph and solve it<br>
<br>
4. return the results<br>
<br>
All our algorithms today<br>
only take<br>
start and<br>
end points.<br>
They could<br>
be extended to take points. Each<br>
"point" (I<br>
use "point" as<br>
a generic<br>
term because it might be a<br>
lat/lon,<br>
node id,<br>
edge id and<br>
offset,<br>
etc) would need to be mapped<br>
to the<br>
appropriate input need<br>
for any<br>
given algorithm.<br>
<br>
So for node based algorithms<br>
like<br>
Dijkstra,and<br>
astar it<br>
would get<br>
resolved to a node. For TRSP<br>
it would get<br>
mapped to the<br>
nearest edge<br>
and offset along that edge.<br>
Postgis<br>
has lots<br>
of handy tools for<br>
doing this.<br>
<br>
-Steve<br>
<br>
<br>
On 4/10/2013 10:50 PM, Mukul<br>
priya wrote:<br>
<br>
Thanks for the reply<br>
steve . i have<br>
already cloned the<br>
github<br>
repository<br>
and looking into various<br>
aspects<br>
of it .<br>
<br>
For IRNN querry<br>
implementation i<br>
think it<br>
is a good<br>
idea to sub<br>
divide<br>
the whole route and<br>
generate n+1<br>
routes<br>
separately ,<br>
say from S<br>
to F1 ,<br>
F1-F2 ,..... F(n-1)-Fn ,<br>
Fn to D . i<br>
wanted to know if<br>
we have<br>
that kind<br>
of a data where each and<br>
every<br>
facility is<br>
mentioned on<br>
the map as a<br>
point (node ) . even if<br>
it is not<br>
directly<br>
connected to<br>
the road<br>
network<br>
we can basically treat it a<br>
pseudo node<br>
and then call<br>
the router<br>
. The<br>
other thing about<br>
optimization<br>
yes we can<br>
do that using<br>
spatial<br>
range<br>
querries suppose there<br>
are several<br>
instances of the same<br>
facility that a<br>
user wants to access<br>
then we can use<br>
spatial range<br>
querries to<br>
locate<br>
that facility which is<br>
the nearest.<br>
<br>
<br>
On Thu, Apr 11, 2013 at<br>
1:42 AM,<br>
Stephen<br>
Woodbridge<br>
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.>_<u></u>___com<br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.><u></u>______com<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.>_<u></u>___com<br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a> <mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>>.<u></u>>________com<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.><u></u>______com<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.>_<u></u>___com<br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>>>><br>
<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a> <mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a> <mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>><br>
<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a> <mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>>><u></u>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a> <mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>>><u></u>.__>________com<br>
<br>
<br>
<br>
<br>
<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a> <mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a> <mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>>.<u></u>>________com<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a><br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>>.><u></u>______com<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.<br>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>.>_<u></u>___com<br>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<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<br>
PM, Mukul<br>
priya wrote:<br>
<br>
<br>
Hi ,<br>
<br>
<br>
Hi Mukul,<br>
<br>
Thank you for your<br>
interest<br>
in pgRouting.<br>
<br>
<br>
I am a<br>
B.tech<br>
fourth year<br>
student at<br>
IIIT-Hyderabad<br>
pursuing a<br>
degree in<br>
computer<br>
science and<br>
engineering<br>
and i will<br>
be soon<br>
pursuing a Masters<br>
Degree in the<br>
field of Spatial<br>
Informatics<br>
and the<br>
research topic<br>
that i<br>
have been<br>
working on is *"In<br>
route nearest<br>
neighbour<br>
querries".*<br>
<br>
<br>
<br>
Last year<br>
i worked<br>
on a project<br>
that was<br>
funded by<br>
Honeywell<br>
technology<br>
solutions<br>
and it gave me<br>
a lot of<br>
insight about<br>
open source<br>
programming and<br>
industrial work<br>
culture.<br>
<br>
I was introduced to<br>
pgrouting by<br>
*Prof. Venkatesh<br>
Raghavan* who<br>
visited<br>
<br>
our college<br>
last summer.<br>
i have<br>
also used<br>
pgrouting for<br>
implementing one<br>
of my Honors<br>
project.<br>
<br>
i have gone<br>
through the<br>
updated<br>
ideas page and<br>
i am<br>
listing out<br>
a topic<br>
that i feel i can<br>
contribute to.<br>
<br>
*Idea *<br>
<br>
Network<br>
Partitioning<br>
<br>
A very simple<br>
method<br>
using which<br>
it can be<br>
done is :<br>
<br>
* *Existence<br>
of a natural<br>
Hierarchy*<br>
<br>
<br>
<br>
Generally road<br>
networks are<br>
organized such<br>
that there<br>
is some<br>
natural<br>
hierarchy for<br>
example if<br>
we look at<br>
the road<br>
network of<br>
USA we<br>
observe that<br>
there are<br>
national<br>
highways which<br>
connect<br>
multiple<br>
large<br>
regions , inter<br>
state roads<br>
connect places<br>
within these<br>
regions<br>
, multi<br>
lane roads<br>
connect city<br>
areas and<br>
then there<br>
are small</blockquote>
</blockquote></div><br></div>