Minimum Spanning Tree based on a street network

4917
13
07-19-2012 12:08 AM
DanielOefele
New Contributor
HI GIS Experts,

I hope you can help me with my network analyse problem (ArcGIS 10.0 SP2 - ArcView License)

Background:
I try to create a network of fiber optic cables to specific points along a street network.

Here is what I want to do:
I want to create a Minimum Spanning Tree based on a street network to give me the shortest path between a couple of
fiber optic access points. The MST should start at a fiber optic distribution point and "span out" to the access
points.

What I tried so far:
I tried to manage it with the Network Analyst and the 'Closest Facility' analysis. The problem is that it handles
each connection between a distribution point and a access point as a independent solution (end up in a single
route) - so its not the MST.
I am not sure if something like that is possible with a geometric network (with sinks and sources) and a flow
direction.

Thank you all for your support in advance,

Daniel
0 Kudos
13 Replies
JaySandhu
Esri Regular Contributor
You could look at the following user written tools that contain some minimum spanning tree tools:
http://www.nrel.colostate.edu/projects/starmap/funconn_index.htm

Jay Sandhu
0 Kudos
DanielOefele
New Contributor
I found a solution for my problem to create a minimum spanning tree (mst) based on a street network:

1. I create a mst with the spanning tree tools (http://resources.arcgis.com/de/gallery/file//geoprocessing/details?entryID=B66BA793-1422-2418-A0BE-D...)

2. I use the geospatial modelling environment (http://www.spatialecology.com/gme/ - convert.linestopoints function) to create a start and endpoint of every single line of my mst. These points get the ID of the line.

3. I use the network analyst and the RouteName (ReouteName is the ID of the mst line) function to create single routes between every start and end point created with the geospatial modelling environment.

Thanks again for your ideas and support
0 Kudos
PeterWilson
Regular Contributor

Hi Daniel

I found the following post of yours and wanted to find out some more detail in how to performed the following. I've got a  similar problem that i'm trying to solve. I've got land parcels that have been identified as users for effluent reuse water for irrigating parks, sports fields and green belts. I want to use the road network to determine the optimal layout of my pipeline network using the parcels as stops. I can easily convert my parcels to points  if need be. I wanted to find out from you in more details how to solved your problem using MST, Network Analyst to generate you network.

Regards

Peter Wilson

0 Kudos
LanoYado
New Contributor III

Hi Daniel, would you mind sending me the tools in the first links since it gives me error and not able to download it.

Thanks in advance 

0 Kudos
DanPatterson_Retired
MVP Esteemed Contributor

don't know if that is the one, but Spanning tree tools is a non-networked base tools if you are or can use shapefiles

0 Kudos
LanoYado
New Contributor III

Thank you Dan, actually it is only for point-input layer while I am looking for minimum spanning tree tool that can be applied on a specific road map (a network with points and lines). 

0 Kudos
DanPatterson_Retired
MVP Esteemed Contributor

yes... it isn't designed for that specifically, but can work if the road can be converted to points and the inter-road spacing is greater the along-road point spacing... that is, so that the spanning tree doesn't hop from one road to another.  sometimes, you can ensure point-along-line traverse, by densifying the points on the network.  You will have issues if the point data set is large, since that incarnation hasn't been optimized (on the todo list)

0 Kudos
LanoYado
New Contributor III

That is a good idea, I converted the lines to points but I got this error:

0 Kudos
DanPatterson_Retired
MVP Esteemed Contributor

strange... did you unzip everything in the same folder? and add the toolbox to arctoolbox?

If there are bits missing Lano, Let me know and I can fix the update in about 8 hours (not on, or near my 'machine' sorry)

0 Kudos