How to avoid circular-dependency errors in Google Closure Library/Compiler

Question

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?

Answer 1

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

This is a flawed assumption. It is not natural to have vertices pointing to their edges and also have edges pointing to their vertices. One should reference the other, not both of them referencing each other. Having duplicate referential responsibilities can cause all sorts of problems. For example, if they ever get out of sync, you won't have a source of truth from which to rebuild your graph.

To avoid circular dependencies, you need to have one "owner" of the relationship. In your particular example, edges referencing vertices strikes me as the more obvious "owner," like so:

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

Then your edge ...

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

Then your graph ...

/**
 * @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); });
 };

Warning: I didn't test this -- it's something I hacked up over a bottle of some nice Puerto Rican rum. I may (read: probably) have something messed up here or there. Regardless, the concept stands. This shows that circular dependencies are not a necessary (nor, to be honest, desirable) requirement for a given language or technology in order to answer questions about graphs.