text: const graphlib = require('graphlib');
  
  exports.ksp = function (g, source, target, K, weightFunc, edgeFunc) {
  
      // clone graph to avoid changes to the original
      let _g = graphlib.json.read(graphlib.json.write(g));
  
      // Initialize containers for candidate paths and k shortest paths
      let ksp = [];
      let candidates = [];
  
      // Compute and add the shortest path */
      let kthPath = getDijkstra(_g, source, target, weightFunc, edgeFunc);
      if (!kthPath) {
          return ksp;
      }
      ksp.push(kthPath);
  
      // Iteratively compute each of the k shortest paths */
      for (let k = 1; k < K; k++) {
  
          // Get the (k-1)st shortest path
          let previousPath = cloneObject(ksp[k - 1]); // clone path to new var
  
          if (!previousPath) {
              break;
          }
          /* Iterate over all of the nodes in the (k-1)st shortest path except for the target node; for each node,
          (up to) one new candidate path is generated by temporarily modifying the graph and then running
          Dijkstra's algorithm to find the shortest path between the node and the target in the modified
          graph */
  
          for (let i = 0; i < previousPath.edges.length; i++) {
  
  
              // Initialize a container to store the modified (removed) edges for this node/iteration
              let removedEdges = [];
  
              // Spur node = currently visited node in the (k-1)st shortest path
              let spurNode = previousPath.edges[i].fromNode;
  
              // Root path = prefix portion of the (k-1)st path up to the spur node
              let rootPath = clonePathTo(previousPath, i);
  
              // Iterate over all of the (k-1) shortest paths */
              ksp.forEach(p => {
                  p = cloneObject(p); // clone p
                  let stub = clonePathTo(p, i);
  
                  // Check to see if this path has the same prefix/root as the (k-1)st shortest path
                  if (isPathEqual(rootPath, stub)) {
                      // If so, eliminate the next edge in the path from the graph (later on, this forces the spur
                      // node to connect the root path with an un-found suffix path) */
                      let re = p.edges[i];
                      _g.removeEdge(re.fromNode, re.toNode);
                      removedEdges.push(re);
                  }
              })
  
              // Temporarily remove all of the nodes in the root path, other than the spur node, from the graph */
              rootPath.edges.forEach(rootPathEdge => {
                  let rn = rootPathEdge.fromNode;
                  if (rn !== spurNode) {
                      // remove node and return removed edges
                      let removedEdgeFromNode = removeNode(_g, rn, weightFunc);
                      removedEdges.push(...removedEdgeFromNode);
                  }
              })
  
              // Spur path = shortest path from spur node to target node in the reduced graph
              let spurPath = getDijkstra(_g, spurNode, target, weightFunc, edgeFunc);
  
              // If a new spur path was identified...
              if (spurPath != null) {
                  // Concatenate the root and spur paths to form the new candidate path
                  let totalPath = cloneObject(rootPath);
                  let edgesToAdd = cloneObject(spurPath.edges);
                  totalPath.edges.push(...edgesToAdd);
                  totalPath.totalCost += spurPath.totalCost;
  
                  // If candidate path has not been generated previously, add it
                  if (!isPathExistInArray(candidates, totalPath)) {
                      candidates.push(totalPath);
                  }
              }
  
              addEdges(_g, removedEdges);
          }
  
          // Identify the candidate path with the shortest cost */
          let isNewPath;
          do {
              kthPath = removeBestCandidate(candidates);
              isNewPath = true;
              if (kthPath != null) {
                  for (let p of ksp) {
                      // Check to see if this candidate path duplicates a previously found path
                      if (isPathEqual(p, kthPath)) {
                          isNewPath = false;
                          break;
                      }
                  }
  
              }
          } while (!isNewPath);
  
          // If there were not any more candidates, stop
          if (kthPath == null) {
              break;
          }
  
          // Add the best, non-duplicate candidate identified as the k shortest path
          ksp.push(kthPath);
      }
      return ksp;
  }
  
  
  // Dijkstra algorithm to find the shortest path
  function getDijkstra(g, source, target, weightFunc, edgeFunc) {
      if (!weightFunc) {
          weightFunc = (e) => g.edge(e);
      }
  
      let dijkstra = graphlib.alg.dijkstra(g, source, weightFunc, edgeFunc);
      return extractPathFromDijkstra(g, dijkstra, source, target, weightFunc, edgeFunc);
  }
  
  function extractPathFromDijkstra(g, dijkstra, source, target, weightFunc, edgeFunc) {
      // check if there is a valid path
      if (dijkstra[target].distance === Number.POSITIVE_INFINITY) {
          return null;
      }
  
      let edges = [];
      let currentNode = target;
      while (currentNode !== source) {
          let previousNode = dijkstra[currentNode].predecessor;
  
          // extract weight from edge, using weightFunc if supplied, or the default way
          let weightValue;
          if (weightFunc) {
              weightValue = weightFunc({ v: previousNode, w: currentNode });
          } else {
              weightValue = g.edge(previousNode, currentNode)
          }
          let edge = getNewEdge(previousNode, currentNode, weightValue);
          edges.push(edge);
          currentNode = previousNode;
      }
  
      let result = {
          totalCost: dijkstra[target].distance,
          edges: edges.reverse()
      };
      return result;
  }
  
  function addEdges(g, edges) {
      edges.forEach(e => {
          g.setEdge(e.fromNode, e.toNode, e.edgeObj);
      })
  }
  
  // input: a graph and a node to remove
  // return value: array of removed edges
  function removeNode(g, rn, weightFunc) {
  
      let remEdges = [];
      let edges = cloneObject(g.edges());
      // save all the edges we are going to remove
      edges.forEach(edge => {
          if (edge.v == rn || edge.w == rn) {
  
              // extract weight
              let weightValue;
              if (weightFunc) {
                  weightValue = weightFunc(edge);
              } else {
                  weightValue = g.edge(edge);
              }
  
              let e = getNewEdge(edge.v, edge.w, weightValue);
              remEdges.push(e);
          }
      })
      g.removeNode(rn); // removing the node from the graph
      return remEdges;
  }
  
  // return a new path object from source path to a given index
  function clonePathTo(path, i) {
      let newPath = cloneObject(path);
      let edges = [];
      let l = path.edges.length;
      if (i > l) {
          i = 1;
      }
      // copy i edges from the source path
      for (let j = 0; j < i; j++) {
          edges.push(path.edges[j]);
      }
  
      // calc the cost of the new path
      newPath.totalCost = 0;
      edges.forEach(edge => {
          newPath.totalCost += edge.weight;
      })
      newPath.edges = edges;
      return newPath;
  }
  
  
  // compare between two path objects, return true if equals
  function isPathEqual(path1, path2) {
      if (path2 == null) {
          return false;
      }
  
      let numEdges1 = path1.edges.length;
      let numEdges2 = path2.edges.length;
  
      // compare number of edges
      if (numEdges1 != numEdges2) {
          return false;
      }
  
      // compare each edge
      for (let i = 0; i < numEdges1; i++) {
          let edge1 = path1.edges[i];
          let edge2 = path2.edges[i];
          if (edge1.fromNode != edge2.fromNode) {
              return false;
          }
          if (edge1.toNode != edge2.toNode) {
              return false;
          }
      }
  
      return true;
  }
  
  // build a new edge object
  function getNewEdge(fromNode, toNode, weight) {
      return {
          fromNode: fromNode,
          toNode: toNode,
          weight: weight
      }
  }
  
  // since javascript sends object by ref, we sometimes want to clone objects and its childs to avoid it
  // this is a workaround for clone objects
  function cloneObject(obj) {
      return JSON.parse(JSON.stringify(obj));
  }
  
  // return true if a given path is found on array of path
  function isPathExistInArray(candidates, path) {
      candidates.forEach(candi => {
          if (isPathEqual(candi, path)) {
              return true;
          }
      })
      return false;
  }
  
  // sort the candidates array by total cose, then remove and return the best candidate.
  function removeBestCandidate(candidates) {
      return candidates.sort((a, b) => a.totalCost - b.totalCost).shift();
  }