I have a NetworkX graph corresponding to a mix of road and telecommunication network of a town, and different sets of nodes (of variable size) representing the location of network devices. I have to find an optimal path connecting all devices along the network and I tought the
steiner_tree algorithmn available in NetworkX should do the trick.
Most of the time I get results within a reasonable time and with a reasonable use of resources (i.e. RAM). Sometimes however, when working with graph of few thousands nodes (around 5000) the process takes longer and eats a great amount of RAM.
I am searching for ways to reduce the complexity of the graph and I found the
contracted_nodes function in
networkx.algorithms.minors module. I use it to "contract" any node with a degree of 2, obtaining a single edge out of a sequence of consecutive edges.
contracted_nodes has an optional
self_loop parameter with the effect of preserving contracted edges as self loops.
Which can be the effects, if any, of these self loops on the