Topological Sort
While reviewing some basic concept, I come across an interesting problem which is called topological sorting. Basically the problem is to find an ordering where the dependency requirements are respected. One concrete example of this problem is how to determine the build order of projects given a set of dependencies between the projects. A project cannot be build unless all the dependencies of that projects are already built. This problem is very relevant if we want to create a tool for building multiple projects.
We can treat the problem as a graph problem where each project is represented by a node and dependencies between projects are represented as directed edges between the nodes. One example is that if project A depends on project B an edge from project B to project A will be created.
One way to approach this problem is to start from nodes which have no incoming edges. Once a node is built, all the outgoing edges from that node shall be removed since they are no longer relevant. The dependency to nodes that are already built becomes irrelevant because they no longer need to be considered. Once we remove all edges originating from built nodes, we can now get the next project to build by searching for nodes without any incoming edges in the updated graph. We continue this process until there is no more nodes left to build. If there are still some nodes that have not been built but we cannot find any nodes without incoming edges, then it means there is circular dependency between some projects and there no valid ordering that can be found.