Algorithm for recursive network optimization

Question

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.

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..')
    print(f'finished!')
    return expanded_mst

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?

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:

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:

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

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.

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)

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

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.