Changeset View
Changeset View
Standalone View
Standalone View
lib/datastore/graph.js
| class Graph { | class Graph { | ||||
| constructor() { | constructor() { | ||||
| this.adjacency_matrix = []; | this.adjacency_matrix = []; | ||||
| this.node_ids = []; | this.node_ids = []; | ||||
| this.nodes = []; | this.nodes = []; | ||||
| this.indexes = []; | this.indexes = []; | ||||
| } | } | ||||
| addNode(id, priority) { | addNode(id, priority) { | ||||
| this.adjacency_matrix.push(Array(this.getNoOfNodes()).fill(0)); | this.adjacency_matrix.push(Array(this.getNoOfNodes()).fill(0)); | ||||
| for (const row of this.adjacency_matrix) { | for (const row of this.adjacency_matrix) { | ||||
| row.push(0); | row.push(0); | ||||
| } | } | ||||
| this.node_ids.push(id); | this.node_ids.push(id); | ||||
| this.nodes.push({ id, priority }); | this.nodes.push({ id, priority }); | ||||
| this.indexes.push(this.nodes.length - 1); | this.indexes.push(this.nodes.length - 1); | ||||
| } | } | ||||
| getNoOfNodes() { | getNoOfNodes() { | ||||
| return this.nodes.length; | return this.nodes.length; | ||||
| } | } | ||||
| addEdge(id_i, id_j) { | addEdge(id_i, id_j) { | ||||
| const [i, j] = this._getIndexesOfNodePair(id_i, id_j); | const [i, j] = this._getIndexesOfNodePair(id_i, id_j); | ||||
| this.adjacency_matrix[i][j] = 1; | this.adjacency_matrix[i][j] = 1; | ||||
| } | } | ||||
| _getIndexesOfNodePair(id_i, id_j) { | _getIndexesOfNodePair(id_i, id_j) { | ||||
| return [this.node_ids.indexOf(id_i), this.node_ids.indexOf(id_j)]; | return [this.node_ids.indexOf(id_i), this.node_ids.indexOf(id_j)]; | ||||
| } | } | ||||
| pathExists(id_i, id_j) { | pathExists(id_i, id_j) { | ||||
| const [i, j] = this._getIndexesOfNodePair(id_i, id_j); | const [i, j] = this._getIndexesOfNodePair(id_i, id_j); | ||||
| return this._pathExists(i, j); | return this._pathExists(i, j); | ||||
| } | } | ||||
| _pathExists(i, j) { | _pathExists(i, j) { | ||||
| if (this.adjacency_matrix[i][j]) { | if (this.adjacency_matrix[i][j]) { | ||||
| return true; | return true; | ||||
| } | } | ||||
| for (let k = 0; k < this.getNoOfNodes(); ++k) { | for (let k = 0; k < this.getNoOfNodes(); ++k) { | ||||
| if (this.adjacency_matrix[i][k]) { | if (this.adjacency_matrix[i][k]) { | ||||
| return this._pathExists(k, j); | return this._pathExists(k, j); | ||||
| } | } | ||||
| } | } | ||||
| return false; | return false; | ||||
| } | } | ||||
| bestFirstSearch() { | bestFirstSearch() { | ||||
| this.front = []; | this.front = []; | ||||
| this.visited = []; | this.visited = []; | ||||
| while (this.visited.length < this.nodes.length) { | while (this.visited.length < this.nodes.length) { | ||||
| const { front_node, next_node } = this._getNextNode(); | const { front_node, next_node } = this._getNextNode(); | ||||
| this.visited.push(next_node); | this.visited.push(next_node); | ||||
| if (front_node !== null) { | if (front_node !== null) { | ||||
| if (this._areAllSuccessorsVisited(front_node)) { | if (this._areAllSuccessorsVisited(front_node)) { | ||||
| const index = this.front.indexOf(front_node); | const index = this.front.indexOf(front_node); | ||||
| this.front.splice(index, 1); | this.front.splice(index, 1); | ||||
| } | } | ||||
| } | } | ||||
| if (!this._areAllSuccessorsVisited(next_node)) { | if (!this._areAllSuccessorsVisited(next_node)) { | ||||
| this.front.push(next_node); | this.front.push(next_node); | ||||
| } | } | ||||
| } | } | ||||
| return this.visited.map(i => this.nodes[i].id); | return this.visited.map(i => this.nodes[i].id); | ||||
| } | } | ||||
| _areAllSuccessorsVisited(i) { | _areAllSuccessorsVisited(i) { | ||||
| for (let j = 0; j < this.nodes.length; ++j) { | for (let j = 0; j < this.nodes.length; ++j) { | ||||
| if (this.adjacency_matrix[i][j] && !this._isVisited(j)) { | if (this.adjacency_matrix[i][j] && !this._isVisited(j)) { | ||||
| return false; | return false; | ||||
| } | } | ||||
| } | } | ||||
| return true; | return true; | ||||
| } | } | ||||
| _isVisited(i) { | _isVisited(i) { | ||||
| return this.visited.includes(i); | return this.visited.includes(i); | ||||
| } | } | ||||
| _isNodeWithoutPredecessors(i) { | _isNodeWithoutPredecessors(i) { | ||||
| for (let j = 0; j < this.nodes.length; ++j) { | for (let j = 0; j < this.nodes.length; ++j) { | ||||
| if (this.adjacency_matrix[j][i]) { | if (this.adjacency_matrix[j][i]) { | ||||
| return false; | return false; | ||||
| } | } | ||||
| } | } | ||||
| return true; | return true; | ||||
| } | } | ||||
| _getNextNode() { | _getNextNode() { | ||||
| const nodesWithoutPredecessorsYetToBeVisited = this.indexes.filter( | const nodesWithoutPredecessorsYetToBeVisited = this.indexes.filter( | ||||
| i => this._isNodeWithoutPredecessors(i) && !this._isVisited(i) | i => this._isNodeWithoutPredecessors(i) && !this._isVisited(i) | ||||
| ); | ); | ||||
| const candidate1 = this._lookForNextNodeInCandidates( | const candidate1 = this._lookForNextNodeInCandidates( | ||||
| nodesWithoutPredecessorsYetToBeVisited | nodesWithoutPredecessorsYetToBeVisited | ||||
| ); | ); | ||||
| Show All 25 Lines | if (candidate1.priority === candidate2.priority) { | ||||
| } | } | ||||
| } | } | ||||
| const front_node = this.indexes.find( | const front_node = this.indexes.find( | ||||
| i => this.adjacency_matrix[i][candidate2.index] | i => this.adjacency_matrix[i][candidate2.index] | ||||
| ); | ); | ||||
| return { front_node, next_node: candidate2.index }; | return { front_node, next_node: candidate2.index }; | ||||
| } | } | ||||
| _lookForNextNodeInCandidates(candidates) { | _lookForNextNodeInCandidates(candidates) { | ||||
| let next_node = null, | let next_node = null, | ||||
| best_priority = Infinity, | best_priority = Infinity, | ||||
| current_mean, | current_mean, | ||||
| best_mean = Infinity; | best_mean = Infinity; | ||||
| for (const candidate of candidates) { | for (const candidate of candidates) { | ||||
| if (this.nodes[candidate].priority < best_priority) { | if (this.nodes[candidate].priority < best_priority) { | ||||
| best_priority = this.nodes[candidate].priority; | best_priority = this.nodes[candidate].priority; | ||||
| Show All 11 Lines | for (const candidate of candidates) { | ||||
| } | } | ||||
| } | } | ||||
| return { | return { | ||||
| index: next_node, | index: next_node, | ||||
| priority: best_priority, | priority: best_priority, | ||||
| mean_priority_of_succcessors: best_mean, | mean_priority_of_succcessors: best_mean, | ||||
| }; | }; | ||||
| } | } | ||||
| _meanPriorityOfSuccessors(i) { | _meanPriorityOfSuccessors(i) { | ||||
| let sum = 0, | let sum = 0, | ||||
| length = 0; | length = 0; | ||||
| for (let j of this.indexes) { | for (let j of this.indexes) { | ||||
| if (this.adjacency_matrix[i][j] && !this._isVisited(j)) { | if (this.adjacency_matrix[i][j] && !this._isVisited(j)) { | ||||
| sum += this.nodes[j].priority; | sum += this.nodes[j].priority; | ||||
| ++length; | ++length; | ||||
| } | } | ||||
| } | } | ||||
| return length > 0 ? sum / length : 0; | return length > 0 ? sum / length : 0; | ||||
| } | } | ||||
| } | } | ||||
| Graph.MAX_PRIORITY = 0; | Graph.MAX_PRIORITY = 0; | ||||
| module.exports = Graph; | module.exports = Graph; | ||||