Here I made an R package that could handle this problem. This tool uses that v.net.steiner algorithm, but uses it iteratively in order to get just the lines of the network that are relevant. Alfter iterate over n samples of your terminals, it calculates a new optimal Steiner Tree for the whole network.
So in resume, you will save ram because:
- You don't need to open the whole QGIS interface.
- Iterations of Steiner Tree are saved in the HDD (in a working grassdata folder).
- The global Steiner Tree is calculated just with useful lines of the network.
Here is the R package: https://github.com/cesarkero/IterativeSteinerTree
Here is a simple code to use it (just change l and p for your lines and points layer):
Here you have an example of how to use it.
update.packages()
library(devtools)
install_github("cesarkero/IterativeSteinerTree")
library(IterativeSteinerTree)
# basic setGRASS (based on iniGRASS params but simplified)
setGRASS(gisBase = "/usr/lib/grass78", epsg= 25829)
# load sldf (l) and spdf (p)
data("l"); data("p")
# calculate Steiner Tree
IST <- IterativeSteinerTree(l, p[1:100,], th=1000, iterations = 25,
samples = 10, clean = TRUE, rpushbullet=FALSE)
The only problem is that this package just work in linux.
You first need to define what you mean by shortest path. If you don't weight your graph (G), shortest path is simply the path that connects the nodes that passes through the fewest number of other nodes. If you want to incorporate the actual length of the lines, you need to create a weighted graph:
# Compute weights
weights = lengths of each link in idict.items # square root of sum of squares or whatever
#Create the network graph
G = nx.Graph()
for k,v, wt in zip(idict.items(), weights):
G.add_edge(v[0],v[1], weight = wt)
Note that since your graph has apparently no directionality, you should not use a DiGraph. A regular Graph should be sufficient. Now G contains weighted links, and you can use the dijkstra algorithms to find the shortest paths.
You should look at this page for your options: https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html Scroll down to "Shortest path algorithms for weighed graphs."
From your question, it appears that you'll want one of the all_pairs_xxx -- which you choose depends on what output you want. If you want the actual nodes along each shortest path, use all_pairs_dijkstra_path. If you just need the lengths, use all_pairs_dijkstra_path_length. If you need both, use all_pairs_dijkstra.
Note that these functions all return an iterator--the shortest paths are not actually computed until you unpack the iterator. This means that these functions will compute very quickly, but the real heavy lifting occurs after you unpack them. You can unpack them simply:
blah = nx.all_pairs_dijkstra_path(G)
shortest_paths = list(blah)
shortest_paths should be the same length as the number of nodes in G.
Note that there is some redundancy in this approach, and I'm not sure if networkX takes advantage of the fact that the shortest path from n0->n1 is the same as n1->n0 for an undirected graph.
Best Answer
If I understand your goal and what you mean by "attach" properly, I think you could use GRASS v.distance tool to find the nearest road feature for each point and create line links connecting them. The tool also allows you to upload attributes from the point layer to the line layer. Ostensibly one can do that with more than one attribute field. However I have only been successful in transferring one attribute field at a time (I'm sure I'm just not doing something right). The single attribute field is sufficient if one uses 'category' or other unique ID as the transferred attribute field; one can then join other attributes from the point layer to the line layer using that shared key field.
I was accessing GRASS tools via QGIS 2.2 (not Processing/SEXTANTE plugin, which in spite of its general excellence kept locking up on this task for me). "Pep", you were obviously already loaded up in GRASS, but here's how I went about it, anyway:
-In QGIS, add a field to attribute table that will soon accept unique identifier (ie, 'cat' in GRASS) of nearest feature
-Create new GRASS mapset and import the line and point layers into GRASS with v.in.ogr.qgis
-Run v.distance tool, choosing 'Category of the nearest feature' for "Values describing the relation between two nearest features" and the name of the newly created attribute field for "Attribute field to (over)write"
-If needed, join attribute tables using newly created common key field. I did this back in QGIS after using v.out.ogr to get both points and lines exported back to shapefiles (note: watch the CRS) under the layer Properties > Join tab.