Help the engineer

Computer Science Level 4

An engineer working for a telecom company wants to design a cable network in a small nation. He can only bury the cables along main roads. Some paths are more expensive than others. It turns out that a previous employee of the company had already layed a network that is not efficient. In order to minimize costs, our engineer wants to optimize the network by removing some edges while keeping all points on the network connected.

For example, the network below can be optimized by removing the edge from $1$ to $4$ : This saves a cost of $3$ .

The engineer is given this larger network to optimize. What is the total cost saved?

Details and assumtions

The network is represented in the text file is represented in an adjacency matrix representation. Basically, the cost from node $x$ to node $y$ is represented in the matrix $A$ as $A_{xy}$ (column $x$ , row $y$ ). $A_{xy}=0$ if a path doesnt exist from $x$ to $y$ .
The example network in the picture above has the following adjacency matrix representation:

The answer is 2852.

1 solution

Agnishom Chattopadhyay
Jul 22, 2015

Note that such a graph cannot have a cycle, since removing the bridge that completes the cycle still keeps the graph connected. Hence, it must be a tree.

The shortest tree that is a subset of a given graph such that it keeps all the vertices connected is called a Minimum Spanning Tree .

Given a graph, we could be using the Kruskal's greedy Algorithm to find the minimum spanning tree

create a forest $F$ (a set of trees), where each vertex in the graph is a separate Tree

create a set $S$ containing all the edges in the graph

while $S$ is nonempty and $S$ is not yet a Spanning Tree:

remove an edge with minimum weight from $S$ .

if the removed edge connects two different trees then add it to the forest $F$ , combining two trees into a single tree.

Notice that this algorithm is easier (or maybe I am not smart enough) to implement with adjacency list rather than an adjacency matrix. So with Python , we start with implementing a Graph class:

class Graph:
    def __init__(self,vertices=[]):
        self.vertices = set(vertices)
        self.edges = {}
    def addEdge(self,(u,v),w):
        if u < v:
            self.edges[(u,v)] = w
        else:
            self.edges[(v,u)] = w

And a function to parse an adjacency matrix:

def adjacencyMatrixToGraph(matrix):
    G = Graph(range(len(matrix)))
    for i in xrange(len(matrix)):
        for j in xrange(len(matrix)):
            if i <= j and matrix[i][j] != 0:
                G.addEdge((i,j),matrix[i][j])
    return G

And finally the Kruskal's Algorithm:

def kruskal(G): 
    A = Graph(list(G.vertices))
    forest = [set([v]) for v in G.vertices]
    def findTree(u):
        for i in xrange(len(forest)):
            if u in forest[i]:
                return i
    for (u,v) in sorted(G.edges, key=G.edges.get):
        i, j = findTree(u), findTree(v)
        if i != j:
            A.addEdge((u,v),G.edges[(u,v)])
            forest[i] = forest[j].union(forest[i])
            forest.pop(j)
        if len(forest[0]) == len(G.vertices):
            break
    return A

The rest should be trivial:

m = [[0, 0, 0, 36, 24, 0, 22, 35, 31, 20, 33, 0, 39, 5, 36, 0, 26, 49, 27, 9],
[0, 0, 2, 14, 8, 0, 33, 4, 27, 37, 17, 0, 15, 18, 12, 0, 0, 0, 0, 49],
[0, 2, 13, 50, 15, 2, 0, 16, 0, 10, 6, 43, 9, 0, 0, 0, 29, 24, 45, 0],
[36, 14, 50, 12, 32, 0, 0, 47, 0, 29, 8, 48, 29, 30, 4, 29, 17, 11, 0, 0],
[24, 8, 15, 32, 0, 0, 0, 27, 0, 0, 0, 30, 0, 18, 0, 0, 0, 22, 48, 0],
[0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 30, 6, 31, 0, 9, 12, 36, 46, 14, 7],
[22, 33, 0, 0, 0, 0, 4, 0, 18, 22, 0, 35, 0, 0, 0, 34, 7, 17, 0, 21],
[35, 4, 16, 47, 27, 0, 0, 0, 38, 26, 0, 42, 0, 27, 0, 0, 0, 24, 0, 10],
[31, 27, 0, 0, 0, 0, 18, 38, 6, 15, 0, 47, 24, 0, 0, 0, 0, 21, 0, 0],
[20, 37, 10, 29, 0, 0, 22, 26, 15, 0, 33, 0, 0, 0, 45, 0, 0, 49, 0, 0],
[33, 17, 6, 8, 0, 30, 0, 0, 0, 33, 49, 0, 0, 3, 0, 34, 4, 0, 0, 45],
[0, 0, 43, 48, 30, 6, 35, 42, 47, 0, 0, 20, 9, 27, 45, 0, 33, 17, 47, 3],
[39, 15, 9, 29, 0, 31, 0, 0, 24, 0, 0, 9, 14, 12, 0, 38, 28, 21, 19, 15],
[5, 18, 0, 30, 18, 0, 0, 27, 0, 0, 3, 27, 12, 0, 30, 0, 28, 0, 0, 0],
[36, 12, 0, 4, 0, 9, 0, 0, 0, 45, 0, 45, 0, 30, 0, 10, 12, 0, 3, 0],
[0, 0, 0, 29, 0, 12, 34, 0, 0, 0, 34, 0, 38, 0, 10, 30, 32, 45, 48, 49],
[26, 0, 29, 17, 0, 36, 7, 0, 0, 0, 4, 33, 28, 28, 12, 32, 0, 0, 22, 6],
[49, 0, 24, 11, 22, 46, 17, 24, 21, 49, 0, 17, 21, 0, 0, 45, 0, 0, 0, 1],
[27, 0, 45, 0, 48, 14, 0, 0, 0, 0, 0, 47, 19, 0, 3, 48, 22, 0, 0, 50],
[9, 49, 0, 0, 0, 7, 21, 10, 0, 0, 45, 3, 15, 0, 0, 49, 6, 1, 50, 26]]

G = adjacencyMatrixToGraph(m)
H = kruskal(G)

print sum(G.edges.values()) - sum(Gnew.edges.values())

Moderator note:

Excellent solution. Indeed, an adjacency matrix is usually not cost effective, best to use a list here.

Nicely written!

Thaddeus Abiy - 5 years, 10 months ago

Help the engineer

The answer is 2852.

1 solution

Moderator note:

0 pending reports