Minimum Spanning Tree with Kruskal Algorithm

Kruskal pondered upon the string artwork put up on the wall years ago by his dad when he was just ten. The strings were pure solid gold wires, bright and deep golden color. The pegs were precious gemstones, of bluish tone, with intricate carving, hand carved by his dad when the old man was still alive.

Fortune reversed since his dad passing away, and he needed the wires now, just the wires for him and his younger brother to get through the months to come. He could not take away the peg, and he needed to ensure that all the pegs were always interconnected by the wires, a strange precondition set by his dad, a famed astrologist. If any of the pegs was removed or disconnected, worst fate would await them, his dad had warned. The current misfortune -  a shortage of money - was to be thought off as just a temporary malady, to be weathered, mild in comparison to the tone of that threat.

He stared for long minutes, at the intricate heritance, his stare accompanied by hopeless resign at his financial situation. No, he must sell it - the whole thing -, he thought. But then, that would a clear violation of his dad's will, and even though the man was no longer around, his words bore eternal weight upon Kruskal.

And so he racked and shook his brain, trying his utmost best to think out of his hollow box. And finally, yes, he thought of something.. why not take some of the wires out, maintaining just a minimal set of wires that interconnect the pegs.

Kruskal noted down in his book of ideas (his notebook) the list of pegs he had to maintain. His goal would be to find the minimal set of wires that interconnect all of the pegs - none of the pegs should be isolated from the rest. He put each peg in its own set (marked by the curly brackets); in other words, initially, each was isolated from all others. They were like trees, he thought, those pegs. But now they were separate trees, each an individual tree oblivious, unconnected to the other.

So the question now is: which wire should he consider first to maintain in the artifact?  He went for the cheapest one - the one with the shortest length. That will be CD, with a length of 3, endpoints at C and D. 

C and D now are a single brunch of trees, kind of a poly-embryonic variation.

Kruskal went on now to select another wire, choosing the next shortest one. That would be GE, the length of which is 4.

G and E now in the same set, replanted to the same pot.

He went on to choose the next shortest edge, taking care not to select an edge that would form a cycle with edges already selected. A cycle - an interconnection that goes around in a loop - would imply an excess wire; there should be none, for he needed every wire that he can salvage. BC now selected.  

Followed next by GD.

Then FE.

His forest now looks as follows, with 5 trees now in the same pot - those interconnected pegs.

He added one more edge, AB, and it's done. He looked at the set of wires that he had set to be maintained on the artifact: AB, BC, CD, DG, GE and FE, the total length of which would be 6 plus 5 plus 3 plus 5 plus 4 plus 5 equals to 28. He looked harder at the artifact. Is there any other possibility? A lesser set of wires that maintain the connectivity of the pegs.

It seemed to him there's none. He had found the minimum spanning tree for the original graph he was given, a set of links that covered all the pegs with no cycle, and with a minimal total length.

Bellman Ford Shortest Path Algorithm

"How to I get from A to other locations?", the Old Man pondered as he fingered the edges in the graph..

He took out his pen, a gift that's still alive from his long-dead spouse, and with a shaking hand, note down the list of roads, or paths or edges, in the graph, with number in brackets denoting the distance of a particular edge.

Those roads - they formed his walking paths, his daily morning routine. He would go to different sites each day from A his home: B a fountain in town, C his favorite restaurant, D the library, E his doctor. And F, his favorite spot in the town's botanical garden. He could not go too far, could not afford a route longer than it should be, as age had shown its effect, imparting laziness and a lesser resolve in him. He would like, not that he really needed, to know the distances from A to each of the other sites. For convenient record keeping, he drew out the following table, the entries for which would be the min distances.

At this time, sleepiness bore upon him. He could not go further. All he knew at the moment is that the distance from A to A is 0; for the rest, he assumed for a start a distance of infinity:

Sleep.

zzzz...

Awake.

Back to his table.

He looked at the list of edges: AB (6), BC(6) and so on...

He starts with AB(6).

The length of AB is 6, and the distance up to A, as noted in the table is 0.

It means that the distance up to B via A is 0 + 6 = 6.

Old Man smiled, gleefully showing the gaps in his teeth, as he updated his table.

On to the next edge, BC (6).

The distance at B is 6, and the distance from B to C is 6.

That added up to 12.

Another update to the table.

Old Man processed the next edge AF (5) in the same way.

He made further update to the table.

Now on to FB (5).

Distance up to F is 5, and the length of FB is 5.

It means that the distance to B via F is 5 + 5 equals to 10, right?

The Old Man wrinkled his wrinkles.

His mind blurry, as he tried to remember his thoughts.

He paused for a toilet break.

And he remembered he had yet to take his breakfast.

And while doing his business in the toilet, he remembered what he was trying to remember.

And it occurred to him.

He rushed out, oblivious to his nakedness and the open window.

If the distance to B via F is 10, and the distance at B is currently indicated as 6 in the table, then of course... of course, it means that there is no need for any update to the table.

The value currently stored in the table is better than the new one.

And so he maintained his table.

FB (5) left no mark on the table.

A different story with FC (6).

The distance up to F is 5, and the distance of FC is 6.

That totals up to 11, which is better than the 12 current indicated for C.

Old Man updated the table for C.

Another update in the table, this time for D.

From infinity to 12.

No go for DC (9).

It doesn't change anything.

Late morning, Old Man was done with all the edges.

He's hungry, but he wandered if he needed to repeat the steps.

Looking at the graph, eyeballing the distance, he noted that his outcome was indeed correct.

Still..

After lunch, he settled in to another possibility.

What if, he pondered, he got something like as follows:

He considered the list of edges to be as per the following order:

After considering all the edges, as per the sequence above, he obtained the following values in his table:

He needed to repeat.

Repeat he did, obtaining the following:

Another round, and he obtained the following:

Doing it again and again, for a total number of iterations of 5, he finally obtained the solution:

It seemed to him that a total of N-1 iterations is needed for his calculation approach to work, N being the number of nodes or sites.

Late evening, and he's yet to start his walk.

He's still thinking.

What if there are negative numbers on his edges?

Negative edges?

Negative numbers you mean? He thought, chuckling as he imagine what his wife would have said were she still to be alive.

But if the numbers were to represent some kind of points or merits or toll charges on the road, it would be realistic.

It's late in the evening. He has to retire.

He will sleep on his problems, now problems far removed from his original intent of simply calculating his walking distances.

Will his approach work for a graph with negative weights?

What if there is a cycle with negative total weights in the graph?

Can his approach deals with such?

Minimum Spanning Tree - Prim's Algorithm

"We are to prepare a proposal, a railway network proposal for the new government", bellowed the Head of the Logistic Department, a minute figure of a man.

Asha gazed at the map, a map of Bhutan, her team of engineers flanking her.

(copyright: http://www.bhutanyontentours.com/bhutan/47-2/)

As the chief engineer, she bore the the burden of leading the effort on the technical side. So the weight of Bellman's bellowing fell upon her. Bellman made neither a speech nor any further elaboration other than that the network needs to cover the 8 most major cities in Bhutan. He promised to come back the next morning to receive an update, a promise that was more like a threat than a promise to Asha and her team.

"So how do we do it?", grumbled Kavi, scratching his round beard. "Think of something", retorted Asha. She was drawing on a white board a layout of the cities listed by Bellman. No names, just numbers for each of the cities - from 0 to  7. Asha knew the places; in fact, she had been there, experienced the life there, as an expatriate engineer. But being a well-engineered engineer, she preferred numbers of course. Cities were dots on the drawing and an edge drawn between cities where Asha deemed a rail is feasible, given her knowledge of the terrain and distance.  Numbers on the edges denoted distances in hundred of kilometers.

"We can't enumerate all possible rail networks, right?", Moses interjected. One of the senior engineers in the team, he was twiddling his pen like a kerambit as he studied Asha's drawing. "No, we can't", said Asha matter-of-factly, apparently unimpressed with the slight hint of algorithmic awareness in her team. She already knew there would be too many, a factorial number of possibilities if they were to work that way.

A solution started to shape in her head, clouded though it was as she gazed hard at the board. "What if we start here", she said, pointing to node 0. "It's not a path we are looking at, Asha", said Moses, "We don't have a starting point".  Asha glared at him. "Yes, I know", she rebuked. "What I am saying is that .. what I want is to consider 0 as the only node in our network of road.", she said. She paraded her idea - assume that 0 to be the starting network of roads - a trivial start of course, one with only one city and no rail. Then progressively add the city closest to the network.

So we start from 0. 

0 is the only city now in our minimal network of connected cities, M.

What's the nearest city to the network?

It's 1, right?

What's next?

Now, note that we have 2 cities now in our network, M.

So the next nearest may be nearest with respect to its distance to either 0 or 1.

That's going to be 7, right?

Let's go on.

What's nearest to the network now?

3, right?

Now, 2.

As you can see here.

Then 5.

Are you getting it?

And so on and so forth.

Asha completed her network, an air of triumph about her, an air of awe enveloping everyone else. None others, except for maybe Moses, understood really how it could work, but it did work. Nothing else they can offer could beat the network derived by Asha in terms of distance.

"That's a good one, Asha", said Kavi, still rubbing his beard. "What shall we call it, this network?" 

"Minimum Spanning Tree", quipped Asha.  "The algorithm?", asked someone else.  "Shall it have a name?" 

Prim's Algorithm. 

The Python code

# assume

#cities = a list of points

#graph = the adjacency matrix

#vertices = number of cities

    

# initialize the MST and the set X

T = {}

X = {}

# select an arbitrary vertex to begin with

X.add(0)

while len(X) != vertices:

    crossing = set()   # a set object

    

    # for each element x in X, add the edge (x, k) to crossing if

    # k is not in X

    for x in X: 

        for k in range(vertices):   

            if k not in X and graph[x][k] > 0:

                crossing.add((x, k))    # the possible edges

                

                

    # find the edge with the smallest weight in crossing

    edge = sorted(crossing, key=lambda e:graph[e[0]][e[1]])[0]

    # add this edge to T

    T.add(edge)

    # add the new vertex to X

    X.add(edge[1])

# print the edges of the MST

for edge in T:

    print(edge)

Dynamic Programming for TSP

What is the meaning of a shortest path? Ahsan ponders...

A shortest path that starts from A and ends at A, through B and C and D and E and F and G.

But sequence between A and A doesn't have to be B to C to D to E to F to G. 

Does it really have to end in G, before coming back to A?

No.

Maybe, it ends in B or C or D or E or F, before coming back to A.

It depends on which would lead to the shortest distance.

Let's think again: what are we looking for?

Aside from A, we have a set of cities S = {B,C,D,E,F,G}

We are looking for the overall cost of a path that starts at A and visits each village in the set {B,C,D,E,F,G} before coming back to A.

Let cost(S) be the cost of traveling from A to the cities in S, before coming to A.

If B is the last city to be visited before coming back to A, then

cost(S) = cost(S - B) + dist(B, A) 

Here, cost(S-B) is the cost of traveling from A to the cities in S-B, before coming to B.

If C is the last city to be visited before coming back to A, then

cost(S) = cost(S - C) + dist(C, A) 

And so on..

The question is which city should be the last before coming back to A.

I can write it all as follows, the sequence of cities to be visited, Ahsan thinks... 

The blanks are to be decided..

I need to think the best path that ends in G before coming to A.

The best path that ends in F before coming to A.

ends in E before coming to A.

and so on.

Surely we need to pick the one that will result in with the minimum cost, he strains his head.

In other words, 

cost(S) = minimum among the following:

•                          cost(S - B) + dist(B, A) 
•                          cost(S - C) + dist(C, A)
•                          cost(S - D) + dist(D, A) 
•                          cost(S - E) + dist(E, A)
•                          cost(S - F) + dist(F, A)
•                          cost(S - G) + dist(G, A)

What's in there, the above? 

dist(B, A) is, of course, the distance from B back to A. 

dist(C, A) from C to A.

And so on.

Ahsan focuses on one of the cost values above..

What's cost(S-G)? 

S-G means the set S with G as the last node.

cost(S-G) would then mean a minimum-cost path that starts from A and covers every node in S-{G} once before coming to G.

So what is this value... cost(S-G)?

The path may end in B before going on to G.

The path may end in C before going on to G.

Or it may end in D before coming to G.

Or in E.

Or in F...

Or in G...

In other words, Ahsan articulates: 

cost(S-G) = minimum among the following:

•                          cost(S - G - B) + dist(B, G)
•                          cost(S - G - C) + dist(C, G) 
•                          cost(S - G - D) + dist(D, G)
•                          cost(S - G - E) + dist(E, G) 
•                          cost(S - G - F) + dist(F, G)

or maybe i should write it in this way.. he squibbles

•                          cost(S - {G, B}) + dist(B, G)
•                          cost(S - {G, C}) + dist(C, G) 
•                          cost(S - {G, D}) + dist(D, G)
•                          cost(S - {G, E}) + dist(E, G) 
•                          cost(S - {G, F}) + dist(F, G)

what am i doing here...

Ahsan glances at the clock.. it's past midnight.

I'm calculating the shortest path for the case whereby we start from A, and the last city before returning back to A is G.

So I have to consider the case where the path before G ends in B.

or ends in C.

or D..

or E..

or F.

and if you consider the path that ends in B...then we have as follows

All for the sake of finding cost(S - {G, B}), you need the minimum of:

•                          cost(S - {G, B, C}) + dist(C, B)
•                          cost(S - {G, B, D}) + dist(D, B) 
•                          cost(S - {G, B, E}) + dist(E, B)
•                          cost(S - {G, B, F}) + dist(F, B) 

And if you consider the first option, you will need to calculate cost(S - {G, B, C}).

Which is the minimum of

• cost(S - {G, B, C, D}) + dist(D, C) 
• cost(S - {G, B, C, E}) + dist(E, C)
• cost(S - {G, B, C, F}) + dist(F, C)

You will just keep continuing, right?

Recursively.. 

To compute  cost(S - {G, B, C, D}), you would need the minimum of 

• cost(S - {G, B, C, D, E}) + dist(E, D) 
• cost(S - {G, B, C, D, F}) + dist(F, D)

We are going recursively... 

At each recursive iteration, we look for the subpath with the smallest distance...

Ahsan beams with delight.

It all seems set then.

TSP can be solved recursively.

Is it better than a plain brute force method though? 

No.. same number of evaluations eventually.

Same number of possibilities...

He moans..

So no advantage..

No, just cleaner implementation probably.

But wait..

Are there repetitions in the recursive calculations?

Clearer if we put it in the form of a tree diagram, he thinks..

At a certain level, there will start to be duplicated computations.

You can see it above.

cost(S-{B,D,E,F}) is the cost for a set in that goes from A, traversing elements in a set that excludes B, D and E, and then coming to F followed by E.

cost(S-{D,B,E,F}) is the cost for a set in that goes from A, traversing elements in a set that excludes B, D and E, then coming to F followed by E.

To fix this repetitions, to eliminate it, we can do as follows: just do it all bottom up.

The fancy name for this: dynamic programming.

It's just recursion turned upside down..

A Sketch of the Python Code

What code I have largely a simplification of the one in https://gist.github.com/mlalevic/6222750.

Suppose we have cities with the following coordinates:

[[3.0, 3.0], [4.0, 5.0], [6.0, 9.0], [0.0, 7.0], [9.0, 9.0], [3.0, 10.0]]

The adjacency matrix, let's name the variable as all_distances, can be derived to be as follows (just use calculator or worksheet or punch in a simple python code :-):

[[ 0.          2.236     6.708     5.          8.485    7.        ]

 [ 2.236    0.           4.472     4.472    6.403    5.099  ]

 [ 6.708    4.472     0.           6.324    3.          3.162  ]

 [ 5.          4.472     6.324     0.          9.220    4.243  ]

 [ 8.485    6.403     3.           9.220    0.          6.083  ]

 [ 7.          5.099     3.162     4.243    6.083    0.        ]]

So how will the dynamic programming work..

First build all subsets of size 2, with each starting from city 0 - whatever your first city 

In our case here, it is [3.0, 3.0].

Build the list of subsets as a dictionary (https://www.tutorialspoint.com/python/python_dictionary.htm), the key being a tuple of the form:  (subset, last_node)

and the value being a tuple of the form: (distance, path)

So the dictionary will be of the form:

{ (subset, last_node): (distance, path),  (subset, last_node): (distance, path), ... }

In more details..

You already have an adjacency matrix, all_distances.

Initialize a blank dictionary A

  A = {}

Iterate through the distances from 0 as follows, using enumerate (http://book.pythontips.com/en/latest/enumerate.html)

  for idx,dist in enumerate(all_distances[0][1:]):

The pairs of idx and dist produced by the loop will be the following:

0 , 2.23606798

1 , 6.70820393

2 , 5.0

3 , 8.48528137

4 , 7.0

Each time in the loop, create a set (Python frozenset: https://www.programiz.com/python-programming/methods/built-in/frozenset), 

        subset = frozenset([0, idx+1])

Each set will just be of the form {0, index}. 

In the code, index is idx + 1, since we want the index to start at 1, not 0 (that's the source).

The last city in the set is just idx+1

        lastCity = idx+1 

The path involves just 2 nodes, 0 and idx+1.

        thePath = [0,idx+1]

Now build a dictionary entry for A:

        A[(subset, lastCity)] = (dist, thePath)

 The overall initial code as follows:

  A = {}

  for idx,dist in enumerate(all_distances[0][1:]):

        subset = frozenset([0, idx+1])

        lastCity = idx+1 

        thePath = [0,idx+1]

        A[(subset, lastCity)] = (dist, thePath)

Your A will be as follows:

{

   (frozenset({0, 1}), 1): (2.236, [0, 1]), 

   (frozenset({0, 2}), 2): (6.708, [0, 2]), 

   (frozenset({0, 3}), 3): (5.0, [0, 3]), 

   (frozenset({0, 4}), 4): (8.485, [0, 4]), 

   (frozenset({0, 5}), 5): (7.0, [0, 5])

}

Now we are going to incrementally build larger paths..

Loop for subset size m (not including the starting point 0) ranging from 2 to the # cities:

  for m in range(2, numcities):

For each subset size, initialize a blank dictionary B:

        B = {}

B is going to be our new dictionary, containing paths longer by one at each iteration. 

Now create combinations of size m.

We make use of the itertools package (https://docs.python.org/2/library/itertools.html).

        for C in itertools.combinations(range(1, numcities), m):

Let S be the combination C with the starting city (0) appended to the front.              

             S = frozenset(C) | {0}

At m = 2, S will be the following:

frozenset({0, 1, 2})

frozenset({0, 1, 3})

frozenset({0, 1, 4})

frozenset({0, 1, 5})

frozenset({0, 2, 3})

frozenset({0, 2, 4})

frozenset({0, 2, 5})

frozenset({0, 3, 4})

frozenset({0, 3, 5})

frozenset({0, 4, 5})

For each of the combinations above, we are going to find the best sequence..

We shall try sequences ending in every possible city

To do this, iterate over the cities in S, minus the starting city

             for j in S - {0}:

   

At each iteration, we are to build a list containing all path ending in the city

                  temp_list = []

For every other city in S, not including 0 and j (the city currently being considered)

                  for k in S:

                        if k != 0 and k!=j:   # for each k which is not 0 and not j

Consider what was the best path (and its distance) that did not include j (the current city), and which ended in k.

How to do this?!

Make use of A !

                               prevSubsetVal = A[(S-{j}, k)]

                               kLastDistPrev = prevSubsetVal[0]

                               kLastPathPrev = prevSubsetVal[1]

Append j to that path.

And add up the cost.

That becomes ur tuple, temp.

                               temp = (kLastDistPrev + all_distances[k][j], kLastPathPrev + [j])

Build up a list containing every path ending in j

                               temp_list.append(temp)

Now you can find the min among all combination ending in j

Find that and put the min in the new cost dictionary, B

                 B[(S, j)] = min(temp_list)

When you are done with computing subsets of size m, update A

        A = B

Here's the overall code up to this stage:

    cnt = len(all_distances)    

    for m in range(2, cnt):

        print('****')

        print ('the subset size, m, is ', m)

        B = {}

        for C in itertools.combinations(range(1, cnt), m):

            S = frozenset(C) | {0}

            print('S is ', S)

            

            # consider subsets ending in j

            for j in S - {0}:

                print('considering subset S of size ', m, ' ending in ',j)

                temp_list = []

                for k in S:

                    if k != 0 and k!=j:

                        prevSubsetVal = A[(S-{j}, k)]

                        kLastDistPrev = prevSubsetVal[0]

                        kLastPathPrev = prevSubsetVal[1]

                        temp = (kLastDistPrev + all_distances[k][j], kLastPathPrev + [j])

                        temp_list.append(temp)

            

                print('Look for min in ', temp_list)

                B[(S, j)] = min(temp_list)  

                print('Adding subsets ending at j = ', j, ' gives you B =', B)

        A = B

        print('A, now containing subset of sizes ', m, ' is ', A)

And when you are done up to the final subset size....

We can list out the final possible paths ...
    final_list = []

To build this list, iterate over the keys in A

Remember, in A,  a key is of the form: (subset, last_node)

and the value: (distance, path)

    for d in iter(A):

Add up distance for the last leg (from last visited node to the starting node):

        entry = (A[d][0] + all_distances[0][d[1]], A[d][1])

Append (distance, path) to final_list
        final_list.append(entry)

Take the minimum among the possible paths:
    res = min(final_list)

Job done