CODEWITHSUNDEEP
pythonsortingminimum-spanning-treeprims-algorithm
Any NOUS
Any NOUS

Reputation: 65

Alternative to this python code?

I have a line of code from class that I don't understand fully and want some easier alternative to. What this does is , uses weightList, which is a list of edges that's connected to each other, and returns the edgelists with lowest corresponding value from the graph (adjacency matrix). This is for a Prim's Minimum Spanning Tree problem.

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

Upvotes: 0

Views: 132

Answers (4)

Vincent Savard
Vincent Savard

Reputation: 35907

Do exactly as you said: for all edges, find the value in the graph which is the lowest.

i, j = current_edge = weightList[0]
current_min = graph[i][j]

for edge in weightList[1:]:
    i, j = edge

    if graph[i][j] < current_min:
        current_min = graph[i][j]
        current_edge = edge

You start with the first edge from your weightList, then you iterate on all other edges to try and find a value which is lower. When you exit the loop, current_edge is the edge with the lowest value.

That being said, it might be worth instead to try and understand your code. I assume you know what sorted does. To sort your weightList, sorted uses the parameter key, which is a function that returns a value. In your case, your function returns the value in graph at the position of your edge. sorted will use this value to compare the edges together.

Thus, this will sort all your edges from the one with the lowest value to the one with the highest value. Then, once it is sorted, you take the first element, which is the edge with the lowest value.

Algorithmically, using sorted for this job isn't a great idea since it has a time complexity of O(n log n). In comparison, my algorithm is O(n) (but probably slower because I assume sorted is implemented in C). Instead, you can obtain the same result in O(n) using standard functions by using min, which certainly is the most efficient and readable option out of all three:

edge = min(weightList, key=lambda (i,j): graph[i][j])

Upvotes: 0

gregbert
gregbert

Reputation: 446

When trying to reduce complexity, I always look for ways to break things out into self explanatory, modular functions:

def distance(adjacency_matrix, start_node, end_node):
    return adjacency_matrix[start_node][end_node]

sorted_edges = sorted(weightList, key=lambda e: distance(graph, e[0], e[1]))
edge = sorted_edges[0];

Upvotes: 0

TripleD
TripleD

Reputation: 339

If you want the code to be a little less "compact", this should do the trick:

shortest = weightList[0]

for edge in weightList:
    if graph[edge[0]][edge[1]] < graph[shortest[0]][shortest[1]]:
        shortest = edge

Set the shortest edge to be equal to the first edge in the weightList, then go through the list and see if any edges are shorter.

Upvotes: 0

qfwfq
qfwfq

Reputation: 2516

Breaking it up a little bit could be enough. How about this? 

get_edge_weight = lambda e: graph[e[0]][e[1]]
sorted_weights = sorted(weightList, key=get_edge_weight)
edge = sorted_weights[0]

Upvotes: 2

Related Questions