[pgrouting-dev] Gsoc 2013 Preliminary project proposal
Mukul priya
mukul2047 at gmail.com
Tue Apr 23 08:22:19 PDT 2013
Thanks Daniel for the info. will keep that in mind. :)
On Tue, Apr 23, 2013 at 8:35 PM, Daniel Kastl <daniel at georepublic.de> wrote:
> Hi Mukul,
>
> You don't need to post the proposal on the list.
> You can also write it to the Melange GSoC system, which allows you to edit
> the proposal until the deadline passed, and we can post comments there,
> which are also visible to other OSGeo mentors.
>
> I know that formatting in Melange is a bit limited, but an easy to read
> proposal makes everyone happy ;-)
>
> Daniel
>
>
>
>
>
> On Tue, Apr 23, 2013 at 11:36 PM, Mukul priya <mukul2047 at gmail.com> wrote:
>
>> 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
>>>>
>>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de
> Web: http://georepublic.de
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130423/7309418a/attachment-0001.html>
More information about the pgrouting-dev
mailing list