CODEWITHSUNDEEP
python-3.xalgorithmsortinggraph
Abrar
Abrar

Reputation: 7222

Sorting nodes of a undirected graph based on value in Python

I am relatively new to Python. I wrote this code in Python (3.x) to solve a problem which involves an undirected graph.

The expected output of the program should print the node which occurs in the kth position from the list of neighbouring nodes of after they are sorted in descending order (based on the value of the node) but if two values are same then the node which comes first when sorted in ascending order of their indices is printed.

If no such node exists then -1 is printed.

n, m, k = input().strip().split(' ')
n, m, k = [int(n), int(m), int(k)]

node_values = list(map(int, input().split(' ')))
d = {}
for i in range(n+1):
    d[i] = []

for i in range(m):
    x, y = input().strip().split(' ')
    x, y = [int(x), int(y)]
    d[x].append(y)
    d[y].append(x)

for key, value in d.items():
    if key != 0:
        if k <= len(value):
            new_list = sorted(value, key=lambda x: node_values[x-1], reverse=True)
            print(new_list[k-1])
        else:
            print(-1)

Here, I am sorting using sort(), providing the key as the value from node_values. But I am confused about adding the second condition (if the values are same then sort them according to the ascending order of their indices).

What am I doing wrong here? Also is it a better choice to use a parallel list for representing the graph over using dictionary?

Upvotes: 0

Views: 934

Answers (1)

T.Lucas
T.Lucas

Reputation: 848

The lambda function used to sort can return a tuple, which in your case would be formed as the node values and the index of the node. 

sorted(value, key=lambda x: (node_values[x-1], x), reverse=True)

But you want a different order: descending for the node values and ascending for the indices. This can be achieved by sorting in descending order the negative value of the indices: x<y => -y < -x. So you can use this lamba function:

sorted(value, key=lambda x: (node_values[x-1], -x), reverse=True)

I assumed 'x' is the index of your node but this is not really clear for me.

Upvotes: 1

Related Questions