- Need help in finding an algorithm
- Posted by robertday5@gmail.com on January 6th, 2005
Need help in finding an efficient algorithm for the following problem.
There are tasks which have predecessor tasks which needs to be
completed before taking up the new task.
Our aim is to find the required order of the tasks, so that the
pre-requisite tasks are always completed before the task.
For example
TaskA needs taskJ and taskK
TaskB needs none
TaskC needs TaskA, taskK
taskD needs taskB
taskJ needs taskB
taskK needs none
There is no cyclical dependency and all the tasks take same amount of
time
A valid answer can be
taskB
taskK
taskJ
taskD
taskC
taskA
- Posted by infobahn on January 6th, 2005
robertday5@gmail.com wrote:
You are asking about topological sorting.
Knuth is a whole flight of stairs away from my desk right now, so
I can't guarantee it, but I'd be amazed if he didn't cover this.
"The Art of Computer Programming", Vol 3, "Sorting and Searching",
Donald E Knuth. If you don't have a copy, ask your librarian.
- Posted by Roger Willcocks on January 6th, 2005
"infobahn" <infobahn@btinternet.com> wrote in message
news:41DD0BA6.87C09101@btinternet.com...
The most efficient algorithm is 'use the (Unix) tsort utility'.
--
Roger
- Posted by infobahn on January 6th, 2005
[Much snippage]
Roger Willcocks wrote:
And I can see how that would turn out...
Adams, Jock : 8/10. Good and tight, but use more comments.
Atkins, Sarah: 5/10. Turn up your warning level. Blech.
Ball, Peter : 9/10. Excellent. Nice code structure.
Cody, Brian : 7/10. Next time, test more thoroughly.
Day, Robert : 0/10. NO, I DID NOT MEAN exec("tsort")!!!
...
- Posted by rossum on January 6th, 2005
On Thu, 6 Jan 2005 10:06:33 +0000 (UTC), infobahn
<infobahn@btinternet.com> wrote:
Climbing stairs is good exercise. Knuth covers topological sorting in
Volume 1 Section 2.2.3 Algorithm T. (My copy was just across the
hall.)
rossum
--
The ultimate truth is that there is no Ultimate Truth
