Algorithm1 calculates the logical tree of given package without installation, it can be divided into 2 steps as:

1. Physical tree construction.

We iterate all dependencies by BFS with queue Q to construct the installing directory Dir (line 6), for each visited node N, we resolve all its direct dependencies alphabetically (line 9). Each direct dependency d are already resolved as a list of satisfying versions Vs in DVGraph (line 10). We first check whether there is an installed node that is not only within Vs but also visible to N (line 11) (As in motivating example, D@1.1.0 is visible to B@1.0.0 and C@1.0.0 while D@2.0.0 is not visible to C@1.0.0). If yes, the installed node would be depended on by N (line 12) (i.e., C@1.0.0 depends on D@1.1.0), otherwise a new proper version would be installed inside at a lower position (lines 14-18) (i.e., D@2.0.0 is installed inside B@1.0.0 since there is already a D at first level). Besides, there are also some rules on selecting versions applied (line 14) (i.e., rules on deprecated[1] and latest version[2]). Finally, the physical tree can be constructed.

2. Logical tree construction.

The physical tree we constructed contains all dependency relations among folders, we iterate all nodes in physical trees and connect them via dependency relations to recover the logical tree (lines 19-23).

Reference:

[1] npm install got different versions according to node-semver. [Online]. Available: https://stackoverflow.com/questions/60350847/npm-install-got-different-versions-according-to-node-semver

[2] Why does node semver use 'latest' in dist-tags as max version for satisfied versions? [Online]. Available: https://stackoverflow.com/questions/60335207/why-does-node-semver-use-latest-in-dist-tags-as-max-version-for-satisfied-vers