[pgrouting-dev] an implementation of beta skeletons, relative neighborhood graph and gabriel graphs

Stephen Woodbridge woodbri at swoodbridge.com
Thu Mar 24 08:07:43 PDT 2016


Hi Dave,

I just looked at the wikipedia pages and these analysis look very 
interesting. My primary focus is on vehicle routing so I'm not sure I'm 
a good judge of their usefulness, but pgRouting has been used for Max 
Flow Analysis and other not vehicle routing problems.

I've cc'd this to the user list to get a wider audience and see if there 
is interest from other users in this kind of analysis.

Also if you put these in a github repository, I believe we have a page 
in our wiki that points to other projects that might be useful to 
pgRouting users. See Friends of pgRouting:
https://github.com/pgRouting/pgrouting/wiki#friends-of-pgrouting

-Steve

On 3/24/2016 10:51 AM, Stephen Woodbridge wrote:
>
>
>
> -------- Forwarded Message --------
> Subject:     Fwd: [pgrouting-dev] an implementation of beta skeletons,
> relative neighborhood graph and gabriel graphs
> Date:     Tue, 22 Mar 2016 09:21:44 +0000
> From:     dave.potts at pinan.co.uk
> To:     woodbri at swoodbridge.com
>
>
>
> Hi Steve,
>
> Sorry to trouble you.
>
> I email this to the development email list and did not get a response.
>
> I know that Beta skelton graphs are not a standard routing style
> function but its the sort otf thing I use in my research which is all
> about network anaylsis.  I just wondered if anybody else did.
>
> Dave.
>
> -------- Forwarded message -------
> From: dave.potts at pinan.co.uk <mailto:dave.potts at pinan.co.uk>
> To: pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
> Sent: 19 March 2016 17:28
> Subject: [pgrouting-dev] an implementation of beta skeletons, relative
> neighborhood graph and gabriel graphs
> Is there any interest in any off the above graph forms in the routing
> library?
>
> See
> https://en.wikipedia.org/wiki/Beta_skeleton
> https://en.wikipedia.org/wiki/Relative_neighborhood_graph
> https://en.wikipedia.org/wiki/Gabriel_graph
>
> I have implementation with the following method signatures
>
> CREATE OR REPLACE FUNCTION pgr_beta_skelton(sql text, beta float,OUT id
> integer ,OUT id1 integer , OUT id2 integer)
>     RETURNS SETOF RECORD AS
>       '$libdir/librouting-2.1', 'dir_graph_beta_skelton'
>       LANGUAGE c STABLE STRICT;
>
> CREATE OR REPLACE FUNCTION pgr_relative_neigborhood_graph(sql text ,OUT
> id integer ,OUT id1 integer , OUT id2 integer)
>     RETURNS SETOF RECORD AS
>       '$libdir/librouting-2.1', 'dir_graph_relative_neigborhood_graph'
>       LANGUAGE c STABLE STRICT;
>
> CREATE OR REPLACE FUNCTION pgr_gabriel_graph(sql text ,OUT id integer
> ,OUT id1 integer , OUT id2 integer)
>     RETURNS SETOF RECORD AS
>       '$libdir/librouting-2.1', 'dir_graph_gabriel_graph'
>       LANGUAGE c STABLE STRICT;
>
> They all take an sql statement of the form
>
> select  st_makeline(v1.the_geom,v2.the_geom) as the_geom  from
>    pgr_gabriel_graph('select id,st_x(the_geom) as x ,st_y(the_geom) as y
> from tmp_table2'), tmp_table2 v1, tmp_table2 v2 where id1=v1.id and
>    id2=v2.id;
>
> Ie the expect an set of objects with an id and a x and y coordinate
>
> In this example tmp_table functions as resource of data, and the above
> statement returns a serries of id statements id refers to id of 1st x/y
> node and the 2nd id refers to 2md x/y pair
> eg
> id  | id1 | id2
> -----+-----+-----
>      1 | 607 | 558
>      2 | 606 | 542
>      3 | 605 | 594
>      4 | 605 | 520
>      5 | 604 | 579
>      6 | 604 | 525
>      7 | 603 | 605
>      8 | 603 | 594
>      9 | 603 | 530
>     10 | 602 | 580
>     11 | 602 | 563
>     12 | 601 | 537
>     13 | 601 | 534
>     14 | 600 | 523
>     15 | 599 | 601
>     16 | 599 | 522
>     17 | 598 | 590
>
>
> regards
>
> Dave.
>
>
>
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev


---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus



More information about the pgrouting-dev mailing list