Networkx memory usage on steiner tree algorithm in QGIS

Question

I'm trying to run a steiner tree for some points on a road using networkx by a simply script in QGIS. It's my first experience with this library. The data are shapefiles and are composed as follows: terminal points 5000 points, road 18000 segments. In the points there is only one integer "ipx" column, in the street a single column integer "weight".

When I launch the algorithm the RAM grows up to 128GB (I have a maximum of 128GB of ram) and remains like this for a long time. I imagined that for so few points and line segments the ram shouldn't grow like that and instead it grows en then appears a message of memory error .

Is this normal?

My code:

import networkx as nx 
strada = nx.read_shp("--path of the shapefile street--",geom_attrs=True, strict=True)
strada_senzadirezione = nx.Graph(strada)
Base = nx.read_shp("--path of the shapefile terminal points--",geom_attrs=True, strict=True)
nodi = list(Base.nodes) 
from networkx.algorithms import approximation as ax
st_tree = ax.steinertree.steiner_tree(strada_senzadirezione,nodi,weight='weight')
nx.write_shp(st_tree, 'd://')

Answer 1

Yes, that is normal. Networkx cannot handle big instances well. I would recommend to use some other software packages, see https://en.wikipedia.org/wiki/Steiner_tree_problem#External_links