3
\$\begingroup\$

(There is a follow-up question available to this: Follow-Up Question)

So I have this:

<html>
<body>
<div id="output">

</div>
<script>
function NodeSet() {
  this.array = [];
}

NodeSet.prototype.clear = function() {
  this.array = [];
}

NodeSet.prototype.add = function(node) {
  this.array[node.id] = node;
}

NodeSet.prototype.includes = function(node) {
  return this.array[node.id] !== undefined;
}

NodeSet.prototype.size = function() {
  return this.array.length;
}

function Node(id) {
  this.id = id;
  this.children = [];
  this.parents  = [];
}

Node.prototype.toString = function() {
  return "[Node " + this.id + "]";
}

function nodeEq(nodeA, nodeB) {
  return nodeA.id === nodeB.id;
}

function connect(tail, head) {
  tail.children.push(head);
  head.parents.push(tail);
}

function BuildPath(s, mu, B) {
  let pi = FindShortestPath(s, mu);
  pi.splice(-1, 1);
  pi.push(...B);
  return pi;
}

function DepthLimitedSearchForward(u, Delta, F) {
  if (Delta === 0) {
    F.add(u);
    return;
  }

  u.children.forEach(function(child) {
    DepthLimitedSearchForward(child, Delta -  1, F);
  });
}

function DepthLimitedSearchBackward(u, Delta, B, F) {
  B.unshift(u);

  if (Delta === 0) {
    if (F.includes(u)) {
      return u;
    }
    B.shift();
    return null;
  }

  for (var i = 0; i !== u.parents.length; i++) {
    let parent = u.parents[i];
    let mu = DepthLimitedSearchBackward(parent, Delta - 1, B , F);

    if (mu !== null) {
      return mu;
    }
  }

  B.shift();
  return null;
}

function FindShortestPath(s, t) {
  if (s.id === t.id) {
    return [s];
  }

  let F = new NodeSet();
  let B = [];
  let Delta = 0;

  while (true) {
    DepthLimitedSearchForward(s, Delta, F);

    for (var i = 0; i < 2; i++) {
      let mu = DepthLimitedSearchBackward(t, 
                        Delta + i, 
                        B, 
                        F);

      if (mu !== null) {
        return BuildPath(s, mu, B);
      }

      B = [];
    }

    F.clear();
    Delta++;
  }
}

function DequeNode(elem) {
  this.next = undefined;
  this.elem = elem;
}

function Deque() {
  this.head = undefined;
  this.tail = undefined;
  this.size = 0;
}

Deque.prototype.shift = function() {
  let ret = this.head.elem;
  this.head = this.head.next;
  this.size--;
  return ret;
}

Deque.prototype.push = function(elem) {
  let newNode = new DequeNode(elem);

  if (this.head) {
    this.tail.next = newNode;
  } else {
    this.head = newNode;
  }

  this.size++;
  this.tail = newNode;
}

Deque.prototype.length = function() {
  return this.size;
}

Deque.prototype.front = function() {
  return this.head.elem;
}

let NULL = "NULL";

function tracebackPath(touchNode, parentsA, parentsB) {
  let path = [];
  let current = touchNode;

  while (current != NULL) {
    path.push(current);
    current = parentsA.get(current);
  }

  path.reverse();
  current = parentsB.get(touchNode);

  while (current != NULL) {
    path.push(current);
    current = parentsB.get(current);
  }

  return path;
}

function NodeMap() {
  this.array = [];
}

NodeMap.prototype.put = function(key, value) {
  this.array[key.id] = value;
}

NodeMap.prototype.get = function(key) {
  return this.array[key.id];
}

NodeMap.prototype.containsKey = function(key) {
  return this.array[key.id] !== undefined;
}

function FindShortestPathWithBiBFS(s, t) {
  let queueA = new Deque();
  let queueB = new Deque();

  let parentsA = new NodeMap();
  let parentsB = new NodeMap();

  let distanceA = new NodeMap();
  let distanceB = new NodeMap();

  queueA.push(s);
  queueB.push(t);

  parentsA.put(s, NULL);
  parentsB.put(t, NULL);

  distanceA.put(s, 0);
  distanceB.put(t, 0);

  let bestCost = 1000 * 1000 * 1000;
  let touchNode = undefined;

  while (queueA.length() > 0 && queueB.length() > 0) {
    let distA = distanceA.get(queueA.front());
    let distB = distanceB.get(queueB.front());

    if (touchNode && bestCost < distA + distB) {
      return tracebackPath(touchNode,
                 parentsA, 
                 parentsB); 
    }

    if (distA < distB) {
      let current = queueA.shift();

      if (distanceB.containsKey(current)
        &&
        bestCost > distA + distB) {
        bestCost = distA + distB;
        touchNode = current;
      }

      for (let i = 0; i < current.children.length; i++) {
        let child = current.children[i];

        if (!distanceA.containsKey(child)) {
           distanceA.put(child, distanceA.get(current) + 1);
           parentsA.put(child, current);
           queueA.push(child);
        }
      }
    } else {
      let current = queueB.shift();

      if (distanceA.containsKey(current) 
          &&
        bestCost > distA + distB) {
        bestCost = distA + distB;
        touchNode = current;
      }

      for (let i = 0; i < current.parents.length; i++) {
        let parent = current.parents[i];

        if (!distanceB.containsKey(parent)) {
           distanceB.put(parent, distanceB.get(current) + 1);
           parentsB.put(parent, current);
           queueB.push(parent);
        }
      }
    }
  }

  return [];
}

let outputDiv = document.getElementById("output");
let graph = [];

const NODES = 100000;
const ARCS = 500000;

for (var id = 0; id < NODES; id++) {
  graph.push(new Node(id));
}

for (var i = 0; i < ARCS; i++) {
  let tailIndex = Math.floor(Math.random() * NODES);
  let headIndex = Math.floor(Math.random() * NODES);
  connect(graph[tailIndex], graph[headIndex]);
}

let sourceIndex = Math.floor(Math.random() * NODES);
let targetIndex = Math.floor(Math.random() * NODES);

let sourceNode = graph[sourceIndex];
let targetNode = graph[targetIndex];

console.log("Source node: " + sourceNode);
console.log("Target node: " + targetNode);
outputDiv.innerHTML += "Source node: " + sourceNode + "<br>" +
             "Target node: " + targetNode;

outputDiv.innerHTML += "<br>BIDDFS:<br>";

var startTime = new Date().getMilliseconds();
var path = FindShortestPath(sourceNode, targetNode);
var endTime = new Date().getMilliseconds();
var num = 1;

for (var i = 0; i < path.length; i++) {
  let node = path[i];
  outputDiv.innerHTML += "<br>" + num + ": " + node;
  console.log(num++ + ": " + node);
}

let duration = endTime - startTime;
console.log("Duration: " + duration + " ms.");
outputDiv.innerHTML += "<br>Duration: " + duration + " ms.";
outputDiv.innerHTML += "<br><br>Bidirectional BFS:";

startTime = new Date().getMilliseconds();
var path2 = FindShortestPathWithBiBFS(sourceNode, targetNode);
endTime = new Date().getMilliseconds();
duration = endTime - startTime;
num = 1;

for (var i = 0; i < path2.length; i++) {
  let node = path2[i];
  outputDiv.innerHTML += "<br>" + num + ": " + node;
  console.log(num++ + ": " + node);
}

console.log("Duration: " + (endTime - startTime) + " ms.");
outputDiv.innerHTML += "<br>Duration: " + duration + " ms.";
</script>
</body>
</html>

Critique request

Could you please tell me how to improve my code in any way?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.