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