[pgrouting-users] Reduce the graph

[Stephen Woodbridge]

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