How Webpack uses dependency graph to build modules

In the last two posts I have discussed about Webpack and it's core concepts. Last two post were based on Webpack's architecture and how we can extend the use of Webpack by building our own plugin. In this post I will be discussing in detail about the dependency graph which Webpack uses for bundling of modules.

I've used the word dependancy graph in my previous posts to describe Webpack bundling. Webpack uses dependency graph to resolve modules which are dependent on one another and build the modules first which are required in some other modules. Let's take the same example which I've used in my first post to understand this more accurately.

In the above example the file bootstrap.main.ts is used as the entry point to build the dependency graph. Other files in the above example are all required in the main file.

So let's see how this dependency graph is resolved and rendered such that all the files are loaded in correct order.

More about Dependency Graph

The graph we will refer here is directed acyclic graph in which the edges are connected in such way that each edge only goes one way. In directed acyclic graph it becomes difficult to traverse the entire graph starting from one point of the graph due to it's acyclic nature.

But how the dependency graph is sorted?
Answer: Topological Sorting

So, your next question will be what is Topological Sorting 😅

What is Topological sorting and how it works?

Let us consider an example of directed acyclic graph to understand this algorithm.

In Topological sorting we take two data structures a set and a stack to maintain the order and keep track of the vertices.

The set will keep track of all the visited vertices while stack will have all the vertices in topologically sorted order.

I am going to refer the above mentioned graph for reference. So let's start with Node E. In the beginning our visited set is empty so we will directly put E in the visited set. After E we will explore the children's of E which are F and H. Since H is not in the visited set and has no children which means that it is fully explored, so we move H from set to stack.

Now next we move to next child of E which is F and check it's occurrence in set. Since it is not present in set so we will add it in the set and look for the child nodes. F has a child node G so we will check in set and add that in the set. Again, G does not have any child nodes so we will add that to the stack.

After moving G into the stack we move back to its parent which is F. All the children's of F are explored so we put F into the stack and move to its parent E. Since all the children's are already moved to stack so we will add E to the stack.

Now we will pick some other unvisited node so let's pick B which has two children's C and D. We will first check that if C is present in the set and will add it to the set as it is not present. After adding C to the set we will again check for the children's of C. E is the only child of C and since it is already present in the set so we will move C to stack.

Next we move towards the next child of B which is D we will check set first and since it is unavailable in the set we will add to the set. D has one child F and since it is already present in set we will add D to the stack.

With this all the children's of B are fully explored so we will add B to the stack.

After completing this cycle we will move to the next unvisited node which is A. Since A has only one child which is present in the set so we will add A to the stack. The final order of set and stack will be like something like this.

The order in which the nodes will be rendered is A, B, D, C, E, F, G, H.

Note- There can be different order for the topological sorting it depends on how you pick the unvisited nodes

Consider all the nodes in the graph as modules which are dependent on one another. The directed vertices points the dependency relationship between modules. Webpack uses Topological sorting to resolve the dependency relationship and renders the modules in the order provided by the algorithm.

Hope this has given you brief insight about the execution and use of dependency graph by webpack.

Happy reading! 📖