[pgrouting-users] Reduce the graph

Aurelien_FILEZ · March 9, 2012, 4:39pm

Hi all,

My edge table has some useless nodes. For example :

edge_id v1 v2 the_geom
1 1 2 LINESTRING(x1 y1, x2 y2)
2 2 3 LINESTRING(x2 y2, x3 y3)

But the vertex 2 is no used in any other edge.

So I would like reduce my graph to transforme this previous example to :

edge_id v1 v2 the_geom
1 1 3 LINESTRING(x1 y1, x2 y2, x3 y3)

Is there is a way to do that ?

Thank you all

Kin

Stephen_Woodbridge1 · March 9, 2012, 4:48pm

On 3/9/2012 11:39 AM, Aurélien FILEZ wrote:

Hi all,

My edge table has some useless nodes. For example :

edge_id v1 v2 the_geom
1 1 2 LINESTRING(x1 y1, x2 y2)
2 2 3 LINESTRING(x2 y2, x3 y3)

But the vertex 2 is no used in any other edge.

So I would like reduce my graph to transforme this previous example to :
edge_id v1 v2 the_geom
1 1 3 LINESTRING(x1 y1, x2 y2, x3 y3)

Is there is a way to do that ?

Thank you all

There is no automatic way to do this. I have done a lot of graph analysis by adding a cnt column to the vertices_tmp column and then updating it to the count of edges connected to that vertex.

Then you can do things like look for:

deadends - cnt=1
connected lines - cnt=2

You could write a stored procedure to that the connected lines, join them together, and update the relevant tables to reflect the new topology.

-Steve

Aurelien_FILEZ · March 10, 2012, 7:20am

Hi,

This table is build with lines I decompose in segments of 2 points.

Maybe it is better to act from these full lines, searching points used by more than one line ?

Thanks,
Kin

On Fri, Mar 9, 2012 at 5:48 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 3/9/2012 11:39 AM, Aurélien FILEZ wrote:

Hi all,

My edge table has some useless nodes. For example :

edge_id v1 v2 the_geom
1 1 2 LINESTRING(x1 y1, x2 y2)
2 2 3 LINESTRING(x2 y2, x3 y3)

But the vertex 2 is no used in any other edge.

So I would like reduce my graph to transforme this previous example to :
edge_id v1 v2 the_geom
1 1 3 LINESTRING(x1 y1, x2 y2, x3 y3)

Is there is a way to do that ?

Thank you all

There is no automatic way to do this. I have done a lot of graph analysis by adding a cnt column to the vertices_tmp column and then updating it to the count of edges connected to that vertex.

Then you can do things like look for:

deadends - cnt=1
connected lines - cnt=2

You could write a stored procedure to that the connected lines, join them together, and update the relevant tables to reflect the new topology.

-Steve

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

Stephen_Woodbridge1 · March 10, 2012, 2:51pm

On 3/10/2012 2:20 AM, Aurélien FILEZ wrote:

Hi,

This table is build with lines I decompose in segments of 2 points.

Maybe it is better to act from these full lines, searching points used
by more than one line ?

Yes, but the question that I am trying to answer is How are you going to do the efficiently?

I just noticed that you already have v1 and v2 assigned, so you can do something like this:

create table vertices_tmp as
select id, count(*) as cnt from
(select v1 as id from edge union all select v2 as id from edge) as foo group by id;

Now to find all the the nodes where cnt=2

select id from vertices_tmp where cnt=2;

And you write a stored procedure to merge the two edges.

-Steve

Thanks,
Kin

On Fri, Mar 9, 2012 at 5:48 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    On 3/9/2012 11:39 AM, Aurélien FILEZ wrote:

        Hi all,

        My edge table has some useless nodes. For example :

        edge_id v1 v2 the_geom
        1 1 2 LINESTRING(x1 y1, x2 y2)
        2 2 3 LINESTRING(x2 y2, x3 y3)

        But the vertex 2 is no used in any other edge.

        So I would like reduce my graph to transforme this previous
        example to :
        edge_id v1 v2 the_geom
        1 1 3 LINESTRING(x1 y1, x2 y2, x3 y3)

        Is there is a way to do that ?

        Thank you all

    There is no automatic way to do this. I have done a lot of graph
    analysis by adding a cnt column to the vertices_tmp column and then
    updating it to the count of edges connected to that vertex.

    Then you can do things like look for:

    deadends - cnt=1
    connected lines - cnt=2

    You could write a stored procedure to that the connected lines, join
    them together, and update the relevant tables to reflect the new
    topology.

    -Steve
    ______________________________ _________________
    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>

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

Aurelien_FILEZ · March 11, 2012, 1:43pm

I’ll try starting from this.

Thank you very much

On Sat, Mar 10, 2012 at 3:51 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 3/10/2012 2:20 AM, Aurélien FILEZ wrote:

Hi,

This table is build with lines I decompose in segments of 2 points.

Maybe it is better to act from these full lines, searching points used
by more than one line ?

Yes, but the question that I am trying to answer is How are you going to do the efficiently?

I just noticed that you already have v1 and v2 assigned, so you can do something like this:

create table vertices_tmp as
select id, count(*) as cnt from
(select v1 as id from edge union all select v2 as id from edge) as foo group by id;

Now to find all the the nodes where cnt=2

select id from vertices_tmp where cnt=2;

And you write a stored procedure to merge the two edges.

-Steve

Thanks,
Kin

On Fri, Mar 9, 2012 at 5:48 PM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

On 3/9/2012 11:39 AM, Aurélien FILEZ wrote:

Hi all,

My edge table has some useless nodes. For example :

edge_id v1 v2 the_geom
1 1 2 LINESTRING(x1 y1, x2 y2)
2 2 3 LINESTRING(x2 y2, x3 y3)

But the vertex 2 is no used in any other edge.

So I would like reduce my graph to transforme this previous
example to :
edge_id v1 v2 the_geom
1 1 3 LINESTRING(x1 y1, x2 y2, x3 y3)

Is there is a way to do that ?

Thank you all

There is no automatic way to do this. I have done a lot of graph
analysis by adding a cnt column to the vertices_tmp column and then
updating it to the count of edges connected to that vertex.

Then you can do things like look for:

deadends - cnt=1
connected lines - cnt=2

You could write a stored procedure to that the connected lines, join
them together, and update the relevant tables to reflect the new
topology.

-Steve

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo. org

mailto:[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>

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
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Aurelien_FILEZ · March 15, 2012, 7:19am

Hello,

I made this :

drop table if exists graph_vertices_tmp;
create table graph_vertices_tmp as
select id, count(*) as cnt from
(
select source as id from edges
union all
select target as id from edges
)
as foo
GROUP BY id;
delete from graph_vertices_tmp where cnt <> 2;
create unique index graph_vertices_tmp_idx_id ON graph_vertices_tmp(id);
REINDEX TABLE graph_vertices_tmp;

create unique index osm_new_way_edges_save_idx_id ON edges(id);
create index osm_new_way_edges_save_idx_source ON edges(source);
create index osm_new_way_edges_save_idx_target ON edges(target);
REINDEX TABLE edges;

create or replace function fct_simplify() RETURNS VOID AS ’
DECLARE
c CURSOR for select id from graph_vertices_tmp;
v integer;
edge_id_to_remove integer;
BEGIN
open c;
LOOP
fetch c into v;
EXIT WHEN NOT FOUND;

SELECT id FROM edges INTO edge_id_to_remove WHERE source = v;

UPDATE edges e SET
geometry = ST_LineMerge(St_Collect(geometry, sub.subgeo)),
d = (d + sub.subd),
t = (t + sub.subt),
cost = (cost + sub.subcost),
reverse_cost = (reverse_cost + sub.subreverse_cost),
target = sub.subtarget
FROM
(
SELECT
geometry as subgeo,
d as subd,
t as subt,
cost as subcost,
reverse_cost as subreverse_cost,
source as subsource,
target as subtarget
FROM edges
WHERE id=edge_id_to_remove
) sub
WHERE target=sub.subsource;

DELETE FROM edges WHERE id = edge_id_to_remove;
END LOOP;
close c;
END;
'LANGUAGE plpgsql;

select fct_simplify()

With a graph of about 38.000.000 segments, and about 25.000.000 vertex to delete, the script is still running after 48H of execution.

Is these indexes are good ?

Is there is better approach ?

Thank you
Kin

2012/3/11 Aurélien FILEZ <kinju59@gmail.com>

I’ll try starting from this.

Thank you very much

On Sat, Mar 10, 2012 at 3:51 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 3/10/2012 2:20 AM, Aurélien FILEZ wrote:

Hi,

This table is build with lines I decompose in segments of 2 points.

Maybe it is better to act from these full lines, searching points used
by more than one line ?

Yes, but the question that I am trying to answer is How are you going to do the efficiently?

I just noticed that you already have v1 and v2 assigned, so you can do something like this:

create table vertices_tmp as
select id, count(*) as cnt from
(select v1 as id from edge union all select v2 as id from edge) as foo group by id;

Now to find all the the nodes where cnt=2

select id from vertices_tmp where cnt=2;

And you write a stored procedure to merge the two edges.

-Steve

Thanks,
Kin

On Fri, Mar 9, 2012 at 5:48 PM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

On 3/9/2012 11:39 AM, Aurélien FILEZ wrote:

Hi all,

My edge table has some useless nodes. For example :

edge_id v1 v2 the_geom
1 1 2 LINESTRING(x1 y1, x2 y2)
2 2 3 LINESTRING(x2 y2, x3 y3)

But the vertex 2 is no used in any other edge.

So I would like reduce my graph to transforme this previous
example to :
edge_id v1 v2 the_geom
1 1 3 LINESTRING(x1 y1, x2 y2, x3 y3)

Is there is a way to do that ?

Thank you all

There is no automatic way to do this. I have done a lot of graph
analysis by adding a cnt column to the vertices_tmp column and then
updating it to the count of edges connected to that vertex.

Then you can do things like look for:

deadends - cnt=1
connected lines - cnt=2

You could write a stored procedure to that the connected lines, join
them together, and update the relevant tables to reflect the new
topology.

-Steve

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo. org

mailto:[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>

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
http://lists.osgeo.org/mailman/listinfo/pgrouting-users