2

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.

The 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 steiner_tree algorithm?

1
1

You can contract all nodes of degree 2 except for the terminals (the nodes that should always be in your tree). The reason is that you will never have a non-terminal node as a leaf in an optimal Steiner tree, otherwise you could just remove it from the tree. You don't need the self loops. As a side note: the Steiner tree algorithm in networkxx is not only quite slow, but also does not provide optimal solutions. You can get much faster and better results with https://scipjack.zib.de/

2
  • 2
    Plaese read @whuber's answer in "Promoting something I am associated with?". Jan 14 at 21:08
  • Sinne I use my real name here, I don't think I am hiding any association. My main interest is for people to use Steiner trees succesfully in practice, the code is open source
    – daniel
    Jan 14 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.