<jupyter_start><jupyter_text>9.4-2 (using custom functions) The Wirehouse Lumber Company will soon begin logging eight groves of trees in the same general area. Therefore, it must develop a system of dirt roads that makes each grove accessible from every other grove. The distance (in miles) between every pair of groves is as follows:  Management now wishes to determine between which pairs of groves the roads should be constructed to connect all groves with a minimum total length of road.(a) Describe how this problem fits the network description of the minimum spanning tree problem. (b) Use the algorithm described in Sec. 9.4 to solve the problem.<jupyter_code>import pandas as pd
# initialize data
df = pd.read_csv('data_arc.csv')
df.head()
# remove any rows that are not connected
df = df[df['distance']!=0]
df.head()
# create set of vertices
nodes = set(df['u'])
nodes
# create list of arc tuples
arcs = list((t[1], t[2]) for t in df.itertuples())
arcs[:10]
distance_dict = dict([((t[1], t[2]), t.distance) for t in df.itertuples()])

def create_neighbor_dict(unconnected_nodes, connected_nodes):
    neighbor_dict ={}
    for i in connected_nodes:
        for j in unconnected_nodes:
            try: 
                distance = distance_dict[i,j]
            except:
                pass
            neighbor_dict.update({(i,j):distance})
    return neighbor_dict
# check
connected_nodes = [1,4]
create_neighbor_dict2(unconnected_nodes, connected_nodes)
    
def find_nearest_neighbor_edge(unconnected_nodes, connected_nodes):
    neighbor_dict = create_neighbor_dict(unconnected_nodes, connected_nodes)
    min_key = min(neighbor_dict, key=neighbor_dict.get)
    return min_key
# check 
find_nearest_neighbor_edge(unconnected_nodes, connected_nodes)
def find_nearest_neighbor(unconnected_nodes, connected_nodes):
    neighbor_dict = create_neighbor_dict(unconnected_nodes, connected_nodes)
    min_key = min(neighbor_dict, key=neighbor_dict.get)
    return  min_key[1]
find_nearest_neighbor(unconnected_nodes, connected_nodes)<jupyter_output><empty_output><jupyter_text>Main logic<jupyter_code># initialize data
unconnected_nodes = list(nodes)
connected_nodes =[]
distance_lst =[]
total_distance = 0
edges =[]

# set a starting node
j = unconnected_nodes[0]
connected_nodes.append(j)
unconnected_nodes.remove(j)

while len(unconnected_nodes) != 0:

    # find the minimum distance for nodes from nodes that are connected to nodes that are not
    edge_soln = find_nearest_neighbor_edge(unconnected_nodes, connected_nodes)
    edge_distance = distance_dict[edge_soln]
    j = edge_soln[1]

    # update trackers
    distance_lst.append(edge_distance)
    total_distance = total_distance + edge_distance
    edges.append(edge_soln)
    unconnected_nodes.remove(j)
    connected_nodes.append(j)

total_distance = round(total_distance,4)
node_1 = [i[0] for i in edges]
node_2 = [i[1] for i in edges]

print('total_distance: ', total_distance)
print('edges: ', edges)
print('distance_lst: ', distance_lst)
print('unconnected_nodes: ', unconnected_nodes)
print('connected_nodes: ', connected_nodes)
output_df = pd.DataFrame(
    {'node_1': node_1,
     'node_2': node_2,
     'distance': distance_lst
    })
output_df

total_distance<jupyter_output><empty_output><jupyter_text>Plot results<jupyter_code>%matplotlib inline
import matplotlib.pyplot as plt
import networkx as nx
from networkx.algorithms import tree
arcs = list((t[1], t[2]) for t in df.itertuples())
distance_dict = dict([((t[1], t[2]), t.distance) for t in df.itertuples()])

G = nx.Graph()

for x in arcs:
    i = x[0]
    j = x[1]
    weight = distance_dict[i,j]
    G.add_edge(i,j,weight = weight)

pos = nx.spring_layout(G) 
nx.draw_networkx_nodes(G, pos, node_size=400)
nx.draw_networkx_edges(G, pos, edgelist=edges,width=1)
nx.draw_networkx_labels(G, pos, font_size=15, font_family='sans-serif')

plt.axis('off')
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09946578478758586, 'fraction_numerical': 0.010429916051895192, 'mean_word_length': 5.105590062111801, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '230237', 'license': 'MIT', 'n_tokens_mistral': 1312, 'n_tokens_neox': 1298, 'n_words': 345, 'path': '9.4 (The Minimum Spanning Tree Problem)/prob_2/9.4-2 (using custom functions).ipynb', 'repo_name': 'shellei503/introduction-to-operations-research-7th-ed', 'size': '3931'}