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

pgRouting pgrouting-dev
1

-------- 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@pinan.co.uk
To: woodbri@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@pinan.co.uk <mailto:dave.potts@pinan.co.uk>
To: pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@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

2

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@pinan.co.uk
To: woodbri@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@pinan.co.uk <mailto:dave.potts@pinan.co.uk>
To: pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@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@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

3

+1 for using pgRouting as a graph tools rather than traffic tool

Cheers,

Rémi-C

···

2016-03-24 16:07 GMT+01:00 Stephen Woodbridge <woodbri@swoodbridge.com>:

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@pinan.co.uk
To: woodbri@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@pinan.co.uk mailto:[dave.potts@pinan.co.uk](mailto:dave.potts@pinan.co.uk)
To: pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@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

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

4

I would also like to see more functions for network analysis.
pgRouting unfortunately has “routing” in its name, but it’s already more than that.

I think it would be nice to create an issue for each function.
Then, if someone wants to add the missing pieces, such as tests and documentation, new functions could be added via pull request.

Daniel

···

On 25/03/16 00:14, Rémi Cura wrote:

+1 for using pgRouting as a graph tools rather than traffic tool

Cheers,

Rémi-C

2016-03-24 16:07 GMT+01:00 Stephen Woodbridge <woodbri@swoodbridge.com>:

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@pinan.co.uk
To: woodbri@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@pinan.co.uk mailto:[dave.potts@pinan.co.uk](mailto:dave.potts@pinan.co.uk)
To: pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@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

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@lists.osgeo.org)
[http://lists.osgeo.org/mailman/listinfo/pgrouting-users](http://lists.osgeo.org/mailman/listinfo/pgrouting-users)

-- 
Georepublic UG & Georepublic Japan
eMail: [daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
Web: [https://georepublic.info](https://georepublic.info)