I have a connected network consisting of lines (edges) and points (nodes). I must connect a subset of these nodes together along the shortest path.

A zoomed-in image of my network is below. The red dots (end points) must all be interconnected to each other following the shortest path. For example, to connect one end point to another, I would need to travel down a green line (connecting line) and along one or more grey lines (path lines) and back up another green line (connecting line) just to connect those two red end points together.

Original Network

As you can see in the following image, I have accomplished this using the following algorithm.

def optimize_fpp_with_mst_addresses_only(g):
    counter = 0
    # Extract address nodes
    address_nodes = [node for node, data in g.nodes(data=True) if data.get('type') == 'address']
    num_address = len(address_nodes)
    print(f'number of addresses: {num_address}')

    # Create a complete weighted graph with addresses as nodes
    complete_graph = nx.Graph()
    for i, u in enumerate(address_nodes):
        counter += 1
        for j, v in enumerate(address_nodes):
            if i < j:  # Avoid duplicate edges and self-loops
                path_length = nx.shortest_path_length(g, source=u, target=v, weight='length')
                complete_graph.add_edge(u, v, weight=path_length)
        print(f'Weighted graph construction: {float(counter/num_address)*100}% complete..')
    counter = 0

    # Compute MST on the complete graph
    print(f'computing mst on complete graph..')
    mst = nx.minimum_spanning_tree(complete_graph, weight='weight')
    #mst = nx.algorithms.approximation.steinertree.steiner_tree(complete_graph, 
    #            terminal_nodes=address_nodes, weight='weight', method = 'mehlhorn')
    num_edges = len(mst.edges())
    # Reconstruct the MST in the original graph
    expanded_mst = nx.Graph()
    for u, v in mst.edges():
        counter += 1
        path = nx.shortest_path(g, source=u, target=v, weight='length')
        for idx in range(len(path) - 1):
            node_u, node_v = path[idx], path[idx+1]
            if not expanded_mst.has_edge(node_u, node_v):
                expanded_mst.add_edge(node_u, node_v, **g[node_u][node_v])
        print(f'Reconstructed MST graph: {float(counter/num_edges)*100}% complete..')
    return expanded_mst

MST connected graph

PROBLEM: Now the hard part. I am tasked with optimizing the network and have the freedom to cut end points from the network if it yields a more optimal value. I believe the value I am trying to minimize is:

Z = sum edge lengths along path / number of connected addresses in path

As @FelixIP pointed out, there is an optimal solution and it would be a single address node not connected to anything:

Z = 0/1

I want to avoid that situation without providing hard coded constraints like minimum number of addresses to connect = 10.

If I added an attribute (N) to every node, so that every node that is an endpoint of the green lines, but is not a red address point gets a value of 1 and all other nodes get a value of 0, perhaps I can ensure more than one address is connected by modifying my function to maximize:

Z = sum N for every node in path connecting addresses / sum length edges in path connecting addresses 

If I maximize that value, I am instructing the optimization algo to find the subnetwork connecting addresses so that the number of addresses connected to the network is as many as possible, while the total length of the subnetwork is as small as possible.

If this is right, then how might I implement it?

  • The answer is any single node with others removed, because length will be zero. Incomplete target function, should be some constrains, e.g. minimum number of nodes
    – FelixIP
    Commented Aug 30, 2023 at 19:34
  • @FelixIP that's a really good point. I'd love to be able to maximize the number of connected addresses while minimizing Z, hoping that the single node situation would never arise. I've thought about assigning an attribute (let's call it N) value of 1 to every node that is linked to a green line but is not an address node and a value of 0 to every other node, then trying to maximize the sum of N at every node along the route that connects any address. Maybe the formula to optimize might be: cumulative sum of N for all nodes along any route / sum length of every edge along that route?
    – bj3t
    Commented Aug 30, 2023 at 22:39

1 Answer 1


I used minimum spanning tree of the graph (solid black line) to connect terminals. Note: not all nodes of the graph shown below:

enter image description here

And applied following algorithm on 631 terminals. Terminal being a graph node with 1 neighbour:

  • find terminal having longest connection (leg) to network, i.e. to node with more than 2 neighbours (intersection)
  • remove terminal and relevant edge
  • convert 2 edges connected to intersection into 1, remove node at intersection
  • compute Z function

Repeat till half of terminals remains. This shows changes of objective function:

enter image description here

At it's minimum at 93 removed nodes remaining network looks like that:

enter image description here

As one can see this algorithm is capable of finding sensible solution, because it is removing most 'stray' terminals. I don't think that optimal solution exists, because even computation of Steiner tree is a massive challenge, this is why they call networkx solution an approximation.

This is brute (dumb?) approach, perhaps something smarter can achieve better results, - e.g. find short leg terminal, and relevant intersection connecting average length edges, when removing shorty will result in a huge gain on a next step? How to code this is a challenge...

UPDATE it seems promising to work with directed graph. To achieve this I've picked random node in a middle of big crowd, call it SINK. Computed travel distance from all other nodes to SINK and flipped those edges where Travel[f] is less than Travel[t], where f and t are edges' from and to nodes. After that I accumulated count of terminals discharging in each edge. This is nothing but Shreve order river classification.

enter image description here enter image description here

To facilitate computations I also pre-computed accumulated value of edges' length.

Algorithm is essentially the same, but instead of shuffling through 1st order streams only, we set-up an upper limit for 'stream' order and:

  • find best edge (F,T) - the one to result in largest Z-function drop
  • remove nodes upstream from F and itself, i.e. [F]+ list(nx.ancestors(G,F))
  • reduce accordingly 'accumulated flow' of terminals and lengths for edges in nx.shortest_path(G,T,SINK) enter image description here

If I break iterations when no improvement were found, results for 1st and 2nd order optimisation look like follows:

enter image description here enter image description here

It is clear from above 2 pictures, when we use higher order, we are able to detect a pair of 'farm houses' sitting at the end of long road as candidates for elimination. They are last in a queue for initial (1st order only)approach because their connections to road are very short.

It's almost a rule: greater optimization/restructure results in a greater number of pissed off people.

  • Very interesting solution, would be nice to see the corresponding code.
    – Kalak
    Commented Aug 31, 2023 at 6:23
  • Luis Cottereau - I second that. Very interesting solution and the graph of Z vs. addresses removed is quite informative. @FelixIP "find short leg terminal, and relevant intersection connecting average length edges, when removing shorty will result in a huge gain on a next step? How to code this is a challenge..." <-- I'm still thinking about how to go about doing this. It is indeed a tough challenge.
    – bj3t
    Commented Sep 1, 2023 at 3:57
  • @FelixIP I'm going to leave this question open for a bit longer to see if there are any other solutions, but your solution is truly appreciated.
    – bj3t
    Commented Sep 1, 2023 at 3:58
  • Good luck with that. I have a feeling that very interesting questions like yours aren't really welcomed here. They are at risk of being closed simply because no specific gis package tagged:( "How to round value" sorts generates times greater interest
    – FelixIP
    Commented Sep 2, 2023 at 3:52
  • @FelixIP what a creative, brilliant solution. Stream networks!
    – bj3t
    Commented Oct 5, 2023 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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