不知道為什么 Fearless 沒(méi)有嵌入他的示例，但我冒昧地將其轉(zhuǎn)換為帶有 Mocha/Chai 單元測(cè)試的 ES6 類(lèi)。
正如其他人所提到的，有向圖應(yīng)該將其關(guān)聯(lián)（也稱(chēng)為邊）存儲(chǔ)在兩個(gè)單獨(dú)的集合中。
這使得查找變得微不足道。
class AssociationGraph {
constructor() {
this.sourceEdges = new Map();
this.targetEdges = new Map();
}
/**
* @brief Clear all associations
*/
clear() {
this.sourceEdges.clear();
this.targetEdges.clear();
}
/**
* @brief Return true if there is a link from source to target
*/
hasLink(source, target) {
let targets = this.sourceEdges.get(source);
return targets != undefined && targets.has(target);
}
/**
* @brief Create a link from source to target, unless one already exists.
*/
addLink(source, target) {
this._add(source, target, this.sourceEdges);
this._add(target, source, this.targetEdges);
}
/**
* @brief Return an iterator over all the targets of source.
*/
targetsOf(source) {
return this._of(source, this.sourceEdges);
}
/**
* @brief Return an iterator over all the sources of target.
*/
sourcesOf(target) {
return this._of(target, this.targetEdges);
}
/**
* @brief Return all unique nodes for all associations.
*/
nodes() {
return [...new Set([...this.sourceEdges.keys(), ...this.targetEdges.keys()])];
}
/**
* @brief Return an iterator that generates edges e.g. {source: a, target:b}
* for all links in the association.
*/
edges() {
let self = this;
return (function*() {
for (let [ srcKey, srcVal ] of self.sourceEdges.entries()) {
for (let [ tarKey, tarVal ] of srcVal.entries()) {
yield { source: srcKey, target: tarKey };
}
}
})();
}
_add(a, b, store) {
let set = store.get(a);
if (set == undefined) {
set = new Set();
store.set(a, set);
}
set.add(b);
}
_of(a, map) {
let b = map.get(a);
if (b == undefined) {
return new Set();
} else {
return b.keys();
}
}
}
// Construct a graph by adding associations
let graph = new AssociationGraph();
graph.addLink('n1', 'n2');
graph.addLink('n1', 'n3');
graph.addLink('n1', 'n4');
graph.addLink('n2', 'n3');
graph.addLink('n3', 'n4');
// Print the nodes
//for (let node of graph.nodes()) console.log(node);
// Print the edges
//for (let edge of graph.edges()) console.log(JSON.stringify(edge));
// Convenience function to transform a CSV string into an array
const strSet = (str) => str.trim().length > 0 ? str.split(/,/g) : [];
// Run a unit test
let assert = chai.assert,
expect = chai.expect,
should = chai.should;
mocha.setup("bdd");
chai.should();
describe('hasLink', () => {
it('n1 ===> n2', () => graph.hasLink('n1', 'n2').should.equal(true));
it('n2 =/=> n4', () => graph.hasLink('n2', 'n4').should.equal(false));
it('n3 ===> n4', () => graph.hasLink('n3', 'n4').should.equal(true));
});
describe('targetsOf', () => {
it('n1 : [n2, n3, n4]', () => expect(
Array.from(graph.targetsOf('n1'))).to.have.members(strSet('n2,n3,n4')));
it('n2 : [n3]', () => expect(
Array.from(graph.targetsOf('n2'))).to.have.members(strSet('n3')));
it('n3 : [n4]', () => expect(
Array.from(graph.targetsOf('n3'))).to.have.members(strSet('n4')));
it('n4 : []', () => expect(
Array.from(graph.targetsOf('n4'))).to.have.members(strSet('')));
});
describe('sourcesOf', () => {
it('n1 : []', () => expect(
Array.from(graph.sourcesOf('n1'))).to.have.members(strSet('')));
it('n2 : [n1]', () => expect(
Array.from(graph.sourcesOf('n2'))).to.have.members(strSet('n1')));
it('n3 : [n1, n2]', () => expect(
Array.from(graph.sourcesOf('n3'))).to.have.members(strSet('n1,n2')));
it('n4 : [n1, n3]', () => expect(
Array.from(graph.sourcesOf('n4'))).to.have.members(strSet('n1,n3')));
});
describe('nodes', () => {
it('graph.nodes()', () => expect( Array.from(graph.nodes())).to.have.members(strSet('n1,n2,n3,n4')));
});
mocha.run();
#mocha-report {
font-family: monospace;
font-size: smaller;
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/chai/4.2.0/chai.min.js"></script><script src="https://cdnjs.cloudflare.com/ajax/libs/mocha/7.1.1/mocha.min.js"></script><div id="mocha"></div>
<link href="https://cdnjs.cloudflare.com/ajax/libs/mocha/7.1.1/mocha.min.css" rel="stylesheet"/>
