[pgrouting-users] Reduce the graph

[Aurélien FILEZ]

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 at gmail.com>

> I'll try starting from this.
>
> Thank you very much
>
>
> On Sat, Mar 10, 2012 at 3:51 PM, Stephen Woodbridge <
> woodbri at 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 at swoodbridge.com <mailto:woodbri at swoodbridge.**com<woodbri at 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 at lists.osgeo. org
>>>    <mailto:Pgrouting-users at lists.**osgeo.org<Pgrouting-users at lists.osgeo.org>
>>> >
>>>    http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>>>    <http://lists.osgeo.org/**mailman/listinfo/pgrouting-**users<http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>>> >
>>>
>>>
>>>
>>>
>>>
>>> ______________________________**_________________
>>> Pgrouting-users mailing list
>>> Pgrouting-users at lists.osgeo.**org <Pgrouting-users at 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 at lists.osgeo.**org <Pgrouting-users at lists.osgeo.org>
>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-**users<http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20120315/3e60ee9f/attachment-0001.html