Complex Sorting - Multi Key
<p>I am using Python 2.6.2. I have a dictionary, <code>graph</code> which has tuple (source, destination) as key with a certain weight as its value.</p>

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

<pre><code>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}
</code></pre>

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

<pre><code>source_dict={0: 12, 2: 0, 3: 12, 4: 28, 5: 21}
</code></pre>

<p>After doing the sort function as below, </p>

<pre><code>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]])
</code></pre>

<p>I get a sorted graph, <code>graph_sort</code> as below,    </p>

<pre><code>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)]
</code></pre>

<p>If you note in <code>graph_sort</code> 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.</p>

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

<p>Have redefined <code>source_dict</code> to <code>source_dict_angle</code> with angle as added information , {source:{angle:weight}}</p>

<pre><code>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}}
</code></pre>

<p>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.</p>

<p>Have intermediary dictionary, <code>relation_graph</code> which has position information of destination relative to source, {source:{angle:destination:value}}</p>

<pre><code>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]}}} 
</code></pre>

<p>Expected result</p>

<pre><code>graph_sort_angle= [((4, 17), 7), ((4, 44), 7), ((4, 30), 7), ((5, 35), 5), ((5, 16), 5), ((3, 9), 8), ...
</code></pre>

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

<p>Is there any way to use the same approach as I have done for <code>graph_sort</code>?</p>

<p>Appreciate if you can give me some pointers. </p>

<p>Will continue to work on this till then.</p>

<p><strong>Additional Explanation 09 Jan 2013 9.30PM : Lennart Regebro</strong> </p>

<p>I would like to sort the keys of <code>graph</code> (tuple) based on the descending values from <code>source_dict_angle</code>.</p>

<p><code>graph</code> is composed of (source, destination) but <code>source_dict_angle</code> 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 <code>graph</code> as we did in the first example.</p>

<p>We are given (not calculated) <code>relation_graph</code>, 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).</p>

<p>So we will </p>

<ol>
<li><p>First refer to <code>source_dict_angle</code> to know which is the highest value.
In this given example, Source 4 with angle 180 degree has the highest value i.e 21</p></li>
<li><p>We compare all destination of Source 4 with angle 180 from <code>relation_graph</code>, i.e [0, 33, 44, 14, 15, 17, 21, 41, 27, 30, 31] if it exist in <code>graph</code>. 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 <code>graph</code>, exist in the angle 180 of Source 4 in <code>relation_graph</code>. 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.</p></li>
<li><p>Once this is done we go to the next highest value in <code>source_dict_angle</code> doing the above steps till all of the sources have been sorted in descending order.</p></li>
</ol>
