SHARE
TWEET

Untitled

a guest Feb 14th, 2020 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const express = require('express')
  2. const app = express()
  3.  
  4. // Main function
  5. function topoSort(){
  6.   const dependencies = [
  7.     [],
  8.     [],
  9.     [1],
  10.     [0],
  11.     [],
  12.     [3],
  13.     [2, 4, 5],
  14.     [5, 6]
  15.   ]
  16.  
  17.  
  18.   let inDegrees = mapInDegrees(dependencies)
  19.   let queue = generateQueue(inDegrees)
  20.   let list = []
  21.  
  22.   for(let i = 0; i < inDegrees.length; i++){
  23.     for(let row of dependencies){
  24.       for(let item of row){
  25.         if(item === queue[0]){
  26.           inDegrees[dependencies.indexOf(row)]-=1  
  27.           if(inDegrees[dependencies.indexOf(row)] == 0){
  28.             queue.push(dependencies.indexOf(row))
  29.           }
  30.           list.push(queue[0])
  31.           queue.shift()
  32.         }
  33.       }
  34.     }
  35.   }
  36.  
  37.   //list.push(dependencies.length-1)
  38.   return list
  39.  
  40. }
  41.  
  42. // Generates in-degrees
  43. function mapInDegrees(dependencies){
  44.   let inDegrees = []
  45.   for(let i = 0; i < dependencies.length; i++){
  46.     inDegrees.push(dependencies[i].length)
  47.   }
  48.   return inDegrees
  49. }
  50.  
  51. // Generates queue
  52. function generateQueue(inDegrees){
  53.   let queue = []
  54.   for(let i = 0; i < inDegrees.length; i++){
  55.     if(inDegrees[i] === 0)
  56.       queue.push(i)
  57.   }
  58.   return queue
  59. }
  60.  
  61. console.log(topoSort())
  62. app.listen(3000, () => {
  63.  
  64. })
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top