Step by Step solution about How to resolve the algorithm Topological sort step by step in the JavaScript programming language

Topological Sort

The provided code performs a topological sort on a directed acyclic graph (DAG) specified as a set of dependencies between packages. A topological sort is an ordering of the vertices in a DAG such that for every directed edge from vertex u to vertex v, u comes before v in the ordering.

Input Data

The input data is a string libs containing the dependencies between packages. Each line in the string represents a package, followed by a list of packages that it depends on. For example:

des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee

This line indicates that the package des_system_lib depends on the packages std, synopsys, std_cell_lib, des_system_lib, dw02, dw01, and ramlib.

Creating the DAG

First, the input data is parsed into a map D, where the keys are the packages and the values are arrays of the packages that they depend on.

const D = libs
 .split('\n')
 .map(e => e.split(' ').filter(e => e != ''))
 .reduce((p, c) =>
   p.set(c[0], c.filter((e, i) => i > 0 && e !== c[0] ? e : null)), new Map());

Then, the map is rotated to represent a DAG, where each key represents a node and the array contains the edges.

const G = [...D.keys()].reduce((p, c) =>
 p.set(
   c,
   [...D.keys()].filter(e => D.get(e).includes(c))),
 new Map()
);

Finding Leaf Nodes

Next, the leaf nodes (nodes with 0 in-degrees) are found using Q:

const Q = [...D.keys()].filter(e => D.get(e).length == 0);

Performing the Topological Sort

Finally, the topological sort is performed using a while loop that iterates through the leaf nodes:

while (Q.length) {
 const u = Q.pop();
 S.push(u);
 G.get(u).forEach(v => {
   D.set(v, D.get(v).filter(e => e !== u));
   if (D.get(v).length == 0) {
     Q.push(v);
   }
 });
}

In each iteration of the loop, a leaf node u is removed from Q and added to the result array S. Then, the dependencies of u are removed from D, and if any of them become leaf nodes, they are added to Q.

The resulting array S contains the topologically sorted list of packages.

Example

The example input data for this code:

des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01             ieee dw01 dware gtech
dw02             ieee dw02 dware
dw03             std synopsys dware dw03 dw02 dw01 ieee gtech
dw04             dw04 ieee dw01 dware gtech
dw05             dw05 ieee dware
dw06             dw06 ieee dware
dw07             ieee dware
dware            ieee dware
gtech            ieee gtech
ramlib           std ieee
std_cell_lib     ieee std_cell_lib
synopsys

Produces the following topological sort:

[
 'ieee',
 'std_cell_lib',
 'gtech',
 'dware',
 'dw07',
 'dw06',
 'dw05',
 'dw02',
 'dw01',
 'dw04',
 'std',
 'ramlib',
 'synopsys',
 'dw03',
 'des_system_lib'
]

const libs =
  `des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
  dw01             ieee dw01 dware gtech
  dw02             ieee dw02 dware
  dw03             std synopsys dware dw03 dw02 dw01 ieee gtech
  dw04             dw04 ieee dw01 dware gtech
  dw05             dw05 ieee dware
  dw06             dw06 ieee dware
  dw07             ieee dware
  dware            ieee dware
  gtech            ieee gtech
  ramlib           std ieee
  std_cell_lib     ieee std_cell_lib
  synopsys`;

// A map of the input data, with the keys as the packages, and the values as
// and array of packages on which it depends.
const D = libs
  .split('\n')
  .map(e => e.split(' ').filter(e => e != ''))
  .reduce((p, c) =>
    p.set(c[0], c.filter((e, i) => i > 0 && e !== c[0] ? e : null)), new Map());
[].concat(...D.values()).forEach(e => {
  D.set(e, D.get(e) || [])
});

// The above map rotated so that it represents a DAG of the form
// Map {
//    A => [ A, B, C],
//    B => [C],
//    C => []
// }
// where each key represents a node, and the array contains the edges.
const G = [...D.keys()].reduce((p, c) =>
  p.set(
    c,
    [...D.keys()].filter(e => D.get(e).includes(c))),
  new Map()
);

// An array of leaf nodes; nodes with 0 in degrees.
const Q = [...D.keys()].filter(e => D.get(e).length == 0);

// The result array.
const S = [];
while (Q.length) {
  const u = Q.pop();
  S.push(u);
  G.get(u).forEach(v => {
    D.set(v, D.get(v).filter(e => e !== u));
    if (D.get(v).length == 0) {
      Q.push(v);
    }
  });
}

console.log('Solution:', S);


Solution: [
  'ieee',
  'std_cell_lib',
  'gtech',
  'dware',
  'dw07',
  'dw06',
  'dw05',
  'dw02',
  'dw01',
  'dw04',
  'std',
  'ramlib',
  'synopsys',
  'dw03',
  'des_system_lib' ]