Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Priority Sorting Challenge

by kvale (Monsignor)
on Jun 01, 2004 at 16:00 UTC ( [id://358165]=note: print w/replies, xml ) Need Help??


in reply to Priority Sorting Challenge

As Abigail-II says, a topological sort is the right algorithm to use if all you have are a set of dependencies to satisfy. If you also have some sort of importance metric on top of the dependencies, the problem is a little harder.

The topological sort will produce a forest, i.e. a set of dependency trees. Among those trees you will find one containing your most important task. Follow the tree back to the root and execute those tasks needed for the most important task. Mark all these tasks as 'done' and find the next most inportant undone task and repeat the procedue, etc. If there are equal priorities, just pick one randomly or create another criterion that breaks the symmetry.

For a circular dependency, there is not much to be done, except to restructure your tasks. It is a pathological case and there is no valid solution as far as the computer is concerned.

-Mark

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://358165]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (2)
As of 2024-04-19 18:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found