Re: [Algorithms] Trimming network connectivity

[Jason H. <jas...@di...>]

Step 1.  Define 'walkability' in a way that you can produce a cost 
metric, and optimize for it.
Step 2.  ????
Step 3.  Profit!

Once you know what it means to improve your graph in quantitative terms, 
you can pretty easily write an algorithm to add an edge, score the graph 
as a whole with the edge in, then take it back out and try another 
edge.  A greedy algorithm will take the best edge at all times and give 
you a fairly decent result.  Fancier systems might use simulated 
annealing to add more edges than a greedy system would, but later come 
back and pare out a few whose contributions have been negated through 
other similar additions.

Thanks,
JH

mark meijer wrote:
> On Fri, May 16, 2008 at 10:59 PM, Robin Green <rob...@gm...> wrote:
>   
>> If I read this right, you start with a 2D point cloud, then you connect them up using a loose metric of "neighbour", you get too many links, then you want to trim the graph.
>>
>> How about substituting this "connect them up" step with a better metric so that you don't have to trim the graph at the end? How about you use the points in the 2D point cloud to generate a Voronoi diagram of the space, and use the adjacency graph of the resulting Voronoi cells as your initial graph. That way you get the "closest neighbour" points using a mathematically precise definition of "neighbour". If you then want to limit the number of neighbours, you just need to trim edges in the graph with too large a valency (number of links) - if you obey spanning rules you'll get the same connectivity but less edges.
>>     
>
>
> I'd considered Delaunay triangulation (the dual graph of Voronoi)
> which is great for
> making the ideal mesh..  with no crossed links.
> But we want some crossed links for better walking coverage.
> Not sure how to add "some" links back in.
>
> For example, take four corners of a square as nodes.
> Connect them up with links by Delaunay and you get one diagonal
> link making two triangles.  But we'd want both diagonals for
> better walkability.
>
> http://en.wikipedia.org/wiki/Delaunay_triangulation
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft 
> Defy all challenges. Microsoft(R) Visual Studio 2008. 
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>