0

I'm developing a system which generates a graph network in memory, and solve the shortest path problem using Dijkstra's algorithm. There are two classes that are referring each other. The first one is

// 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_;
};

And the other is...

// 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_;
};

Yes, edges are referring vertices, vertices are referring edges. I think this is natural.

The problem is that these codes cannot be compiled, because including circular dependency. It is said here that system designs containing circular dependency is wrong, but I can't finally find out what's wrong with it.

Is it wrong to use closure-compiler to develop applications that can solve the shortest path problem with JavaScript? Are there alternative solutions?

4

1 回答 1

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); });
 };

警告：我没有对此进行测试——这是我在一瓶不错的波多黎各朗姆酒上捣碎的。我可能（阅读：可能）在这里或那里有一些事情搞砸了。无论如何，这个概念是成立的。这表明，对于给定的语言或技术，为了回答有关图的问题，循环依赖不是必要的（老实说，也不是可取的）要求。

于 2013-10-20T05:59:15.233 回答