sort(cmp=func)

[Tobiah]

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?

Thanks

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

[Daniel Fetchinson]

Re: sort(cmp=func)

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.

Cheers,
Daniel
--
Psss, psss, put it down! - http://www.cafepress.com/putitdown

[David Wahler]

Re: sort(cmp=func)

On Wed, Jul 9, 2008 at 10:58 PM, Daniel Fetchinson
<fetchinson@goo glemail.comwrot e:

>

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

Presumably what the OP really wants is to sort using the transitive
closure of dep_cmp, which is a topological sort.

http://en.wikipedia.org/wiki/Topological_sorting has details and a
linear-time algorithm.

-- David

[norseman]

Re: sort(cmp=func)


Tobiah 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?
>
Thanks
>
Tobiah
** Posted from http://www.teranews.com **
--

http://mail.python.org/mailman/listinfo/python-list

>

=============== =============== ====

If you are running Linux take a look at
/lib/modules/[kernel-ver]/modules.dep

In other words, to create a list like:
this module: depends on these
module-a module-f, module-g

copy ALL modules to a scratch directory
ls -1 | sort >file.lst
(or dir /b/l | sort >file.lst)
concept:
#outer loop
get a filename from file.lst
create a list of all imports in it
compare filename, in turn, to each line in file
if it finds itself loop
#inner loop
otherwise open module and create 2nd list of all imports in this file
compare each item in list one to each item in list two and output
one line for each match to imports1.lst, format:
module name needing, module name wanted (filenames not def names)

#outer loop2
get a line from dep1.lst
parse to f1=first-name, f2=second-name
create list of imports for f2
#inner loop2
check each import of f2 against name of f1
if there is a match, print Circular conflict with: f1 and f2 to
problems.lst

A sort on second filename on line combined with a visual inspection will
often help point out any 3-way (or more) circulars.
(a needs b needs c needs a) No guarantees, though.

You will have to resolve circulars yourself. Usually involves changing
code. If A needs output from B to run and B needs output from A to run
you have an obvious circular. Rewrite/fix the code.

Perhaps make a lib file of all the imports for the project. (Which is
the preferred practice.) Load it with the main logic. Thus none will be
run until all are present. Then eliminate whatever circular nonsense
still exists...

If problems.lst is empty all that needs to be done is for each import to
check the dep1.lst and first load the second filename on the line for
each first-name matching module wanted. For a given first filename not
being in a circular, manual ordering of the dep1.lst can be done if
needed. (Perhaps f1,a1:f1,b1:f1, c1 needs to be f1,c1:f1,a1:f1, b1 ?
Simply because descriptive alpha name sort winds up being wrong load
sequence.)

Just because a piece of code can be reused does not mean it is
generically practical to do so. The why of this is your current problem.

My first reaction to your original post is that you inherited something
and are setting about cleaning it up so you can work on it.


Best of luck. Succeed and you get to claim another T-shirt. :)


Steve
norseman@hughes .net

[Tobiah]

Re: sort(cmp=func)

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
>relationship s 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(table s)):
this_table = tables[this_index]
for prev_index in range(this_inde x):
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 **