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?
>
> It's only meaningful to talk about sorting if your particular
> 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 **
--
http://mail.python.org/mailman/listinfo/python-list
