[pgrouting-dev] Gsoc 2013 Preliminary project proposal
Dave Potts
dave.potts at pinan.co.uk
Sun Apr 14 06:02:24 PDT 2013
On 14/04/13 06:29, Stephen Woodbridge wrote:
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.
Dave.
> 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=b.node_a or 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>> 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>
>>
>> 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> 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>
>> <mailto:woodbri at swoodbridge.__com
>> <mailto: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>
>> <mailto:woodbri at swoodbridge.__com
>> <mailto:woodbri at swoodbridge.com>>
>> <mailto:woodbri at swoodbridge.
>> <mailto:woodbri at swoodbridge.>____com
>>
>> <mailto:woodbri at swoodbridge.__com
>> <mailto: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
>> roads to
>> connect
>> individual houses.
>>
>> so what we can do is first
>> rank these
>> classes that
>> constitute the road network and then use the
>> highest
>> level roads to
>> divide the road network into large regions
>> enclosed by
>> these
>> roads. each
>> of the divided regions can further be divided
>> again
>> using next lower
>> level road.
>>
>> so suppose we have a road network
>> which n
>> classes of
>> different roads then we can create a tree of
>> depth n-1
>> where the
>> root of
>> the tree will represent the entire road
>> network and
>> children of
>> the the
>> root node will represent the area formed by
>> partitioning the
>> root using
>> the level 1 ( highest ) edges and so on . the
>> nodes
>> will basically
>> represent a smaller part of the road network.
>>
>> The idea seems to be very naive
>> right now
>> but if
>> anyone can
>> give some feedback whether it is achievable or
>> not or
>> may be suggest
>> some modifications.
>>
>>
>> Yes this is the basics of how this could work.
>> Because we
>> build our
>> graphs dynamically for each route request, we
>> can do
>> something like
>> this today. Typically you have to feed the route
>> request
>> and SQL
>> query that provides the edges needed to build the
>> graph and
>> this can
>> be simply the bounding box of the start and end
>> point of
>> the route
>> expanded slightly to allow the route move
>> outside that
>> bounds by a
>> little if needed. A case in point are start and
>> end points
>> that form
>> a vertical of horizontal line.
>>
>> So for the natural hierarchy, you can for a SQL
>> query like:
>>
>> select * from edges where st_dwithin(the_geom,
>> start_pnt,
>> radius)
>> union
>> select * from edges where st_dwithin(the_geom,
>> end_pnt, radius)
>> union
>> select * from edges
>> where st_expand(st_makeline(start_______pnt,
>> end_pnt), pct)
>>
>>
>> and road_class < 4;
>>
>> So this gets all edges regardless of class at the
>> start and
>> end and
>> then gets all the major roads and highways
>> between the
>> start and end
>> points. We can dynamically select the edges that
>> we want
>> when we
>> build the graph.
>>
>> Regardless of how you implement the routing, the
>> problem is all
>> about the data. If you have a road segment the is
>> misqualified, you
>> might end up with a network that is broken between
>> start
>> and end.
>> This can alsoo happen if ramps are not coded
>> correctly.
>>
>> One of the challenges we have today is that we
>> have to be
>> able to
>> construct the whole graph in memory before we can
>> start
>> routing.
>> This is ok for small areas but it is a problem if
>> you want to
>> generate a route between say Miami, Florida and
>> Seattle,
>> Washington.
>> An interesting problem would be the ability to
>> partition
>> the data in
>> spatial chucks and only load them as the solver
>> needed them.
>>
>> If you think about your edges sorted into say 1
>> degree grid
>> partitions,
>> then you load the partition for the start point
>> and start
>> routing
>> using A* search, when you frontier get to an edge
>> of the
>> grid you
>> are in, then you load the adjacent grid and
>> continue, if
>> you bump
>> into another grid boundary that is not loaded
>> yet, you
>> load, if it
>> is already loaded you continue. Anyway food for
>> thought! :)
>>
>>
>> In route nearest neighbour
>> querries(
>> IRNN) which
>> handle
>> querries like computation of shortest path ,
>> provided
>> that the user
>> wants to visit facilities F1 , F2 ,.....FN
>> while he/she
>> drives
>> or walks
>> from source to destination. Network
>> partitioning can
>> optimize these
>> computations too as the search space reduces
>> significantly once
>> we have
>> the partitions. Handling such querries have
>> not been
>> implemented
>> yet. It
>> will be very helpful if we can have some
>> discussion
>> about whether
>> implementing it is feasible or not.
>>
>>
>> What is we just added via support to routing? Then
>> we could do
>> something like say generate a route: Start, F1,
>> F2, ... Fn, End
>> This would allow us to build a graph one time and
>> then generate
>> multiple sub-routes with in the graph. Today if
>> you want to
>> do that
>> you have to generate n+1 routes and build the
>> graph n+1
>> times. We
>> could also do some preliminary optimization of
>> the via
>> points based
>> on Euclidean distance using something like TSP
>> before
>> calling the
>> router.
>>
>>
>>
>> It would be great if someone
>> could give
>> a general
>> idea
>> how to go about learning more about the areas
>> mentioned with
>> respect
>> to the organization's projects.Specially
>> suggest those
>> ideas
>> which the
>> developers think are achievable for now . I
>> will also
>> be grateful if
>> somebody can guide me regarding the
>> development
>> framework of
>> pgrouting
>> so that i get familiar with the whole
>> framework in the
>> coming days.
>>
>>
>> I would clone the github repository and look at
>> branch
>> sew-devel-2_0
>> this is our new tree structure and it has code,
>> doc, and
>> test all
>> organized in a nice way that makes it easy to
>> multiple
>> contributors
>> work with the tree.
>>
>> Ask questions, There is a tutorial floating around
>> and lots of
>> people that are will to help.
>>
>> -Steve
>>
>> Thank you .
>>
>> Mukul Priya
>> Lab for spatial Informatics
>> IIIT-Hyderabad
>>
>>
>>
>> _____________________________________________________
>>
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>
>> <mailto:pgrouting-dev at lists.__osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>
>> <mailto:pgrouting-dev at lists.
>> <mailto:pgrouting-dev at lists.>____osgeo.org <http://osgeo.org>
>> <mailto:pgrouting-dev at lists.__osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>>
>> http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>
>>
>> <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>
>>
>>
>> <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>>
>> <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>__>
>>
>>
>> _____________________________________________________
>>
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>
>> <mailto:pgrouting-dev at lists.__osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>
>> <mailto:pgrouting-dev at lists.
>> <mailto:pgrouting-dev at lists.>____osgeo.org <http://osgeo.org>
>> <mailto:pgrouting-dev at lists.__osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>>
>> http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>
>>
>> <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>
>>
>>
>> <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>>
>> <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>__>
>>
>>
>>
>>
>>
>> ___________________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>
>> <mailto:pgrouting-dev at lists.__osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>
>> http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>>
>> <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>
>>
>>
>> ___________________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>
>> <mailto:pgrouting-dev at lists.__osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>
>> http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>
>>
>>
>>
>>
>> _________________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>
>> http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>
>>
>> _________________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>> http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>
>>
>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list