Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
@atomly/data-structures-sdk
Advanced tools
@atomly/data-structures-sdk - npm Package Compare versions
Comparing version 1.0.1-alpha.0 to 1.0.1-alpha.1
@@ -11,52 +11,49 @@ "use strict"; | ||
| */ | ||
| let EdgesMap = /** @class */ (() => { | ||
| class EdgesMap { | ||
| constructor() { | ||
| this.from = {}; | ||
| class EdgesMap { | ||
| constructor() { | ||
| this.from = {}; | ||
| } | ||
| addEdge(fromVertexKey, toVertexKey, weight = EdgesMap.__DEFAULT_EDGE_WEIGHT) { | ||
| if (!this.from[fromVertexKey]) { | ||
| this.from[fromVertexKey] = { to: {} }; | ||
| } | ||
| addEdge(fromVertexKey, toVertexKey, weight = EdgesMap.__DEFAULT_EDGE_WEIGHT) { | ||
| if (!this.from[fromVertexKey]) { | ||
| this.from[fromVertexKey] = { to: {} }; | ||
| } | ||
| const edge = new Edge_1.Edge(fromVertexKey, toVertexKey, weight); | ||
| this.from[fromVertexKey].to[toVertexKey] = edge; | ||
| return edge; | ||
| const edge = new Edge_1.Edge(fromVertexKey, toVertexKey, weight); | ||
| this.from[fromVertexKey].to[toVertexKey] = edge; | ||
| return edge; | ||
| } | ||
| getEdge(fromVertexKey, toVertexKey) { | ||
| if (this.hasEdge(fromVertexKey, toVertexKey)) { | ||
| return this.from[fromVertexKey].to[toVertexKey]; | ||
| } | ||
| getEdge(fromVertexKey, toVertexKey) { | ||
| if (this.hasEdge(fromVertexKey, toVertexKey)) { | ||
| return this.from[fromVertexKey].to[toVertexKey]; | ||
| } | ||
| return undefined; | ||
| return undefined; | ||
| } | ||
| hasEdge(fromVertexKey, toVertexKey) { | ||
| if (!this.from[fromVertexKey]) { | ||
| return false; | ||
| } | ||
| hasEdge(fromVertexKey, toVertexKey) { | ||
| if (!this.from[fromVertexKey]) { | ||
| return false; | ||
| } | ||
| return Boolean(this.from[fromVertexKey].to[toVertexKey]); | ||
| return Boolean(this.from[fromVertexKey].to[toVertexKey]); | ||
| } | ||
| removeEdge(fromVertexKey, toVertexKey) { | ||
| if (this.hasEdge(fromVertexKey, toVertexKey)) { | ||
| const removedEdge = this.from[fromVertexKey].to[toVertexKey]; | ||
| delete this.from[fromVertexKey].to[toVertexKey]; | ||
| return removedEdge; | ||
| } | ||
| removeEdge(fromVertexKey, toVertexKey) { | ||
| if (this.hasEdge(fromVertexKey, toVertexKey)) { | ||
| const removedEdge = this.from[fromVertexKey].to[toVertexKey]; | ||
| delete this.from[fromVertexKey].to[toVertexKey]; | ||
| return removedEdge; | ||
| } | ||
| return undefined; | ||
| } | ||
| clear() { | ||
| this.from = {}; | ||
| return this; | ||
| } | ||
| values() { | ||
| const edges = Object | ||
| .values(this.from) | ||
| .reduce((acc, { to }) => { | ||
| return acc.concat(Object.values(to)); | ||
| }, []); | ||
| return edges; | ||
| } | ||
| return undefined; | ||
| } | ||
| EdgesMap.__DEFAULT_EDGE_WEIGHT = constants_1.__DEFAULT_EDGE_WEIGHT; | ||
| return EdgesMap; | ||
| })(); | ||
| clear() { | ||
| this.from = {}; | ||
| return this; | ||
| } | ||
| values() { | ||
| const edges = Object | ||
| .values(this.from) | ||
| .reduce((acc, { to }) => { | ||
| return acc.concat(Object.values(to)); | ||
| }, []); | ||
| return edges; | ||
| } | ||
| } | ||
| exports.EdgesMap = EdgesMap; | ||
| EdgesMap.__DEFAULT_EDGE_WEIGHT = constants_1.__DEFAULT_EDGE_WEIGHT; | ||
| //# sourceMappingURL=EdgesMap.js.map |
@@ -15,212 +15,209 @@ "use strict"; | ||
| */ | ||
| let Graph = /** @class */ (() => { | ||
| class Graph { | ||
| constructor(args = {}) { | ||
| var _a; | ||
| // Setting up the graph "metadata" configuration: | ||
| this.isDirectedGraph = (_a = args.isDirectedGraph) !== null && _a !== void 0 ? _a : Graph.__DEFAULT_IS_DIRECTED_GRAPH; | ||
| // Instantiating adjacency list: | ||
| this.adjacencyList = new Map(); | ||
| // Instantiating and binding maps of vertices and edges: | ||
| this.verticesMap = new Map(); | ||
| if (args.vertices) { | ||
| args.vertices.forEach(vertex => { | ||
| this.addVertex(vertex.key, vertex.value); | ||
| }); | ||
| class Graph { | ||
| constructor(args = {}) { | ||
| var _a; | ||
| // Setting up the graph "metadata" configuration: | ||
| this.isDirectedGraph = (_a = args.isDirectedGraph) !== null && _a !== void 0 ? _a : Graph.__DEFAULT_IS_DIRECTED_GRAPH; | ||
| // Instantiating adjacency list: | ||
| this.adjacencyList = new Map(); | ||
| // Instantiating and binding maps of vertices and edges: | ||
| this.verticesMap = new Map(); | ||
| if (args.vertices) { | ||
| args.vertices.forEach(vertex => { | ||
| this.addVertex(vertex.key, vertex.value); | ||
| }); | ||
| } | ||
| this.edgesMap = new EdgesMap_1.EdgesMap(); | ||
| if (args.edges) { | ||
| args.edges.forEach(edge => { | ||
| this.addEdge(edge.from, edge.to, edge.weight); | ||
| }); | ||
| } | ||
| // Binding traversals: | ||
| this.traversal = { | ||
| breadthFirst: this._breadthFirstTraversal.bind(this), | ||
| depthFirst: this._depthFirstTraversal.bind(this), | ||
| }; | ||
| } | ||
| addVertex(key, value) { | ||
| const vertex = new Vertex_1.Vertex(key, value); | ||
| this.verticesMap.set(vertex.key, vertex); | ||
| if (!this.adjacencyList.get(vertex.key)) { | ||
| this.adjacencyList.set(vertex.key, new Set()); | ||
| } | ||
| return vertex; | ||
| } | ||
| addEdge(fromVertexKey, toVertexKey, weight = Graph.__DEFAULT_EDGE_WEIGHT) { | ||
| // Checking if the vertices exist and if the edge already exists. | ||
| const shouldAddEdge = (this.hasVertex(fromVertexKey) && | ||
| this.hasVertex(toVertexKey) && | ||
| !this.edgesMap.hasEdge(fromVertexKey, toVertexKey)); | ||
| // Using JavaScript `Set` data structures to make sure that the edges | ||
| // are unique respective to the interconnected vertices. | ||
| if (shouldAddEdge) { | ||
| this.adjacencyList.get(fromVertexKey).add(toVertexKey); | ||
| // Adding the outgoing Edge: | ||
| const addedEdge = this.edgesMap.addEdge(fromVertexKey, toVertexKey, weight); | ||
| // If it's NOT a directed graph, also add the incoming Edge: | ||
| if (!this.isDirectedGraph) { | ||
| this.adjacencyList.get(toVertexKey).add(fromVertexKey); | ||
| this.edgesMap.addEdge(toVertexKey, fromVertexKey, weight); | ||
| } | ||
| this.edgesMap = new EdgesMap_1.EdgesMap(); | ||
| if (args.edges) { | ||
| args.edges.forEach(edge => { | ||
| this.addEdge(edge.from, edge.to, edge.weight); | ||
| return addedEdge; | ||
| } | ||
| return undefined; | ||
| } | ||
| getVertex(key) { | ||
| return this.verticesMap.get(key); | ||
| } | ||
| getEdge(fromVertexKey, toVertexKey) { | ||
| return this.edgesMap.getEdge(fromVertexKey, toVertexKey); | ||
| } | ||
| hasVertex(key) { | ||
| return this.verticesMap.has(key); | ||
| } | ||
| hasEdge(fromVertexKey, toVertexKey) { | ||
| return this.edgesMap.hasEdge(fromVertexKey, toVertexKey); | ||
| } | ||
| removeVertex(key) { | ||
| const removedVertex = this.getVertex(key); | ||
| if (removedVertex) { | ||
| const set = this.adjacencyList.get(key); | ||
| if (set) { | ||
| // Removing all all edges connecting to this vertex: | ||
| set.forEach(connectedVertexKey => { | ||
| const connectedEdges = this.adjacencyList.get(connectedVertexKey); | ||
| if (connectedEdges) { | ||
| connectedEdges.delete(key); | ||
| this.removeEdge(key, connectedVertexKey); | ||
| } | ||
| }); | ||
| } | ||
| // Binding traversals: | ||
| this.traversal = { | ||
| breadthFirst: this._breadthFirstTraversal.bind(this), | ||
| depthFirst: this._depthFirstTraversal.bind(this), | ||
| }; | ||
| this.verticesMap.delete(key); | ||
| this.adjacencyList.delete(key); | ||
| } | ||
| addVertex(key, value) { | ||
| const vertex = new Vertex_1.Vertex(key, value); | ||
| this.verticesMap.set(vertex.key, vertex); | ||
| if (!this.adjacencyList.get(vertex.key)) { | ||
| this.adjacencyList.set(vertex.key, new Set()); | ||
| return removedVertex; | ||
| } | ||
| removeEdge(fromVertexKey, toVertexKey) { | ||
| // Checking if the vertices exist in the list. | ||
| const shouldRemoveEdge = (this.hasVertex(fromVertexKey) && | ||
| this.hasVertex(toVertexKey)); | ||
| if (shouldRemoveEdge) { | ||
| this.adjacencyList.get(fromVertexKey).delete(toVertexKey); | ||
| const removedEdge = this.edgesMap.removeEdge(fromVertexKey, toVertexKey); | ||
| if (!this.isDirectedGraph) { | ||
| this.adjacencyList.get(toVertexKey).delete(fromVertexKey); | ||
| this.edgesMap.removeEdge(toVertexKey, fromVertexKey); | ||
| } | ||
| return vertex; | ||
| return removedEdge; | ||
| } | ||
| addEdge(fromVertexKey, toVertexKey, weight = Graph.__DEFAULT_EDGE_WEIGHT) { | ||
| // Checking if the vertices exist and if the edge already exists. | ||
| const shouldAddEdge = (this.hasVertex(fromVertexKey) && | ||
| this.hasVertex(toVertexKey) && | ||
| !this.edgesMap.hasEdge(fromVertexKey, toVertexKey)); | ||
| // Using JavaScript `Set` data structures to make sure that the edges | ||
| // are unique respective to the interconnected vertices. | ||
| if (shouldAddEdge) { | ||
| this.adjacencyList.get(fromVertexKey).add(toVertexKey); | ||
| // Adding the outgoing Edge: | ||
| const addedEdge = this.edgesMap.addEdge(fromVertexKey, toVertexKey, weight); | ||
| // If it's NOT a directed graph, also add the incoming Edge: | ||
| if (!this.isDirectedGraph) { | ||
| this.adjacencyList.get(toVertexKey).add(fromVertexKey); | ||
| this.edgesMap.addEdge(toVertexKey, fromVertexKey, weight); | ||
| } | ||
| return addedEdge; | ||
| } | ||
| return undefined; | ||
| return undefined; | ||
| } | ||
| updateVertexValue(key, value) { | ||
| const updatedVertex = this.getVertex(key); | ||
| if (updatedVertex) { | ||
| updatedVertex.value = value; | ||
| return updatedVertex; | ||
| } | ||
| getVertex(key) { | ||
| return this.verticesMap.get(key); | ||
| return undefined; | ||
| } | ||
| clear() { | ||
| this.verticesMap.clear(); | ||
| this.edgesMap.clear(); | ||
| this.adjacencyList.clear(); | ||
| return this; | ||
| } | ||
| values() { | ||
| return { | ||
| vertices: Array.from(this.verticesMap.values()), | ||
| edges: this.edgesMap.values(), | ||
| }; | ||
| } | ||
| /** | ||
| * Breadth First Traversal of the graph. Returns every | ||
| * vertex that is connected (directly or indirectly) to the starting | ||
| * vertex. | ||
| * @param key - Vertex identifier. | ||
| * @param callback - Optional callback invoked on every level of the BF traversal. All of the vertices of the level as well as the depth are passed as parameters. | ||
| */ | ||
| _breadthFirstTraversal(key, callback) { | ||
| if (!this.hasVertex(key)) { | ||
| return []; | ||
| } | ||
| getEdge(fromVertexKey, toVertexKey) { | ||
| return this.edgesMap.getEdge(fromVertexKey, toVertexKey); | ||
| const startingVertex = this.getVertex(key); | ||
| const visitedVerticesHashTable = {}; // Cache hash table. | ||
| const queue = []; | ||
| // The starting vertex of the traversal always starts at depth zero. | ||
| // The traversal will begin here and the vertex will be flagged as visited. | ||
| let depth = 0; | ||
| let vertices = [startingVertex]; | ||
| queue.push(vertices); // TODO: Add a Queue data-structure | ||
| if (callback) { | ||
| callback(vertices, depth); | ||
| } | ||
| hasVertex(key) { | ||
| return this.verticesMap.has(key); | ||
| visitedVerticesHashTable[startingVertex.key] = null; | ||
| while (queue.length > 0) { | ||
| const level = queue.shift(); | ||
| const adjacentVertices = []; | ||
| level.forEach((vertex) => { | ||
| const edges = this.adjacencyList.get(vertex.key); | ||
| edges.forEach(vertexKey => { | ||
| if (!(vertexKey in visitedVerticesHashTable)) { | ||
| visitedVerticesHashTable[vertexKey] = null; | ||
| const vertex = this.getVertex(vertexKey); | ||
| adjacentVertices.push(vertex); | ||
| } | ||
| }); | ||
| queue.push(adjacentVertices); | ||
| }); | ||
| vertices = vertices.concat(adjacentVertices); | ||
| if (adjacentVertices.length && callback) { | ||
| depth += 1; | ||
| callback(adjacentVertices, depth); | ||
| } | ||
| } | ||
| hasEdge(fromVertexKey, toVertexKey) { | ||
| return this.edgesMap.hasEdge(fromVertexKey, toVertexKey); | ||
| return vertices; | ||
| } | ||
| /** | ||
| * Depth First Traversal of the graph. Returns every | ||
| * vertex that is connected (directly or indirectly) to the starting | ||
| * vertex. | ||
| * @param key - Vertex identifier. | ||
| * @param callback - Optional callback invoked on every vertex of the DF traversal. | ||
| */ | ||
| _depthFirstTraversal(key, callback) { | ||
| if (!this.hasVertex(key)) { | ||
| return []; | ||
| } | ||
| removeVertex(key) { | ||
| const removedVertex = this.getVertex(key); | ||
| if (removedVertex) { | ||
| const set = this.adjacencyList.get(key); | ||
| if (set) { | ||
| // Removing all all edges connecting to this vertex: | ||
| set.forEach(connectedVertexKey => { | ||
| const connectedEdges = this.adjacencyList.get(connectedVertexKey); | ||
| if (connectedEdges) { | ||
| connectedEdges.delete(key); | ||
| this.removeEdge(key, connectedVertexKey); | ||
| } | ||
| }); | ||
| const vertices = []; | ||
| const visitedVerticesHashTable = {}; // Cache hash table. | ||
| const traverse = (vertexKey) => { | ||
| const edges = this.adjacencyList.get(vertexKey); | ||
| const vertex = this.getVertex(vertexKey); | ||
| if (vertex) { | ||
| vertices.push(vertex); | ||
| visitedVerticesHashTable[vertexKey] = null; | ||
| if (callback) { | ||
| callback(vertex); | ||
| } | ||
| this.verticesMap.delete(key); | ||
| this.adjacencyList.delete(key); | ||
| } | ||
| return removedVertex; | ||
| } | ||
| removeEdge(fromVertexKey, toVertexKey) { | ||
| // Checking if the vertices exist in the list. | ||
| const shouldRemoveEdge = (this.hasVertex(fromVertexKey) && | ||
| this.hasVertex(toVertexKey)); | ||
| if (shouldRemoveEdge) { | ||
| this.adjacencyList.get(fromVertexKey).delete(toVertexKey); | ||
| const removedEdge = this.edgesMap.removeEdge(fromVertexKey, toVertexKey); | ||
| if (!this.isDirectedGraph) { | ||
| this.adjacencyList.get(toVertexKey).delete(fromVertexKey); | ||
| this.edgesMap.removeEdge(toVertexKey, fromVertexKey); | ||
| if (!edges || edges.size === 0) { | ||
| return; | ||
| } | ||
| return removedEdge; | ||
| } | ||
| return undefined; | ||
| } | ||
| updateVertexValue(key, value) { | ||
| const updatedVertex = this.getVertex(key); | ||
| if (updatedVertex) { | ||
| updatedVertex.value = value; | ||
| return updatedVertex; | ||
| } | ||
| return undefined; | ||
| } | ||
| clear() { | ||
| this.verticesMap.clear(); | ||
| this.edgesMap.clear(); | ||
| this.adjacencyList.clear(); | ||
| return this; | ||
| } | ||
| values() { | ||
| return { | ||
| vertices: Array.from(this.verticesMap.values()), | ||
| edges: this.edgesMap.values(), | ||
| }; | ||
| } | ||
| /** | ||
| * Breadth First Traversal of the graph. Returns every | ||
| * vertex that is connected (directly or indirectly) to the starting | ||
| * vertex. | ||
| * @param key - Vertex identifier. | ||
| * @param callback - Optional callback invoked on every level of the BF traversal. All of the vertices of the level as well as the depth are passed as parameters. | ||
| */ | ||
| _breadthFirstTraversal(key, callback) { | ||
| if (!this.hasVertex(key)) { | ||
| return []; | ||
| } | ||
| const startingVertex = this.getVertex(key); | ||
| const visitedVerticesHashTable = {}; // Cache hash table. | ||
| const queue = []; | ||
| // The starting vertex of the traversal always starts at depth zero. | ||
| // The traversal will begin here and the vertex will be flagged as visited. | ||
| let depth = 0; | ||
| let vertices = [startingVertex]; | ||
| queue.push(vertices); // TODO: Add a Queue data-structure | ||
| if (callback) { | ||
| callback(vertices, depth); | ||
| } | ||
| visitedVerticesHashTable[startingVertex.key] = null; | ||
| while (queue.length > 0) { | ||
| const level = queue.shift(); | ||
| const adjacentVertices = []; | ||
| level.forEach((vertex) => { | ||
| const edges = this.adjacencyList.get(vertex.key); | ||
| edges.forEach(vertexKey => { | ||
| if (!(vertexKey in visitedVerticesHashTable)) { | ||
| visitedVerticesHashTable[vertexKey] = null; | ||
| const vertex = this.getVertex(vertexKey); | ||
| adjacentVertices.push(vertex); | ||
| } | ||
| }); | ||
| queue.push(adjacentVertices); | ||
| edges.forEach(connectedVertexKey => { | ||
| // If the connected vertex is not in the results list (not visited) | ||
| if (!(connectedVertexKey in visitedVerticesHashTable)) { | ||
| traverse(connectedVertexKey); | ||
| } | ||
| }); | ||
| vertices = vertices.concat(adjacentVertices); | ||
| if (adjacentVertices.length && callback) { | ||
| depth += 1; | ||
| callback(adjacentVertices, depth); | ||
| } | ||
| } | ||
| return vertices; | ||
| } | ||
| /** | ||
| * Depth First Traversal of the graph. Returns every | ||
| * vertex that is connected (directly or indirectly) to the starting | ||
| * vertex. | ||
| * @param key - Vertex identifier. | ||
| * @param callback - Optional callback invoked on every vertex of the DF traversal. | ||
| */ | ||
| _depthFirstTraversal(key, callback) { | ||
| if (!this.hasVertex(key)) { | ||
| return []; | ||
| } | ||
| const vertices = []; | ||
| const visitedVerticesHashTable = {}; // Cache hash table. | ||
| const traverse = (vertexKey) => { | ||
| const edges = this.adjacencyList.get(vertexKey); | ||
| const vertex = this.getVertex(vertexKey); | ||
| if (vertex) { | ||
| vertices.push(vertex); | ||
| visitedVerticesHashTable[vertexKey] = null; | ||
| if (callback) { | ||
| callback(vertex); | ||
| } | ||
| if (!edges || edges.size === 0) { | ||
| return; | ||
| } | ||
| edges.forEach(connectedVertexKey => { | ||
| // If the connected vertex is not in the results list (not visited) | ||
| if (!(connectedVertexKey in visitedVerticesHashTable)) { | ||
| traverse(connectedVertexKey); | ||
| } | ||
| }); | ||
| } | ||
| }; | ||
| traverse(key); | ||
| return vertices; | ||
| } | ||
| }; | ||
| traverse(key); | ||
| return vertices; | ||
| } | ||
| Graph.__DEFAULT_EDGE_WEIGHT = constants_1.__DEFAULT_EDGE_WEIGHT; | ||
| Graph.__DEFAULT_IS_DIRECTED_GRAPH = constants_1.__DEFAULT_IS_DIRECTED_GRAPH; | ||
| Graph.Vertex = Vertex_1.Vertex; | ||
| Graph.Edge = Edge_1.Edge; | ||
| return Graph; | ||
| })(); | ||
| } | ||
| exports.Graph = Graph; | ||
| Graph.__DEFAULT_EDGE_WEIGHT = constants_1.__DEFAULT_EDGE_WEIGHT; | ||
| Graph.__DEFAULT_IS_DIRECTED_GRAPH = constants_1.__DEFAULT_IS_DIRECTED_GRAPH; | ||
| Graph.Vertex = Vertex_1.Vertex; | ||
| Graph.Edge = Edge_1.Edge; | ||
| //# sourceMappingURL=Graph.js.map |
@@ -71,4 +71,7 @@ export interface IVertex<T = unknown> { | ||
| * TODOs for v2: | ||
| * - [ ] Add an optimized `Queue` data structure for the traversals. | ||
| * - [ ] Add internal Djikstra's Algorithm to find the shortest path between two vertices, | ||
| * this will be used by the `query` API. | ||
| * this will be used by the `query` API (this will need a `PriorityQueue` data structure). | ||
| * - [ ] Add internal Bellman-Ford algorithm, similar to Djikstra's Algorithm except it supports | ||
| * negative edge weights and edge weights equal to zero. | ||
| * - [ ] Add `query` API to: query if certain vertices are connected, or filtering by weight | ||
@@ -75,0 +78,0 @@ * (i.e. added/accumulated weight), or resolving all vertices connected to a certain vertex |
| { | ||
| "name": "@atomly/data-structures-sdk", | ||
| "version": "1.0.1-alpha.0", | ||
| "version": "1.0.1-alpha.1", | ||
| "description": "> TODO: description", | ||
@@ -38,3 +38,3 @@ "author": "Robert Molina <rmolinamir@gmail.com>", | ||
| }, | ||
| "gitHead": "e08cf79b4fad1a6cdee8536cf559dba0e27fef73" | ||
| "gitHead": "9b8bfbd4d2bfdf396270fd9f50059c68fc782728" | ||
| } |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by8.57%
322928
- Number of package files
- increased by2.22%
46
- Lines of code
- increased by34.41%
3000
No dependency changes