Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts

Sort dependency list or Topological Sorting in PHP

Topological Sorting - Wkipedia


In the field of computer science, a topological sort (sometimes abbreviated toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed a cyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

Sometimes, we fall into situations where we have a list of tasks to be done, but with a condition that each of the tasks may need one or more tasks from the list to be done before them. Let’s, consider that we have to do tasks a,b,c,d and the condition is b & d has to be done before the task a, then the sorting will become b,d,a,c.