Project Euler 107: Determining the most efficient way to connect the network.

Project Euler 107: Determining the most efficient way to connect the network.

Written by on 28 July 2012

Topics: Project Euler

After the description of the disjoint set data structure (which I think you should read), it cannot come as a surprise what kind of solution we want to use for problem 107 of Project Euler. However, let as always start with the problem description:

The following undirected network consists of seven vertices and twelve edges with a total weight of 243.

The same network can be represented by the matrix below.

    ABCDEFG
A-161221---
B16--1720--
C12--28-31-
D211728-181923
E-20-18--11
F--3119--27
G---231127-

However, it is possible to optimise the network by removing some edges and still ensure that all points on the network remain connected. The network which achieves the maximum saving is shown below. It has a weight of 93, representing a saving of 243 – 93 = 150 from the original network.

Using network.txt a text file containing a network with forty vertices, and given in matrix form, find the maximum saving which can be achieved by removing redundant edges whilst ensuring that the network remains connected.

Let me say it in this way. If you know that there already exists algorithms for this kind of problem, then it is dead easy. If you don’t then I wouldn’t even know how to start. However, I was in the lucky first category. What we are trying to find is a minimum spanning tree. Which is the smallest set of vertices in a weighted graph, such that we only have one component in the graph (all vertices are connected).

There exists two algorithms which are used to find this tree; Prim’s algorithm and Kruskal’s algorithm and to me the latter seemed like the simplest one to understand and implement, so that is what I used.

From Wikipedia we have the description

  • 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 F is not yet spanning
    • remove an edge with minimum weight from S
    • if that edge connects two different trees, then add it to the forest, combining two trees into a single tree
    • otherwise discard that edge.

At the termination of the algorithm, the forest has only one component and forms a minimum spanning tree of the graph.

So all we need now is to implement the algorithm and the input reading around it. Oh… and not least figure out that we should find the saving not the cost of the minimum spanning tree. That took me 10 minutes of debugging.

Using the disjoint data set class we just covered the code looks like

//Read the input file
string[] lines = File.ReadAllLines(filename);

//create a forest F (a set of trees),
//where each vertex in the graph is a separate tree
int N = lines[0].Split(',').Length;
DisjointSet vertices = new DisjointSet(N);

//create a set S containing all the edges in the graph
//The tuple contains weight,vertex, vertex
List<Tuple<int, int, int>> edges = new List<Tuple<int, int, int>>();
int initialWeight = 0;

for(int i = 0; i < N; i++){
    string[] edge = lines[i].Split(',');

    for (int j = 0; j < i; j++) {
        if (edge[j] != "-") {
            int weight = Convert.ToInt32(edge[j]);
            edges.Add(new Tuple<int,int,int>(weight,i,j));
            initialWeight += weight;
        }
    }
}

//Sort edges to have the minimum weight at top
edges.Sort();
int k = 0;

//while S is nonempty and F is not yet spanning
int minSpanningTreeWeight = 0;
//while(!vertices.isSpanning()){
while (!vertices.isSpanning()) {
    //remove an edge with minimum weight from S
    //Since we have a sorted list we just go through the list

    //if that edge connects two different trees,
    //then add it to the forest,
    //combining two trees into a single tree
    if(vertices.Find(edges[k].Item2) != vertices.Find(edges[k].Item3)){
        vertices.Union(edges[k].Item2, edges[k].Item3);
        minSpanningTreeWeight += edges[k].Item1;
    }
    k++;
}

Then what remains is to subtract the weight of the spanning tree from the weight of the original graph and we have the following solution (click to see the solution)

The saving is 259679

which runs in

Solution took 2,4353 ms

Wrapping up

Once you figure out that there are indeed algorithms for this kind of stuff the problem is reduced to something which is a matter of implementation. Something which should be trivial, but I often find myself struggling to find the right way to code the algorithms and data structures. In this problem I had help with the Disjoint-set data structure and that made it almost trivial.

The full source code can be found here.

How did you solve this problem?

5 Comments For This Post I'd Love to Hear Yours!

  1. Scott says:

    I’m solving it using Prim’s Minimal Spanning Tree Algorithm. It’s not working yet though (implementation issues . . . ).

  2. Chintan says:

    I have been using the Kruskal’s algorithm too but I’m getting 259671 as the answer.It shows the total weight to be 261832 which seems to be correct.If you could post the weights of the edges in the MST,it would be easier for me to check my error! :)

    Lang:C++

  3. Kristian says:

    I could do that, but there are a pretty lot of them (513), so would you mind me mailing them to you instead? And what format would you like them in?

  4. Chintan says:

    Yes sure!You can mail them to me,I don’t mind them at all!
    And I don’t know C# so a C/C++ code to print them or a text file containing them or even if you paste them in the body,anything would be fine!

  5. Bilbo says:

    Can you repost the input file network.txt. The link seems to be broken.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.