Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
@datastructures-js/graph
Advanced tools
@datastructures-js/graph - npm Package Compare versions
Comparing version 1.0.2 to 2.0.0
208
index.js
@@ -1,207 +0,1 @@ | ||
| /** | ||
| * datastructures-js/graph | ||
| * @copyright 2018 Eyas Ranjous <eyas.ranjous@gmail.com> | ||
| * @license MIT | ||
| */ | ||
| const shortestPath = require('./shortest-path'); | ||
| const traverse = require('./traverse'); | ||
| /** | ||
| * graph vertex | ||
| * @function | ||
| */ | ||
| const vertex = (k, v) => { | ||
| const key = k; | ||
| let value = v; | ||
| /** | ||
| * @returns {(string|number)} | ||
| */ | ||
| const getKey = () => key; | ||
| /** | ||
| * @param {object} val | ||
| */ | ||
| const setValue = (val) => { | ||
| value = val; | ||
| }; | ||
| /** | ||
| * @returns {object} | ||
| */ | ||
| const getValue = () => value; | ||
| // vertex api | ||
| return { | ||
| getKey, | ||
| setValue, | ||
| getValue | ||
| }; | ||
| }; | ||
| /** | ||
| * graph & directed graph | ||
| * @function | ||
| */ | ||
| const graph = (options) => { | ||
| let vertices = {}; | ||
| let edges = {}; | ||
| let verticesCount = 0; | ||
| const { directed } = (options && options) || false; | ||
| const self = {}; | ||
| const dfs = dfsFn(self); | ||
| /** | ||
| * add a vertex to the graph | ||
| * @param {(string|number)} key | ||
| * @param {object} value | ||
| */ | ||
| const addVertex = (key, value) => { | ||
| if (!vertices[key]) { | ||
| vertices[key] = vertex(key, value); | ||
| edges[key] = {}; | ||
| verticesCount += 1; | ||
| } | ||
| }; | ||
| /** | ||
| * removes a vertex from the graph | ||
| * @param {(string|number} key | ||
| */ | ||
| const removeVertex = (key) => { | ||
| if (vertices[key]) { | ||
| vertices[key] = undefined; | ||
| verticesCount -= 1; | ||
| } | ||
| }; | ||
| /** | ||
| * checks if the graph has a vertex | ||
| * @param {(string|number)} key | ||
| * @returns {boolean} | ||
| */ | ||
| const hasVertex = key => !!vertices[key]; | ||
| /** | ||
| * gets the count of the vertices in the graph | ||
| * @returns {number} | ||
| */ | ||
| const countVertices = () => verticesCount; | ||
| /** | ||
| * adds an edge between two existing vertices | ||
| * @param {(string|number)} key1 - first vertext key | ||
| * @param {(string|number)} key2 - second vertex key | ||
| * @param {number} the numeric weight of the edge | ||
| */ | ||
| const addEdge = (key1, key2, weight) => { | ||
| if (hasVertex(key1) && hasVertex(key2)) { | ||
| const w = +weight || 0; | ||
| edges[key1][key2] = w; | ||
| if (!directed) { | ||
| edges[key2][key1] = w; | ||
| } | ||
| } | ||
| }; | ||
| /** | ||
| * checks if the graph has an edge between two existing vertices | ||
| * @param {(string|number)} key1 | ||
| * @param {(string|number)} key2 | ||
| * @returns {boolean} | ||
| */ | ||
| const hasEdge = (key1, key2) => { | ||
| if (hasVertex(key1) && hasVertex(key2)) { | ||
| if (directed && edges[key1][key2] >= 0) { | ||
| return true; | ||
| } else if (edges[key1][key2] >= 0 && edges[key2][key1] >= 0) { | ||
| return true; | ||
| } | ||
| } | ||
| return false; | ||
| }; | ||
| /** | ||
| * checks if the graph has edges from a vertex | ||
| * @param {(string|number)} key | ||
| * @returns {boolean} | ||
| */ | ||
| const hasEdges = (key) => { | ||
| }; | ||
| /** | ||
| * gets the weight of the edge between two vertices | ||
| * @returns {number|null} | ||
| */ | ||
| const getWeight = (key1, key2) => { | ||
| if (hasVertex(key1) && key1 === key2) { | ||
| return 0; | ||
| } else if (hasEdge(key1, key2)) { | ||
| return edges[key1][key2]; | ||
| } | ||
| return null; | ||
| }; | ||
| /** | ||
| * removes an existing edge between two vertices | ||
| * @param {(string|number)} key1 | ||
| * @param {(string|number)} key2 | ||
| */ | ||
| const removeEdge = (key1, key2) => { | ||
| if (hasEdge(key1, key2)) { | ||
| edges[key1][key2] = -1; | ||
| edges[key2][key1] = -1; | ||
| } | ||
| }; | ||
| /** | ||
| * traverse the graph using using a traversal algorithm | ||
| * @param {(string|number)} key - starting vertex key | ||
| * @param {function} cb - called with each vertex value | ||
| * @param {string} - traversal type, default is bfs | ||
| */ | ||
| const traverse = (key, cb, type) => { | ||
| const trv = traverse[type] || traverse.bfs; | ||
| return trv(self)(key, cb); | ||
| }; | ||
| /** | ||
| * finds all the shortest paths between two vertices in the graph | ||
| * @param {(string|number)} key1 - source vertex key | ||
| * @param {(string|number)} key2 - destination vertex key | ||
| * @param {string} type - algorithm name - default is dfs | ||
| * @returns {array} | ||
| */ | ||
| const findShortestPath = (key1, key2, type) => { | ||
| const algFn = shortestPath[type] || shortestPath.dfs; | ||
| return algFn(self)(key1, key2); | ||
| }; | ||
| /** | ||
| * clears the graph | ||
| */ | ||
| const clear = () => { | ||
| vertices = {}; | ||
| edges = {}; | ||
| verticesCount = 0; | ||
| }; | ||
| // graph api | ||
| return { | ||
| addVertex, | ||
| removeVertex, | ||
| hasVertex, | ||
| countVertices, | ||
| addEdge, | ||
| hasEdge, | ||
| hasEdges, | ||
| removeEdge, | ||
| getWeight, | ||
| traverse, | ||
| findShortestPath, | ||
| clear | ||
| }; | ||
| }; | ||
| module.exports = graph; | ||
| module.exports = require('./src/graph'); |
| { | ||
| "name": "@datastructures-js/graph", | ||
| "version": "1.0.2", | ||
| "version": "2.0.0", | ||
| "description": "graph & directed graph implementation in javascript", | ||
@@ -5,0 +5,0 @@ "main": "index.js", |
@@ -121,26 +121,2 @@ ## Graph & Directed Graph | ||
| **.dfsTraverse(key, cb)** | ||
| traverse the graph from a strating vertex using depth-first search and call cb for each vertex object. | ||
| ```js | ||
| graph.traverseDfs('v1', v => console.log(v.getKey(), v.getValue())); | ||
| // v1 true | ||
| // v2 true | ||
| // v3 true | ||
| // v4 true | ||
| // v5 true | ||
| ``` | ||
| **.bfsTraverse(key, cb)** | ||
| traverse the graph from a strating vertex using breadth-first search and call cb for each vertex object. | ||
| ```js | ||
| graph.traverseDfs('v5', v => console.log(v.getKey(), v.getValue())); | ||
| // v5 true | ||
| // v4 true | ||
| // v3 true | ||
| // v2 true | ||
| // v1 true | ||
| ``` | ||
| **.traverse(key, cb, type)** | ||
@@ -165,20 +141,10 @@ | ||
| **.dfsShortestPath(key1, key2)** | ||
| **.findShortestPath(v1, v2, algorithm)** | ||
| finds the shortest path between two vertices based on a depth-first search algorithm. | ||
| ```js | ||
| console.log(graph.findShortestPath('v1', 'v5')); | ||
| // [ ['v1', 'v2', 'v4', 'v3', 'v5'] ] | ||
| find all possible shortests paths (same minimum weight sum) between two vertices using an algorithm. | ||
| console.log(directedGraph.dfsShortestPath('v1', 'v5')); | ||
| // [['v1', 'v4', 'v3', 'v5']] | ||
| ``` | ||
| Right now, only a DFS algorithm is implemented (default). DFS finds the shortest path between two vertices based on depth-first search. | ||
| **.findShortestPath(v1, v2, algorithm)** | ||
| find all possible shortests paths (same weight sum) between two vertices in the graph using an algorithm. | ||
| Right now, only a DFS algorithm is implemented. so it does the same as `.dfsShortestPath`. | ||
| ```javascript | ||
| console.log(graph.findShortestPath('v1', 'v5')); | ||
| console.log(graph.findShortestPath('v1', 'v5', 'dfs')); | ||
| // [ ['v1', 'v2', 'v4', 'v3', 'v5'] ] | ||
@@ -185,0 +151,0 @@ ``` |
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
Major refactor
Supply chain riskPackage has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.
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
Major refactor
Supply chain riskPackage has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by39.04%
30162
- Lines of code
- increased by39.96%
669
Worsened metrics
- Number of package files
- decreased by-13.64%
19
- Number of lines in readme file
- decreased by-17%
166
No dependency changes