# Algorithm for recursive network optimization

I have a very challenging problem I am trying to solve.

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

address_nodes = [node for node, data in g.nodes(data=True) if data.get('type') == 'address']

# Create a complete weighted graph with addresses as nodes
complete_graph = nx.Graph()
counter += 1
if i < j:  # Avoid duplicate edges and self-loops
path_length = nx.shortest_path_length(g, source=u, target=v, weight='length')

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):
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?

• 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 Aug 30 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
Aug 30 at 22:39

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:

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.

• Very interesting solution, would be nice to see the corresponding code. Aug 31 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
Sep 1 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
Sep 1 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 Sep 2 at 3:52
• @FelixIP what a creative, brilliant solution. Stream networks!
– bj3t
Oct 5 at 3:14