Complex Sorting - Multi Key

Question

I am using Python 2.6.2. I have a dictionary, graph which has tuple (source, destination) as key with a certain weight as its value.

Would like to sort graph based on source in descending order of weight. There could be more than one same source in the tuple of graph with different destination.

graph= {(2, 18): 0, (5, 13): 2, (0, 10): 2, (0, 36): 1, (3, 14): 2, (5, 23): 2, (0, 24): 1, (4, 32): 7, (2, 29): 0, (3, 27): 2, (0, 33): 2, (5, 42): 2, (5, 11): 2, (5, 39): 3, (3, 9): 8, (0, 41): 4, (5, 16): 5, (4, 17): 7, (4, 44): 7, (0, 31): 2, (5, 35): 5, (4, 30): 7}

Created an intermediary dictionary, source_dict which has source as key and accumulated weight based on source as its value, {source:weight}

source_dict={0: 12, 2: 0, 3: 12, 4: 28, 5: 21}

After doing the sort function as below,

source_desc_sort=sorted(source_dict.items(), key=lambda x: x[1], reverse=True)
sortkeys = dict((x[0], index) for index,x in enumerate(source_desc_sort))
graph_sort = sorted(graph.iteritems(), key=lambda x: sortkeys[x[0][0]])

I get a sorted graph, graph_sort as below,

graph_sort= [((4, 17), 7), ((4, 44), 7), ((4, 30), 7), ((4, 32), 7), ((5, 23), 2), ((5, 35), 5), ((5, 13), 2), ((5, 42), 2), ((5, 11), 2), ((5, 39), 3), ((5, 16), 5), ((0, 10), 2), ((0, 36), 1), ((0, 24), 1), ((0, 33), 2), ((0, 41), 4), ((0, 31), 2), ((3, 14), 2), ((3, 27), 2), ((3, 9), 8), ((2, 29), 0), ((2, 18), 0)]

If you note in graph_sort the order of keys for the same source is not important e.g for tuples with 5 as source, ((5, 23), 2) can come before ((5, 35), 5) or after eventhough the one have lower value than the other.

Now this is my challenges which I am trying to solve since 2 days ago,

Have redefined source_dict to source_dict_angle with angle as added information , {source:{angle:weight}}

source_dict_angle={0: {0: 2, 90: 4, 180: 6}, 2: {0: 0, 270: 0}, 3: {180: 4, 270: 8}, 4: {0: 7, 180: 21}, 5: {0: 6, 90: 10, 180: 2, 270: 3}}

I like to do the sorting same as above but based on angle of source. Example, the tuples with 4 as source and with destination(s) in angle 180 have to start first as it has highest value i.e 21. Followed by tuples with 5 as source and with destination(s) in angle 90 and so on.

Have intermediary dictionary, relation_graph which has position information of destination relative to source, {source:{angle:destination:value}}

relation_graph={0: {0: {32: [1], 36: [1], 23: [1], 24: [1], 16: [1]}, 90: {3: [1], 41: [1], 44: [1]}, 180: {33: [1], 10: [1], 31: [1]}}, 1: {}, 2: {0: {18: [1]}, 270: {29: [1]}}, 3: {180: {27: [1], 14: [1], 31: [1]}, 270: {0: [1], 33: [1], 36: [1], 9: [1], 1: [1], 24: [1], 41: [1], 10: [1]}}, 4: {0: {32: [1], 18: [1], 23: [1]}, 180: {0: [1], 33: [1], 44: [1], 14: [1], 15: [1], 17: [1], 21: [1], 41: [1], 27: [1], 30: [1], 31: [1]}}, 5: {0: {42: [1], 11: [1], 23: [1]}, 90: {7: [1], 8: [1], 16: [1], 35: [1]}, 180: {0: [1], 13: [1], 14: [1], 44: [1]}, 270: {1: [1], 2: [1], 39: [1], 29: [1]}}} 

Expected result

graph_sort_angle= [((4, 17), 7), ((4, 44), 7), ((4, 30), 7), ((5, 35), 5), ((5, 16), 5), ((3, 9), 8), ...

I am unable to find the solution for this as yet, I am trying to reuse the solution I have done for graph_sort but it is not working well. Have feeling I must do it different way.

Is there any way to use the same approach as I have done for graph_sort?

Appreciate if you can give me some pointers.

Will continue to work on this till then.

Additional Explanation 09 Jan 2013 9.30PM : Lennart Regebro

I would like to sort the keys of graph (tuple) based on the descending values from source_dict_angle.

graph is composed of (source, destination) but source_dict_angle only have source and angle information, {source:{angle:weight}}. It does not have destination information. We would not be able to sort the tuples from graph as we did in the first example.

We are given (not calculated) relation_graph, where we have the source, angle and destination information, {source:{angle:destination:value}} . We will use this dictionary to see which source pairs with which destination using which angle (0 deg, 90 deg, 180 deg or 270 deg).

So we will

1. First refer to source_dict_angle to know which is the highest value. In this given example, Source 4 with angle 180 degree has the highest value i.e 21

2. We compare all destination of Source 4 with angle 180 from relation_graph, i.e [0, 33, 44, 14, 15, 17, 21, 41, 27, 30, 31] if it exist in graph. If yes, we rank the (Source, Destination) tuple in first position, i.e (4, 17). This can also be done in another way, since we have to sort Source 4, we check if any of the destination of Source 4 in graph, exist in the angle 180 of Source 4 in relation_graph. If yes, we rank (Source, Destination) tuple in first position. As the same source could be paired with more than one destination using the same angle, it is possible for us to have more than one (Source, Destination) tuples. e.g (4, 17), (4, 44), and (4, 30). This means, Source 4 uses angle 180 to connect to Destination 17, Destination 44 and Destination 30, hence the 3 pair of tuples. The order between these 3 pair of tuples are not a problem.

3. Once this is done we go to the next highest value in source_dict_angle doing the above steps till all of the sources have been sorted in descending order.

Answer 1

Skip the intermediate dictionary, that's not necessary.

For sorting on the source, you just do:

graph_sort = sorted(graph.iteritems(), key=lambda x: x[0][0])

For sorting on the angle you do:

def angle(x):
   key, value = x
   source, destination = key
   return <insert angle calculation here>

graph_sort = sorted(graph.iteritems(), key=angle)

Update:

You need to stop using loads of different dictionaries to keep different data that all belongs together. Create a class for the item that keeps all the information.

From what I can gather from your question you have a dictionary of graph items which keeps source, destination and a weight. You then have another dictionary which keeps the wight, again. You then have a third dictionary that keeps the angle.

Instead just do this:

class Graph(object):
    def __init__(self, source, destination, weight, angle):
        self.source = source
        self.destination = destination
        self.weight = weight
        self.angle = angle

Your sorting problem is now trivial.