CODEWITHSUNDEEP
algorithm
KDecker
KDecker

Reputation: 7148

Determine an ordering of dependent "things"; Ex. ordering of processes necessary to get to work

I am trying to determine a name for the problem I have so I can find solutions.

An example problem. Before you can go out the door in the morning you have to do a few things. Such as showering, getting dressed, and eating. It makes sense to do some things before others. Such as getting dressed after you shower. Given a list of things, along with their corresponding things that must be done before them, how can you determine the order of these things?

I just can't think of name of this problem/algorithms used to solve this problem. I think it can be solved by representing the things in a graph and finding the longest path through it?

Upvotes: 0

Views: 73

Answers (1)

senshin
senshin

Reputation: 10360

The problem you're trying to solve is called dependency resolution. This problem is typically solved using topological sorting.

The basic idea is that if you have a task X which must be performed before a task Y, you should build a directed graph with an edge pointing from X to Y, and do the same for all the other tasks that interdepend on one another. Then, perform a topological sort on the graph (which can be done iff there are no cycles in the graph) to generate an ordering on the tasks which ensures that all of a given task's dependencies precede the task.

Upvotes: 1

Related Questions