algorithm for depending Elements

I just plainly hate algorithm that should be perfect, but the perfect solutions I come up with sre memory or runtime hungry like doom3 or even worse.
So this time it's about Elements that have dependencies like Linux Packages. So e.g 9 depends on 3 and 6, 3 depends on 6 and 1, etc. Now that I got those conditions I have to find out ALL possible orders in which I could install those Packages. I know that e.g. aptitude solves dependencies, but the packages where only an example.
So is there an perfect algorithm for this Problem and if not I'm sure this Problem has a name in theoretic  computer science.
Please /prog/ be my hero.

Forget it, it's NP-complete.

MRP

>>2

No it's not, 'tard

>>2
r u shure??

>>4
Sorry it is, read page 612 of the "intro to algos" by Ron Rivest for the explaination.

Graph theory, topological order(s).

Build a tree, faggot.

>>8

ANGRY COMPSCI STUDENT STRIKES AGAIN!

>>8
WTF?! Didn't you notice that in my example there are multiple dependencies on same element as well as Dependencies shared by more than one Element.
How the fuck am I supposed to build a non-repeating tree with that easily? Even if I sort out the double Elements, still following the branches alone won't give me all orders.
I would value your advice if you would've said it a little nicer. If you want to insult me, at least think about what you say.

Well doesn't matter anymore, I've just written a method which just produces all combinations possible and then checks if they work with the dependencies. The time and memory usage is horrible but acceptable for the low amount of elements given.

>>10
Are you saying there are recursive dependencies in your dataset?

>>11
He means his dependency graph looks like this:     b
    / \
   /   \
  /     \
 a       d
  \     /
   \   /
    \ /
     cWhere all arrows are pointing to the left (which I wouldn't need to say if there were an easy way of drawing arrow heads in ascii).

So it's not technically a tree. But I can't see why that should be a problem.

Ah fuck they changed the way the code tag works.

>>12

Ah, yes, that's what I was thinking of (circular dependency, not recursive).

I take it it's not for a package manager then.

Circular dependencies means you are fucked

a depends on b.
b depends on c.
c depends on a.

OH SHI-

Optimize THIS

Should be convey as   such in your   spare time Quite.

Biden OBAMA BIDEN OBAMA   BIDEN OBAMA BIDEN   OBAMA BIDEN OBAMA   BIDEN OBAMA BIDEN   OBAMA BIDEN OBAMA   BIDEN OBAMA BIDEN   OBAMA BIDEN OBAMA   BIDEN OBAMA BIDEN   OBAMA BIDEN OBAMA   BIDEN OBAMA BIDEN   OBAMA BIDEN OBAMA   BIDEN OBAMA BIDEN   OBAMA BIDEN OBAMA   BIDEN OBAMA BIDEN   OBAMA BIDEN OBAMA   BIDEN OBAMA BIDEN   OBAMA BIDEN OBAMA.

22 Name: Anonymous 2011-01-31 21:35

<-- check em dubz