@datastructures-js/graph - npm Package Compare versions

Comparing version 5.1.5 to 5.2.0

CHANGELOG.md

@@ -8,2 +8,8 @@ # Changelog
 ## [Unreleased]
+## [v5.2.0] - 2022-11-07
+### Added
+- `.getConnectedVertices(key)` to get connected nodes to a given node.
+- `.getConnecetedEdges(key)`to get connected edges from a given node.
+- `traverseDfs(key, cb, abortCb)` added abortCb optional param to abort traversal.
+- `traverseBfs(key, cb, abortCb)` added abortCb optional param to abort traversal.
 
@@ -10,0 +16,0 @@ ## [v5.1.5] - 2022-08-15

package.json

 {
   "name": "@datastructures-js/graph",
-  "version": "5.1.5",
+  "version": "5.2.0",
   "description": "graph & directed graph implementation in javascript",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -23,2 +23,4 @@ # @datastructures-js/graph
   * [getWeight](#getweight)
+  * [getConnectedVertices](#getconnectedvertices)
+  * [getConnectedEdges](#getconnectededges)
   * [removeVertex](#removevertex)
@@ -162,2 +164,18 @@ * [removeEdge](#removeedge)
 
+### getConnectedVertices
+Returns a list of keys of vertices connected to a given vertex.
+
+```js
+console.log(directedGraph.getConnectedVertices('v4')); // ['v3', 'v5']
+console.log(graph.getConnectedVertices('v1')); // ['v2', 'v3']
+```
+
+### getConnectedEdges
+Returns an object of keys of vertices connected to a given vertex with the edges weight.
+
+```js
+console.log(directedGraph.getConnectedEdges('v4')); // { v3: 1, v5: 4 }
+console.log(graph.getConnectedEdges('v1')); // { v2: 2, v3: 6 }
+```
+
 ### removeVertex
@@ -210,3 +228,3 @@ Removes a vertex with all its edges from the graph.
 ### traverseDfs
-Traverses the graph from a starting vertex using the depth-first recursive search.
+Traverses the graph from a starting vertex using the depth-first recursive search. it also accepts an optional third param as a callback to abort traversal when it returns true.
 
@@ -229,6 +247,16 @@ ```js
 */
+
+let counter = 0;
+graph.traverseDfs('v1', (key, value) => {
+  console.log(`${key}: ${value}`);
+  counter += 1;
+}, () => counter > 1);
+/*
+v1: true
+v2: true
+*/
 ```
 
 ### traverseBfs
-Traverses the graph from a starting vertex using the breadth-first search with a queue.
+Traverses the graph from a starting vertex using the breadth-first search with a queue. it also accepts an optional third param as a callback to abort traversal when it returns true.
 
@@ -251,2 +279,12 @@ ```js
 */
+
+let counter = 0;
+graph.traverseBfs('v1', (key, value) => {
+  console.log(`${key}: ${value}`);
+  counter += 1;
+}, () => counter > 1);
+/*
+v1: true
+v2: true
+*/
 ```
@@ -253,0 +291,0 @@

src/directedGraph.d.ts

@@ -6,2 +6,3 @@ export class DirectedGraph<T extends number|string, U = undefined> {
   getVerticesCount(): number;
+  getConnectedVertices(key: T): T[];
   addEdge(srcKey: T, destKey: T, weight?: number): DirectedGraph<T, U>;
@@ -13,5 +14,6 @@ hasEdge(srcKey: T, destKey: T): boolean;
   getEdgesCount(): number;
-  traverseDfs(srcKey: T, cb: (key: T, value: U) => void): void;
-  traverseBfs(srcKey: T, cb: (key: T, value: U) => void): void;
+  getConnectedEdges(key: T): { [key: T]: number };
+  traverseDfs(srcKey: T, cb: (key: T, value: U) => void, abortCb?: () => boolean): void;
+  traverseBfs(srcKey: T, cb: (key: T, value: U) => void, abortCb?: () => boolean): void;
   clear(): void;
 }

src/directedGraph.js

@@ -69,2 +69,30 @@ /**
   /**
+   * Returns the vertices connected to a given vertex
+   * @public
+   * @return {array}
+   */
+  getConnectedVertices(key) {
+    if (!this._edges.has(key)) return [];
+
+    const result = [];
+    this._edges.get(key).forEach((w, k) => result.push(k));
+    return result;
+  }
+
+  /**
+   * Returns the edges connected to a given vertex
+   * @public
+   * @return {object}
+   */
+  getConnectedEdges(key) {
+    if (!this._edges.has(key)) return {};
+
+    const result = {};
+    this._edges.get(key).forEach((w, k) => {
+      result[k] = w;
+    });
+    return result;
+  }
+
+  /**
    * Adds a directed edge from a source vertex to a destination
@@ -182,6 +210,9 @@ * @public
    * @param {function} cb
+   * @param {function} abortCb
    */
-  traverseDfs(srcKey, cb) {
+  traverseDfs(srcKey, cb, abortCb) {
     const traverseDfsRecursive = (key, visited = new Set()) => {
-      if (!this.hasVertex(key) || visited.has(key)) return;
+      if (!this.hasVertex(key) || visited.has(key) || (abortCb && abortCb())) {
+        return;
+      }
 
@@ -203,4 +234,5 @@ cb(key, this._vertices.get(key));
    * @param {function} cb
+   * @param {function} abortCb
    */
-  traverseBfs(srcKey, cb) {
+  traverseBfs(srcKey, cb, abortCb) {
     if (!this.hasVertex(srcKey)) return;
@@ -211,3 +243,3 @@
 
-    while (!queue.isEmpty()) {
+    while (!queue.isEmpty() && (!abortCb || !abortCb())) {
       const nextKey = queue.dequeue();
@@ -214,0 +246,0 @@ cb(nextKey, this._vertices.get(nextKey));

New alerts

License Policy Violation

License

This 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

License

This 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

20349

increased by12.71%

Lines of code

326

increased by10.14%

Number of lines in readme file

307

increased by14.13%

No dependency changes