[pgrouting-dev] Gsoc 2013 Preliminary project proposal
Daniel Kastl
daniel at georepublic.de
Tue Apr 23 08:05:05 PDT 2013
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130424/0f973e06/attachment-0001.html>
More information about the pgrouting-dev
mailing list