sort(cmp=func)

Tobiah toby at tobiah.org
Thu Jul 10 21:03:06 CEST 2008

```On Wed, 09 Jul 2008 20:58:32 -0700, Daniel Fetchinson wrote:

>> I have a list of objects that generate code.  Some
>> of them depend on others being listed first, to
>> satisfy dependencies of others.
>>
>> I wrote a cmp function something like this:
>>
>> def dep_cmp(ob1, ob2):
>>
>> 	if ob1.name in ob2.deps:
>> 		return -1
>> 	else:
>> 		return 1
>>
>> I also tried returning 0 when there were no dependency
>> relationships between the objects.
>>
>> This failed, because every object was not compared with
>> ever other.  I imagine that this is because sort assumes
>> that if a > b and b > c, then a > c.  In my case, this
>> isn't really true.  If a is not dependent on b, and
>> b is not dependent on c, that doesn't mean that a is not
>> dependent on c.
>>
>> Is there a better way?
>
> definition of "<" is transitive. I.e. a < b and b < c should imply a <
> c. If this is not satisfied, it doesn't make sense to sort according
> to your "<" definition. It's just not a well-defined operation and no
> trick will make it work.

There is a meaningful relationship here however.  Basically, some
items must precede some other items.  There are more than one
correct orders however.  Here was my eventual solution. I had to
compare each item with each other item, swapping on failed
dependencies.  Recursion simplified this greatly:

def dep_sort(tables):

for this_index in range(len(tables)):
this_table = tables[this_index]
for prev_index in range(this_index):
prev_table = tables[prev_index]
if this_table.name in prev_table.deps:
tables[prev_index] = this_table
tables[this_index] = prev_table
dep_sort(tables)
return

** Posted from http://www.teranews.com **

```