[postgis-users] minimum spanning tree?

[Rob Tester]

There are a couple of organizations using the boost lib to solve shortest path graphs using Djikstra algorithms as well as the A Star and TSP. It would not be a stretch to get this code and modify it to use the min spanning tree code in boost as well. 

I have taken the code and made major performance enhancements that are currently being tested. So be wary of better ways to structure the SQL interface to postgis to achieve your goals.

You can get the base code from http://www.cartoweb.org/ that provides the basic for interfacing with Djisktra in boost if you want more, please contact me offline and I can send you a package that also implements the AStar and TSP, along with my performance enhancements.

Rob.



----- Original Message ----- 
  From: Paul Ramsey 
  To: PostGIS Users Discussion 
  Sent: Monday, November 06, 2006 1:44 PM
  Subject: Re: [postgis-users] minimum spanning tree?


  No such thing right now. If someone is interested in the problem, there is some background here:


  <http://en.wikipedia.org/wiki/Minimum_spanning_tree>


  P


  On 6-Nov-06, at 3:09 PM, Catherine Morency wrote:


    Hello,



    I am a new user of Postgis. 

    I am looking for a function to compile the length of the shortest string connecting a set of points.  

    There are no network, only spatial points. I have already compiled the convex hull of these sets of points and I am looking for another indicator.



    Thank you.



    ====================================

    Catherine Morency, ing., Ph.D.

    Professeure adjointe

    Département des génies civil, géologique et des mines

    École Polytechnique de Montréal

    Groupe MADITUC

    (514) 340-4711 p.4502

    cmorency at polymtl.ca

    ====================================



    _______________________________________________
    postgis-users mailing list
    postgis-users at postgis.refractions.net
    http://postgis.refractions.net/mailman/listinfo/postgis-users




------------------------------------------------------------------------------


  _______________________________________________
  postgis-users mailing list
  postgis-users at postgis.refractions.net
  http://postgis.refractions.net/mailman/listinfo/postgis-users
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20061106/1a50df2e/attachment.html>