Differential D213 Diff 722 lib/datastore/graph.js

Changeset View

Standalone View

lib/datastore/graph.js

This file was added.

				class Graph {
				constructor() {
				this.adjacency_matrix = [];
				this.node_ids = [];
				this.nodes = [];
				this.indexes = [];
				}
				addNode(id, priority) {
				this.adjacency_matrix.push(Array(this.getNoOfNodes()).fill(0));
				kuba-orlikUnsubmitted Not Done Inline Actions (could) Korzystamy tutaj z macierzy sąsiedztwa - możnaby to przerobić tak, aby po prostu utworzyć małą klasę "GraphNode", która miałaby swoje `parents` i `children` kuba-orlik: (could) Korzystamy tutaj z macierzy sąsiedztwa - możnaby to przerobić tak, aby po prostu…
				for (const row of this.adjacency_matrix) {
				row.push(0);
				}
				this.node_ids.push(id);
				this.nodes.push({ id, priority });
				this.indexes.push(this.nodes.length - 1);
				}
				getNoOfNodes() {
				return this.nodes.length;
				}
				addEdge(id_i, id_j) {
				const [i, j] = this._getIndexesOfNodePair(id_i, id_j);
				this._addEdge(i, j);
				}
				_getIndexesOfNodePair(id_i, id_j) {
				return [this.node_ids.indexOf(id_i), this.node_ids.indexOf(id_j)];
				}
				_addEdge(i, j) {
				this.adjacency_matrix[i][j] = 1;
				}
				pathExists(id_i, id_j) {
				const [i, j] = this._getIndexesOfNodePair(id_i, id_j);
				return this._pathExists(i, j);
				}
				_pathExists(i, j) {
				if (this.adjacency_matrix[i][j]) {
				return true;
				}
				for (let k = 0; k < this.getNoOfNodes(); ++k) {
				if (this.adjacency_matrix[i][k]) {
				return this._pathExists(k, j);
				}
				}
				return false;
				}
				bestFirstSearch() {
				kuba-orlikUnsubmitted Done Inline Actions (should) skoro nie robimy tego rekurencynie, to rozbicie na `bestFirstSearch` i `_bestFirstSeacth` możemy usunąć ;) Podobnie dla reszty par funkcji `_fn` i `fn` kuba-orlik: (should) skoro nie robimy tego rekurencynie, to rozbicie na `bestFirstSearch` i…
				this.front = [];
				this.visited = [];
				this._bestFirstSearch();
				return this.visited.map(i => this.nodes[i].id);
				}
				_areAllSuccessorsVisited(i) {
				for (let j = 0; j < this.nodes.length; ++j) {
				if (this.adjacency_matrix[i][j] && !this._isVisited(j)) {
				return false;
				}
				}
				return true;
				}
				_isVisited(i) {
				return this.visited.includes(i);
				}
				_isNodeWithoutPredecessors(i) {
				for (let j = 0; j < this.nodes.length; ++j) {
				if (this.adjacency_matrix[j][i]) {
				return false;
				}
				}
				return true;
				}
				_bestFirstSearch() {
				while (this.visited.length < this.nodes.length) {
				const { front_node, next_node } = this._getNextNode();
				this.visited.push(next_node);

				if (front_node !== null) {
				if (this._areAllSuccessorsVisited(front_node)) {
				const index = this.front.indexOf(front_node);
				this.front.splice(index, 1);
				}
				}

				if (!this._areAllSuccessorsVisited(next_node)) {
				this.front.push(next_node);
				}
				}
				}
				_getNextNode() {
				const nodesWithoutPredecessorsYetToBeVisited = this.indexes.filter(
				i => this._isNodeWithoutPredecessors(i) && !this._isVisited(i)
				);

				const candidate1 = this._lookForNextNodeInCandidates(
				nodesWithoutPredecessorsYetToBeVisited
				);
				if (candidate1.priority === Graph.MAX_PRIORITY) {
				return { front_node: null, next_node: candidate1.index };
				}

				const successorsYetToBeVisited = this.front.reduce((successors, i) => {
				this.indexes
				.filter(j => this.adjacency_matrix[i][j] && !this._isVisited(j))
				.map(j => successors.add(j));
				return successors;
				}, new Set());

				const candidate2 = this._lookForNextNodeInCandidates(
				successorsYetToBeVisited
				);

				if (candidate1.priority < candidate2.priority) {
				return { front_node: null, next_node: candidate1.index };
				}

				if (candidate1.priority === candidate2.priority) {
				if (
				candidate1.mean_priority_of_succcessors <
				candidate2.mean_priority_of_succcessors
				) {
				return { front_node: null, next_node: candidate1.index };
				}
				}

				const front_node = this.indexes.find(
				i => this.adjacency_matrix[i][candidate2.index]
				);
				return { front_node, next_node: candidate2.index };
				}
				_lookForNextNodeInCandidates(candidates) {
				let next_node = null,
				highest_priority = Infinity,
				current_mean,
				highest_mean = Infinity;
				for (const candidate of candidates) {
				if (this.nodes[candidate].priority < highest_priority) {
				highest_priority = this.nodes[candidate].priority;
				highest_mean = this._meanPriorityOfSuccessors(candidate);
				next_node = candidate;
				if (this.nodes[candidate].priority === Graph.MAX_PRIORITY) {
				break;
				}
				} else if (this.nodes[candidate].priority === highest_priority) {
				current_mean = this._meanPriorityOfSuccessors(candidate);
				if (current_mean < highest_mean) {
				highest_mean = current_mean;
				next_node = candidate;
				}
				}
				kuba-orlikUnsubmitted Done Inline Actions (should) `highest` jest tutaj mylące, bo szukamy takiego node'a, gdzie priorytet ma najniższą liczbową wartość. albo należy odwrócić porządek priorytetów, albo zmienić tutaj nazewnictwo - np. na "best_priority", albo zmienić `priority` na `weight` kuba-orlik: (should) `highest` jest tutaj mylące, bo szukamy takiego node'a, gdzie priorytet ma najniższą…
				}
				return {
				index: next_node,
				priority: highest_priority,
				mean_priority_of_succcessors: highest_mean,
				};
				}
				_meanPriorityOfSuccessors(i) {
				let sum = 0,
				length = 0;
				for (let j of this.indexes) {
				if (this.adjacency_matrix[i][j] && !this._isVisited(j)) {
				sum += this.nodes[j].priority;
				++length;
				}
				}
				return length > 0 ? sum / length : 0;
				}
				}

				Graph.MAX_PRIORITY = 0;

				module.exports = Graph;