Socket
Socket
Sign inDemoInstall

@atomly/data-structures-sdk

Package Overview
Dependencies
0
Maintainers
2
Versions
8
Alerts
File Explorer

Advanced tools

npm Scripts

Install Socket

Detect and block malicious and high-risk dependencies

Install

Comparing version 1.0.1-alpha.0 to 1.0.1-alpha.1

report.20200910.183627.30156.0.001.json

85

dist/graph/EdgesMap.js

@@ -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

383

dist/graph/Graph.js

@@ -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

5

dist/graph/types.d.ts

@@ -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

4

package.json
{
"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"
}
dist/graph/EdgesMap.js.map

Sorry, the diff of this file is not supported yet

dist/graph/Graph.js.map

Sorry, the diff of this file is not supported yet

tsconfig.tsbuildinfo

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap

About

Packages

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc