时间戳

首页 > 解决方案 > CouchDB 中图中的最短路径

javascript - CouchDB 中图中的最短路径

问题描述

我正在尝试计算存储在 CouchDB 中的图中的最短路径。我必须在 db 中执行此操作，因为我的任务是比较 3 个不同 DBMS 在各种情况下的查询速度。因此，加载数据并在 python（或其他任何东西）中运行 dijkstra 不是一种选择。我对基于文档的数据库很陌生，所以我可能错了，但我认为我唯一的选择是视图。

我的数据库结构如下：

我的想法是创建一个返回最短路径的视图。我有这个代码来计算它。它基于这篇文章。我只需要稍作修改，否则我会遇到let,foreach 之类的语法错误：

function (doc) {
  function Graph() {
    this.nodes = [];
    this.adjacencyList = {};

    this.addNode = function(node) {
      if(this.nodes.indexOf(node) != -1)
        return;
      this.nodes.push(node); 
      this.adjacencyList[node] = [];
    }

    this.addEdge = function(node1, node2, weight) {
      this.adjacencyList[node1].push({node:node2, weight: weight});
      //this.adjacencyList[node2].push({node:node1, weight: weight});
    }

    this.shortestPath = function(startNode, endNode){
      var times = {};
      var backtrace = {};
      var pq = new PriorityQueue();

      times[startNode] = 0;

      for(var i = 0; i<this.nodes.length; i++){
        if(this.nodes[i] != startNode){
          times[node] = Infinity;
        }
      }

      pq.enqueue([startNode, 0]);

      while (!pq.isEmpty()) {
        var shortestStep = pq.dequeue();
        var currentNode = shortestStep[0];
        for(var i=0;i< this.adjacencyList[currentNode].length; i++){
          var neighbor = this.adjacencyList[currentNode][i];
          var time = times[currentNode] + neighbor.weight;
          if (time < times[neighbor.node]) {
            times[neighbor.node] = time;
            backtrace[neighbor.node] = currentNode;
            pq.enqueue([neighbor.node, time]);
          }
        }
      }
      var path = [endNode];
      var lastStep = endNode;
      while(lastStep !== startNode) {
        path.unshift(backtrace[lastStep]);
        lastStep = backtrace[lastStep];
      }

      return 'Path is ${path} and time is ${times[endNode]}';
    }
  };

  function PriorityQueue() {
    this.collection = [];

    this.enqueue = function(element){
      if (this.isEmpty()){ 
        this.collection.push(element);
      } else {
        var added = false;
        for (var i = 1; i <= this.collection.length; i++){
          if (element[1] < this.collection[i-1][1]){ 
            this.collection.splice(i-1, 0, element);
            added = true;
            break;
          }
        }
        if (!added){
            this.collection.push(element);
        }
      }
    };

    this.dequeue = function() {
      var value = this.collection.shift();
      return value;
    };

    this.isEmpty = function() {
      return (this.collection.length === 0) 
    };
  };

  var graph = new Graph();

  var startNode = 118;
  var endNode = 270;
  for (var i = 0; i < doc.edges.length; ++i) {
    graph.addNode(doc.edges[i].start);
    graph.addNode(doc.edges[i].end);
    graph.addEdge(doc.edges[i].start,doc.edges[i].end,doc.edges[i].distance);
  }

  emit("shortest", graph.shortestPath(startNode,endNode));
}

但是，当查询视图时，我得到 0 行。

编辑：

这是一个示例数据集：

{
  "_id": "7c75c647957f57eaa47103d5795eab44",
  "_rev": "3-4c8bc32cf6129209b1ce2fec35f6e6cd",
  "edges": [
    {
      "start": "1609",
      "end": "1622",
      "distance": 57.403187
    },
    {
      "start": "2471",
      "end": "2479",
      "distance": 29.718756
    },
    {
      "start": "2463",
      "end": "2471",
      "distance": 61.706902
    },
    {
      "start": "2443",
      "end": "2448",
      "distance": 19.080025
    },
    ...
}

标签： javascriptcouchdb

解决方案

终于我找到了。当我将 foreach 重写为传统的 for 时，我忘记了更改：

for(var i = 0; i<this.nodes.length; i++){
    if(this.nodes[i] != startNode){
      times[node] = Infinity;
    }
}

对此：

for(var i = 0; i<this.nodes.length; i++){
   if(this.nodes[i] != startNode){
      times[this.nodes[i]] = Infinity;
   }
}

有趣的是，我在 CouchDB 中没有看到任何错误。我必须使用 node.js 在本地运行我的代码才能发现有错误。

推荐阅读