On Wed, Jul 9, 2008 at 10:58 PM, Daniel Fetchinson <[EMAIL PROTECTED]> 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. >
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 -- http://mail.python.org/mailman/listinfo/python-list
