如何在Google Closure庫/編譯器中避免循環依賴錯誤

Question

我正在開發一個系統，它在內存中生成一個圖形網絡，並使用Dijkstra算法解決最短路徑問題。有兩個類彼此互相引用。第一個是

// edge.js 
goog.provide('Edge'); 
goog.require('Vertex'); 

/** 
* @constructor 
*/ 
Edge = function(){ 
    this.vertices_ = []; 
}; 

/** 
* @param {Vertex} vertex 
*/ 
Edge.prototype.addVertex(vertex){ 
    this.vertices_.push(vertex); 
}; 

/** 
* @return {Array.<Vertex>} 
*/ 
Edge.prototype.getVertices(){ 
    return this.vertices_; 
}; 

，另一個是...

// vertex.js 
goog.provide('Vertex'); 
goog.require('Edge'); 

/** 
* @constructor 
*/ 
Vertex = function(){ 
    this.edges_ = []; 
}; 

/** 
* @param {Edge} edge 
*/ 
Vertex.prototype.addEdge(edge){ 
    this.edges_.push(edge); 
}; 

/** 
* @return {Array.<Edge>} 
*/ 
Vertex.prototype.getAllEdges(){ 
    return this.edges_; 
}; 

是，邊指頂點，頂點指邊。我認爲這很自然。

問題是這些代碼無法編譯，因爲包括循環依賴。據說here包含循環依賴的系統設計是錯誤的，但我不能最終發現它有什麼問題。

使用閉包編譯器開發能夠解決JavaScript的最短路徑問題的應用程序是否錯誤？有其他解決方案嗎？

Answer 1

邊指的是頂點，頂點指的是邊。我認爲這很自然。

這是一個有缺陷的假設。它是而不是自然有頂點指向其邊緣，也有指向其頂點的邊緣。一個應該引用另一個，而不是兩個引用對方。有重複的參照責任可能會導致各種問題。例如，如果它們不同步，則不會有重建圖形的真相來源。

爲了避免循環依賴，您需要擁有一個關係的「所有者」。在您的具體的例子，邊參照頂點給我的印象比較明顯的「主人」，就像這樣：

// vertex.js 
goog.provide('Vertex'); 

goog.require('goog.math.Coordinate'); 

/** 
* @constructor 
* @param {number=} opt_x x-position, defaults to 0 
* @param {number=} opt_y y-position, defaults to 0 
* @extends {goog.math.Coordinate} 
*/ 
Vertex = function(opt_x, opt_y) { 
    goog.base(this, opt_x, opt_y); 
}; 

那麼你的優勢...

// edge.js 
goog.provide('Edge'); 

goog.require('Vertex'); 
goog.require('goog.math.Coordinate'); 

/** 
* @constructor 
* @param {Vertex} start 
* @param {Vertex} end 
*/ 
Edge = function(start, end) { 
    /** 
    * @type {Vertex} 
    * @private 
    */ 
    this.start_ = start; 

    /** 
    * @type {Vertex} 
    * @private 
    */ 
    this.end_ = end; 
}; 

/** 
* @return {number} 
*/ 
Edge.prototype.getDistance = function() { 
    goog.math.Coordinate.distance(this.start_, this.end_); 
}; 

/** 
* Checks if this Edge connects to the referenced vertex. 
* @param {Vertex} vertex 
* @return {bool} 
*/ 
Edge.prototype.connects = function(vertex) { 
    return this.start_ === vertex || this.end_ === vertex; 
}; 

/** 
* @return {Vertex} 
*/ 
Edge.prototype.getStart = function() { 
    return this.start_; 
}; 

/** 
* @return {Vertex} 
*/ 
Edge.prototype.getEnd = function() { 
    return this.end_; 
}; 

然後你的圖...

/** 
* @param {Array.<Edge>} edges 
* @constructor 
*/ 
Graph = function(edges) { 

    /** 
    * @type {Array.<Edge>} 
    * @private 
    */ 
    this.edges_ = edges; 
}; 

/** 
* @param {Vertex} start 
* @param {Vertex} end 
* @return {number|undefined} shortest path between {@code start} and {@code end}, 
* with 'undefined' being returned if a path does not exist. 
*/ 
Graph.prototype.getShortestPath = function(start, end) { 
    return this.getShortestPath_(start, end, 0, []); 
} 

/** 
* @param {Vertex} start 
* @param {Vertex} end 
* @param {number} traveled amount traveled thus far 
* @param {Array.<Vertex>} path the route taken thus far 
* @return {number|undefined} 
* @private 
*/ 
Graph.prototype.getShortestPath_ = function(start, end, traveled, path) { 
    if (start == end) { 
     return traveled + 0; 
    } 

    var distances = goog.array.map(
     this.getEdgesToTry_(start, path), 
     function (edge) { 
      var nextStart; 

      if (edge.getStart() === start) { 
       nextStart = edge.getEnd(); 
      } else { 
       nextStart = edge.getStart(); 
      } 

      return this.getShortestPath_(
       newStart, 
       end, 
       edge.getDistance() + traveled, 
       goog.array.concat(path, start) 
      ); 
     }, 
     this 
    ); 

    return goog.array.reduce(
     distances, 
     function (shortestDistance, distance) { 
      if (distance !== undefined) { 
       if (shortestDistance === undefined) { 
        return distance; 
       } else { 
        return Math.min(shortestDistance, distance); 
       } 
      } else { 
       return shortestDistance; 
      } 
     }, 
     undefined 
    );  
}; 

/** 
    * @param {Vertex} vertex 
    * @param {Array.<Vertex>} path 
    * @return {Array.<Vertex>} 
    * @private 
    */ 
Graph.prototype.getEdgesToTry_ = function(vertex, path) { 
    return goog.array.filter(
     this.edges_, 
     function (edge) { return this.isEdgeToTry_(edge, vertex, path); }, 
     this 
    );   
}; 

/** 
    * @param {Edge} edge 
    * @param {Vertex} start 
    * @param {Array.<Vertex>} path 
    * @return {bool} 
    * @private 
    */ 
Graph.prototype.isEdgeToTry_ = function(edge, start, path) { 
    return edge.connects(start) 
     && goog.array.every(
      path, function(vertex) { return !edge.connects(vertex); }); 
}; 

警告：我沒有測試這個 - 這是我在一瓶some nice Puerto Rican rum上闖入的東西。我可能（看起來可能）在這裏或那裏搞砸了一些東西。無論如何，這個概念的立場。這表明對於給定的語言或技術來說，循環依賴不是必需的（也不是真的，可取的）要求，以回答關於圖的問題。