最近需要用JavaScript处理图算法,没找到适合的库,就自己写一套玩玩。
Graph.js
仿照Graph.java写的,实现无向图API。
(function(){
return Graph = (function () {
// create empty Graph with V vertices
function Graph(V) {
this._V = V;
this._E = 0;
this._adj = [];
for(var i=0;i<V;i++)
this._adj.push([]);
}
Object.defineProperty(Graph.prototype, "V", {
get: function () {
return this._V;
},
enumerable: true,
configurable: true
});
Object.defineProperty(Graph.prototype, "E", {
get: function () {
return this._E;
},
enumerable: true,
configurable: true
});
// Adds the undirected edge v-w to this graph.
Graph.prototype.addEdge = function (v, w) {
this._E++;
this._adj[v].push(w);
this._adj[w].push(v);
};
// Returns the vertices adjacent to vertex v
Graph.prototype.adj = function (v) {
return this._adj[v];
};
return Graph;
}());
})();
测试数据使用tinyG.txt,结果如下:
CC.js
仿照CC.java写的,使用DFS算法为无向图计算连通图。
(function(){
return CC = (function () {
// Computes the connected components of the DiGraph
function CC(G) {
this._marked = []; // marked[v] = has vertex v been marked?
this._id = []; // id[v] = id of connected component containing v
this._size = []; // size[id] = number of vertices in given component
this._count = 0; // number of connected components
for(var i=0;i<G.V;i++) {
this._id.push(0);
this._size.push(0);
this._marked.push(false);
}
for(var v=0;v<G.V;v++) {
if (!this._marked[v]) {
this.dfs(G, v);
this._count++;
}
}
}
// Returns the number of strong components.
Object.defineProperty(CC.prototype, "count", {
get: function () {
return this._count;
},
enumerable: true,
configurable: true
});
Object.defineProperty(CC.prototype, "ids", {
get: function () {
return this._id;
},
enumerable: true,
configurable: true
});
// DFS on graph G
CC.prototype.dfs = function (G, v) {
this._marked[v] = true;
this._id[v] = this._count;
this._size[this._count]++;
var adj = G.adj(v);
for(var i=0;i<adj.length;i++) {
var w = adj[i];
if(!this._marked[w])
this.dfs(G, w);
}
};
// Are vertices v and w in the same connected component?
CC.prototype.areConnected = function (v, w) {
return this._id[v] === this._id[w];
};
// Returns the component id of the connected component containing vertex v
CC.prototype.id = function (v) {
return this._id[v];
};
// Returns the number of vertices in the connected component containing vertex v
CC.prototype.size = function (v) {
return this._size[v];
};
return CC;
}());
})();
测试数据使用tinyG.txt,结果如下:
DiGraph.js
仿照Digraph.java写的,实现有向图API。
(function(){
return DiGraph = (function () {
// create empty digraph with V vertices
function DiGraph(V) {
this._V = V;
this._E = 0;
this._adj = [];
for(var i=0;i<V;i++)
this._adj.push([]);
}
Object.defineProperty(DiGraph.prototype, "V", {
get: function () {
return this._V;
},
enumerable: true,
configurable: true
});
Object.defineProperty(DiGraph.prototype, "E", {
get: function () {
return this._E;
},
enumerable: true,
configurable: true
});
// add edge v→w
DiGraph.prototype.addEdge = function (v, w) {
this._adj[v].unshift(w);
this._E++;
};
// vertices pointing from v
DiGraph.prototype.adj = function (v) {
return this._adj[v];
};
DiGraph.prototype.reverse = function() {
var reverse = new DiGraph(this._V);
for (var v = 0; v < this._V; v++) {
var adj = this.adj(v);
for(var i=0;i<adj.length;i++) {
var w = adj[i];
reverse.addEdge(w, v);
}
}
return reverse;
};
return DiGraph;
}());
})();
测试数据使用tinyDAG.txt,结果如下:
DepthFirstOrder.js
仿照DepthFirstOrder.java写的,为有向图计算前序和后序。
(function(){
return DepthFirstOrder = (function () {
// Determines a depth-first order for the DiGraph
function DepthFirstOrder(G) {
this._marked = []; //marked[v] = has v been marked in dfs?
this._pre = []; // pre[v] = preorder number of v
this._post = []; // post[v] = postorder number of v
this._preorder = []; // vertices in preorder
this._postorder = []; // vertices in postorder
this._preCounter = 0; // counter or preorder numbering
this._postCounter = 0; // counter for postorder numbering
for(var i=0;i<G.V;i++) {
this._marked.push(false);
this._pre.push(0);
this._post.push(0);
}
for (var v = 0; v < G.V; v++) {
if (!this._marked[v])
this.dfs(G, v);
}
}
// Returns the vertices in pre-order.
Object.defineProperty(DepthFirstOrder.prototype, "preorder", {
get: function () {
return this._preorder;
},
enumerable: true,
configurable: true
});
// Returns the vertices in post-order.
Object.defineProperty(DepthFirstOrder.prototype, "postorder", {
get: function () {
return this._postorder;
},
enumerable: true,
configurable: true
});
// Returns the vertices in reverse post-order.
Object.defineProperty(DepthFirstOrder.prototype, "reversePost", {
get: function () {
return this._postorder.reverse();
},
enumerable: true,
configurable: true
});
// Run DFS in digraph G from vertex v and compute pre-order/post-order
DepthFirstOrder.prototype.dfs = function (G, v) {
this._marked[v] = true;
this._pre[v] = this._preCounter++;
this._preorder.push(v);
var adj = G.adj(v);
for(var i=0;i<adj.length;i++) {
var w = adj[i];
if(!this._marked[w])
this.dfs(G, w);
}
this._postorder.push(v);
this._post[v] = this._postCounter++;
};
// Returns the pre-order number of vertex
DepthFirstOrder.prototype.pre = function (v) {
return this._pre[v];
};
// Returns the post-order number of verte
DepthFirstOrder.prototype.post = function (v) {
return this._post[v];
};
return DepthFirstOrder;
}());
})();
测试数据使用tinyDAG.txt,结果如下:
KosarajuSharirSCC.js
仿照KosarajuSharirSCC.java写的,使用Kosaraju-Sharir算法为有向图计算强连通图。
(function(){
// Kosaraju-Sharir algorithm implementation to compute strong components in a DiGraph (with two DFSs).
return KosarajuSharirSCC = (function () {
// Computes the strong components of the DiGraph
function KosarajuSharirSCC(G) {
this._id = []; // id[v] = id of connected component containing v
this._marked = []; // marked[v] = has vertex v been marked?
this._count = 0; // number of strong connected components
for(var i=0;i<G.V;i++) {
this._id.push(0);
this._marked.push(false);
}
// compute reverse post-order of reverse graph
var dfs = new DepthFirstOrder(G.reverse());
var reversePost = dfs.reversePost;
// run DFS on G, using reverse postorder to guide calculation
for(var i=0;i<reversePost.length;i++) {
var v = reversePost[i];
if (!this._marked[v]) {
this.dfs(G, v);
this._count++;
}
}
}
// Returns the number of strong components.
Object.defineProperty(KosarajuSharirSCC.prototype, "count", {
get: function () {
return this._count;
},
enumerable: true,
configurable: true
});
Object.defineProperty(KosarajuSharirSCC.prototype, "ids", {
get: function () {
return this._id;
},
enumerable: true,
configurable: true
});
// DFS on graph G
KosarajuSharirSCC.prototype.dfs = function (G, v) {
this._marked[v] = true;
this._id[v] = this._count;
var adj = G.adj(v);
for(var i=0;i<adj.length;i++) {
var w = adj[i];
if(!this._marked[w])
this.dfs(G, w);
}
};
// Are vertices v and w in the same strong component?
KosarajuSharirSCC.prototype.stronglyConnected = function (v, w) {
return this._id[v] === this._id[w];
};
// Returns the component id of the strong component containing vertex v
KosarajuSharirSCC.prototype.id = function (v) {
return this._id[v];
};
return KosarajuSharirSCC;
}());
})();
测试数据使用tinyDG.txt,结果如下: