Solve the Village Water Pipe Layout with NetworkX Minimum Spanning Tree

1 Water Pipe Layout Problem

There are 10 villages; we need to lay water pipes to connect them with minimal total length. The table shows distances; 0 indicates no direct connection.

2 NetworkX Solution Process

2.1 Step 1: Prepare Data

Import data and libraries.

import matplotlib.pyplot as plt
%matplotlib inline
import networkx as nx
import pandas as pd
data = {1: {1: 0, 2: 5, 3: 6, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 9, 10: 0},
        2: {1: 5, 2: 0, 3: 1, 4: 2, 5: 12, 6: 0, 7: 5, 8: 0, 9: 0, 10: 2},
        3: {1: 6, 2: 1, 3: 0, 4: 6, 5: 0, 6: 7, 7: 0, 8: 0, 9: 0, 10: 0},
        4: {1: 0, 2: 2, 3: 6, 4: 0, 5: 8, 6: 0, 7: 4, 8: 0, 9: 0, 10: 3},
        5: {1: 0, 2: 12, 3: 0, 4: 8, 5: 0, 6: 0, 7: 0, 8: 1, 9: 0, 10: 0},
        6: {1: 0, 2: 0, 3: 7, 4: 0, 5: 0, 6: 0, 7: 5, 8: 0, 9: 7, 10: 0},
        7: {1: 0, 2: 5, 3: 0, 4: 4, 5: 0, 6: 5, 7: 0, 8: 10, 9: 0, 10: 0},
        8: {1: 0, 2: 0, 3: 0, 4: 0, 5: 1, 6: 0, 7: 10, 8: 0, 9: 0, 10: 0},
        9: {1: 9, 2: 0, 3: 0, 4: 0, 5: 0, 6: 7, 7: 0, 8: 0, 9: 0, 10: 0},
        10:{1: 0, 2: 2, 3: 0, 4: 3, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0}}
pipeline = pd.DataFrame(data)  # Convert to DataFrame

2.2 Step 2: Generate Graph

Convert the DataFrame to a NetworkX graph; alternatively one could use an adjacency matrix with nx.Graph(A).

G = nx.from_pandas_adjacency(pipeline)  # Build graph from DataFrame

2.3 Step 3: Compute Minimum Spanning Tree

G_tree = nx.minimum_spanning_tree(G, weight='weight')  # Compute weighted MST

Note: the weight='weight' argument is required; otherwise NetworkX computes an unweighted MST.

2.4 Step 4: Output Results

print(G_tree.edges)  # Show edges of the MST

The edges returned give the optimal pipe layout:

[(10, 2), (9, 6), (8, 5), (7, 4), (7, 6), (5, 4), (4, 2), (3, 2), (2, 1)]

For visualization, draw the network and highlight the MST edges:

pos = nx.layout.circular_layout(G)  # Circular layout
nx.draw(G, pos, with_labels=True, node_color='c', alpha=0.8)  # Draw graph
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_color='m')
nx.draw_networkx_edges(G, pos, edgelist=G_tree.edges, edge_color='orange', width=4)

3 Full Code

import matplotlib.pyplot as plt
%matplotlib inline
import networkx as nx
import pandas as pd
data = {1: {1: 0, 2: 5, 3: 6, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 9, 10: 0},
        2: {1: 5, 2: 0, 3: 1, 4: 2, 5: 12, 6: 0, 7: 5, 8: 0, 9: 0, 10: 2},
        3: {1: 6, 2: 1, 3: 0, 4: 6, 5: 0, 6: 7, 7: 0, 8: 0, 9: 0, 10: 0},
        4: {1: 0, 2: 2, 3: 6, 4: 0, 5: 8, 6: 0, 7: 4, 8: 0, 9: 0, 10: 3},
        5: {1: 0, 2: 12, 3: 0, 4: 8, 5: 0, 6: 0, 7: 0, 8: 1, 9: 0, 10: 0},
        6: {1: 0, 2: 0, 3: 7, 4: 0, 5: 0, 6: 0, 7: 5, 8: 0, 9: 7, 10: 0},
        7: {1: 0, 2: 5, 3: 0, 4: 4, 5: 0, 6: 5, 7: 0, 8: 10, 9: 0, 10: 0},
        8: {1: 0, 2: 0, 3: 0, 4: 0, 5: 1, 6: 0, 7: 10, 8: 0, 9: 0, 10: 0},
        9: {1: 9, 2: 0, 3: 0, 4: 0, 5: 0, 6: 7, 7: 0, 8: 0, 9: 0, 10: 0},
        10:{1: 0, 2: 2, 3: 0, 4: 3, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0}}
pipeline = pd.DataFrame(data)
G = nx.from_pandas_adjacency(pipeline)
G_tree = nx.minimum_spanning_tree(G, weight='weight')
print(G_tree.edges)
pos = nx.layout.circular_layout(G)
nx.draw(G, pos, with_labels=True, node_color='c', alpha=0.8)
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_color='m')
nx.draw_networkx_edges(G, pos, edgelist=G_tree.edges, edge_color='orange', width=4)