undirected-graph-typed - npm Package Compare versions

Comparing version 1.48.3 to 1.48.4

dist/data-structures/graph/abstract-graph.d.ts

@@ -91,2 +91,3 @@ import type { DijkstraResult, VertexKey } from '../../types';
     addVertex(key: VertexKey, value?: V): boolean;
+    isVertexKey(potentialKey: any): potentialKey is VertexKey;
     /**
@@ -93,0 +94,0 @@ * Time Complexity: O(1) - Constant time for Map operations.

dist/data-structures/graph/abstract-graph.js

@@ -103,2 +103,6 @@ "use strict";
     }
+    isVertexKey(potentialKey) {
+        const potentialKeyType = typeof potentialKey;
+        return potentialKeyType === "string" || potentialKeyType === "number";
+    }
     /**
@@ -105,0 +109,0 @@ * Time Complexity: O(1) - Constant time for Map operations.

dist/data-structures/graph/directed-graph.d.ts

@@ -99,16 +99,34 @@ import { AbstractEdge, AbstractGraph, AbstractVertex } from './abstract-graph';
     /**
-     * Time Complexity: O(|E|) where |E| is the number of edges
+     * Time Complexity: O(E) where E is the number of edges
      * Space Complexity: O(1)
      */
     /**
-     * Time Complexity: O(|E|) where |E| is the number of edges
+     * Time Complexity: O(E) where E is the number of edges
      * Space Complexity: O(1)
      *
-     * The function removes an edge from a graph and returns the removed edge, or undefined if the edge was not found.
-     * @param {EO} edge - The `edge` parameter is an object that represents an edge in a graph. It has two properties: `src`
-     * and `dest`, which represent the source and destination vertices of the edge, respectively.
-     * @returns The method `deleteEdge` returns the removed edge (`EO`) if it exists, or `undefined` if the edge does not exist.
+     * The `deleteEdge` function removes an edge from a graph and returns the removed edge.
+     * @param {EO | VertexKey} edgeOrSrcVertexKey - The `edge` parameter can be either an `EO` object (edge object) or
+     * a `VertexKey` (key of a vertex).
+     * @param {VertexKey} [destVertexKey] - The `destVertexKey` parameter is an optional parameter that
+     * represents the key of the destination vertex of the edge. It is used to specify the destination
+     * vertex when the `edge` parameter is a vertex key. If `destVertexKey` is not provided, the function
+     * assumes that the `edge`
+     * @returns the removed edge (EO) or undefined if no edge was removed.
      */
-    deleteEdge(edge: EO): EO | undefined;
+    deleteEdge(edgeOrSrcVertexKey: EO | VertexKey, destVertexKey?: VertexKey): EO | undefined;
     /**
+     * Time Complexity: O(1) - Constant time for Map operations.
+     * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+     */
+    /**
+     * Time Complexity: O(1) - Constant time for Map operations.
+     * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+     *
+     * The `deleteVertex` function removes a vertex from a graph by its ID or by the vertex object itself.
+     * @param {VO | VertexKey} vertexOrKey - The parameter `vertexOrKey` can be either a vertex object (`VO`) or a vertex ID
+     * (`VertexKey`).
+     * @returns The method is returning a boolean value.
+     */
+    deleteVertex(vertexOrKey: VO | VertexKey): boolean;
+    /**
      * Time Complexity: O(|E|) where |E| is the number of edges
@@ -115,0 +133,0 @@ * Space Complexity: O(1)

dist/data-structures/graph/directed-graph.js

@@ -153,26 +153,42 @@ "use strict";
     /**
-     * Time Complexity: O(|E|) where |E| is the number of edges
+     * Time Complexity: O(E) where E is the number of edges
      * Space Complexity: O(1)
      */
     /**
-     * Time Complexity: O(|E|) where |E| is the number of edges
+     * Time Complexity: O(E) where E is the number of edges
      * Space Complexity: O(1)
      *
-     * The function removes an edge from a graph and returns the removed edge, or undefined if the edge was not found.
-     * @param {EO} edge - The `edge` parameter is an object that represents an edge in a graph. It has two properties: `src`
-     * and `dest`, which represent the source and destination vertices of the edge, respectively.
-     * @returns The method `deleteEdge` returns the removed edge (`EO`) if it exists, or `undefined` if the edge does not exist.
+     * The `deleteEdge` function removes an edge from a graph and returns the removed edge.
+     * @param {EO | VertexKey} edgeOrSrcVertexKey - The `edge` parameter can be either an `EO` object (edge object) or
+     * a `VertexKey` (key of a vertex).
+     * @param {VertexKey} [destVertexKey] - The `destVertexKey` parameter is an optional parameter that
+     * represents the key of the destination vertex of the edge. It is used to specify the destination
+     * vertex when the `edge` parameter is a vertex key. If `destVertexKey` is not provided, the function
+     * assumes that the `edge`
+     * @returns the removed edge (EO) or undefined if no edge was removed.
      */
-    deleteEdge(edge) {
+    deleteEdge(edgeOrSrcVertexKey, destVertexKey) {
         let removed = undefined;
-        const src = this._getVertex(edge.src);
-        const dest = this._getVertex(edge.dest);
+        let src, dest;
+        if (this.isVertexKey(edgeOrSrcVertexKey)) {
+            if (this.isVertexKey(destVertexKey)) {
+                src = this._getVertex(edgeOrSrcVertexKey);
+                dest = this._getVertex(destVertexKey);
+            }
+            else {
+                return;
+            }
+        }
+        else {
+            src = this._getVertex(edgeOrSrcVertexKey.src);
+            dest = this._getVertex(edgeOrSrcVertexKey.dest);
+        }
         if (src && dest) {
             const srcOutEdges = this._outEdgeMap.get(src);
             if (srcOutEdges && srcOutEdges.length > 0) {
-                (0, utils_1.arrayRemove)(srcOutEdges, (edge) => edge.src === src.key);
+                (0, utils_1.arrayRemove)(srcOutEdges, (edge) => edge.src === src.key && edge.dest === (dest === null || dest === void 0 ? void 0 : dest.key));
             }
             const destInEdges = this._inEdgeMap.get(dest);
             if (destInEdges && destInEdges.length > 0) {
-                removed = (0, utils_1.arrayRemove)(destInEdges, (edge) => edge.dest === dest.key)[0];
+                removed = (0, utils_1.arrayRemove)(destInEdges, (edge) => edge.src === src.key && edge.dest === dest.key)[0];
             }
@@ -183,2 +199,32 @@ }
     /**
+     * Time Complexity: O(1) - Constant time for Map operations.
+     * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+     */
+    /**
+     * Time Complexity: O(1) - Constant time for Map operations.
+     * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+     *
+     * The `deleteVertex` function removes a vertex from a graph by its ID or by the vertex object itself.
+     * @param {VO | VertexKey} vertexOrKey - The parameter `vertexOrKey` can be either a vertex object (`VO`) or a vertex ID
+     * (`VertexKey`).
+     * @returns The method is returning a boolean value.
+     */
+    deleteVertex(vertexOrKey) {
+        let vertexKey;
+        let vertex;
+        if (this.isVertexKey(vertexOrKey)) {
+            vertex = this.getVertex(vertexOrKey);
+            vertexKey = vertexOrKey;
+        }
+        else {
+            vertex = vertexOrKey;
+            vertexKey = this._getVertexKey(vertexOrKey);
+        }
+        if (vertex) {
+            this._outEdgeMap.delete(vertex);
+            this._inEdgeMap.delete(vertex);
+        }
+        return this._vertices.delete(vertexKey);
+    }
+    /**
      * Time Complexity: O(|E|) where |E| is the number of edges
@@ -185,0 +231,0 @@ * Space Complexity: O(1)

dist/data-structures/graph/undirected-graph.d.ts

@@ -88,15 +88,34 @@ import { AbstractEdge, AbstractGraph, AbstractVertex } from './abstract-graph';
     /**
-     * Time Complexity: O(|E|), where |E| is the number of edges incident to the given vertex.
+     * Time Complexity: O(E), where E is the number of edges incident to the given vertex.
      * Space Complexity: O(1)
      */
     /**
-     * Time Complexity: O(|E|), where |E| is the number of edges incident to the given vertex.
+     * Time Complexity: O(E), where E is the number of edges incident to the given vertex.
      * Space Complexity: O(1)
      *
-     * The deleteEdge function removes an edge between two vertices in a graph.
-     * @param {EO} edge - The parameter "edge" is of type EO, which represents an edge in a graph.
-     * @returns The method is returning either the removed edge (of type EO) or undefined if the edge was not found.
+     * The function `deleteEdge` deletes an edge between two vertices in a graph.
+     * @param {EO | VertexKey} edgeOrOneSideVertexKey - The parameter `edgeOrOneSideVertexKey` can be
+     * either an edge object or a vertex key.
+     * @param {VertexKey} [otherSideVertexKey] - The parameter `otherSideVertexKey` is an optional
+     * parameter that represents the key of the vertex on the other side of the edge. It is used when the
+     * `edgeOrOneSideVertexKey` parameter is a vertex key, and it specifies the key of the vertex on the
+     * other side of the
+     * @returns The `deleteEdge` function returns either the deleted edge object (EO) or `undefined`.
      */
-    deleteEdge(edge: EO): EO | undefined;
+    deleteEdge(edgeOrOneSideVertexKey: EO | VertexKey, otherSideVertexKey?: VertexKey): EO | undefined;
     /**
+     * Time Complexity: O(1) - Constant time for Map operations.
+     * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+     */
+    /**
+     * Time Complexity: O(1) - Constant time for Map operations.
+     * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+     *
+     * The `deleteVertex` function removes a vertex from a graph by its ID or by the vertex object itself.
+     * @param {VO | VertexKey} vertexOrKey - The parameter `vertexOrKey` can be either a vertex object (`VO`) or a vertex ID
+     * (`VertexKey`).
+     * @returns The method is returning a boolean value.
+     */
+    deleteVertex(vertexOrKey: VO | VertexKey): boolean;
+    /**
      * Time Complexity: O(1)
@@ -103,0 +122,0 @@ * Space Complexity: O(1)

dist/data-structures/graph/undirected-graph.js

@@ -138,17 +138,80 @@ "use strict";
     /**
-     * Time Complexity: O(|E|), where |E| is the number of edges incident to the given vertex.
+     * Time Complexity: O(E), where E is the number of edges incident to the given vertex.
      * Space Complexity: O(1)
      */
     /**
-     * Time Complexity: O(|E|), where |E| is the number of edges incident to the given vertex.
+     * Time Complexity: O(E), where E is the number of edges incident to the given vertex.
      * Space Complexity: O(1)
      *
-     * The deleteEdge function removes an edge between two vertices in a graph.
-     * @param {EO} edge - The parameter "edge" is of type EO, which represents an edge in a graph.
-     * @returns The method is returning either the removed edge (of type EO) or undefined if the edge was not found.
+     * The function `deleteEdge` deletes an edge between two vertices in a graph.
+     * @param {EO | VertexKey} edgeOrOneSideVertexKey - The parameter `edgeOrOneSideVertexKey` can be
+     * either an edge object or a vertex key.
+     * @param {VertexKey} [otherSideVertexKey] - The parameter `otherSideVertexKey` is an optional
+     * parameter that represents the key of the vertex on the other side of the edge. It is used when the
+     * `edgeOrOneSideVertexKey` parameter is a vertex key, and it specifies the key of the vertex on the
+     * other side of the
+     * @returns The `deleteEdge` function returns either the deleted edge object (EO) or `undefined`.
      */
-    deleteEdge(edge) {
-        return this.deleteEdgeBetween(edge.vertices[0], edge.vertices[1]);
+    deleteEdge(edgeOrOneSideVertexKey, otherSideVertexKey) {
+        let oneSide, otherSide;
+        if (this.isVertexKey(edgeOrOneSideVertexKey)) {
+            if (this.isVertexKey(otherSideVertexKey)) {
+                oneSide = this._getVertex(edgeOrOneSideVertexKey);
+                otherSide = this._getVertex(otherSideVertexKey);
+            }
+            else {
+                return;
+            }
+        }
+        else {
+            oneSide = this._getVertex(edgeOrOneSideVertexKey.vertices[0]);
+            otherSide = this._getVertex(edgeOrOneSideVertexKey.vertices[1]);
+        }
+        if (oneSide && otherSide) {
+            return this.deleteEdgeBetween(oneSide, otherSide);
+        }
+        else {
+            return;
+        }
     }
     /**
+     * Time Complexity: O(1) - Constant time for Map operations.
+     * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+     */
+    /**
+     * Time Complexity: O(1) - Constant time for Map operations.
+     * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+     *
+     * The `deleteVertex` function removes a vertex from a graph by its ID or by the vertex object itself.
+     * @param {VO | VertexKey} vertexOrKey - The parameter `vertexOrKey` can be either a vertex object (`VO`) or a vertex ID
+     * (`VertexKey`).
+     * @returns The method is returning a boolean value.
+     */
+    deleteVertex(vertexOrKey) {
+        let vertexKey;
+        let vertex;
+        if (this.isVertexKey(vertexOrKey)) {
+            vertex = this.getVertex(vertexOrKey);
+            vertexKey = vertexOrKey;
+        }
+        else {
+            vertex = vertexOrKey;
+            vertexKey = this._getVertexKey(vertexOrKey);
+        }
+        const neighbors = this.getNeighbors(vertexOrKey);
+        if (vertex) {
+            neighbors.forEach(neighbor => {
+                const neighborEdges = this._edges.get(neighbor);
+                if (neighborEdges) {
+                    const restEdges = neighborEdges.filter(edge => {
+                        return !edge.vertices.includes(vertexKey);
+                    });
+                    this._edges.set(neighbor, restEdges);
+                }
+            });
+            this._edges.delete(vertex);
+        }
+        return this._vertices.delete(vertexKey);
+    }
+    /**
      * Time Complexity: O(1)
@@ -155,0 +218,0 @@ * Space Complexity: O(1)

package.json

 {
   "name": "undirected-graph-typed",
-  "version": "1.48.3",
+  "version": "1.48.4",
   "description": "Undirected Graph. Javascript & Typescript Data Structure.",
@@ -148,4 +148,4 @@ "main": "dist/index.js",
   "dependencies": {
-    "data-structure-typed": "^1.48.3"
+    "data-structure-typed": "^1.48.4"
   }
 }

src/data-structures/graph/abstract-graph.ts

@@ -167,2 +167,7 @@ /**
 
+  isVertexKey(potentialKey: any): potentialKey is VertexKey {
+    const potentialKeyType = typeof potentialKey;
+    return potentialKeyType === "string" || potentialKeyType === "number"
+  }
+
   /**
@@ -169,0 +174,0 @@ * Time Complexity: O(1) - Constant time for Map operations.

src/data-structures/graph/directed-graph.ts

@@ -181,23 +181,39 @@ /**
   /**
-   * Time Complexity: O(|E|) where |E| is the number of edges
+   * Time Complexity: O(E) where E is the number of edges
    * Space Complexity: O(1)
    */
 
+
   /**
-   * Time Complexity: O(|E|) where |E| is the number of edges
+   * Time Complexity: O(E) where E is the number of edges
    * Space Complexity: O(1)
    *
-   * The function removes an edge from a graph and returns the removed edge, or undefined if the edge was not found.
-   * @param {EO} edge - The `edge` parameter is an object that represents an edge in a graph. It has two properties: `src`
-   * and `dest`, which represent the source and destination vertices of the edge, respectively.
-   * @returns The method `deleteEdge` returns the removed edge (`EO`) if it exists, or `undefined` if the edge does not exist.
+   * The `deleteEdge` function removes an edge from a graph and returns the removed edge.
+   * @param {EO | VertexKey} edgeOrSrcVertexKey - The `edge` parameter can be either an `EO` object (edge object) or
+   * a `VertexKey` (key of a vertex).
+   * @param {VertexKey} [destVertexKey] - The `destVertexKey` parameter is an optional parameter that
+   * represents the key of the destination vertex of the edge. It is used to specify the destination
+   * vertex when the `edge` parameter is a vertex key. If `destVertexKey` is not provided, the function
+   * assumes that the `edge`
+   * @returns the removed edge (EO) or undefined if no edge was removed.
    */
-  deleteEdge(edge: EO): EO | undefined {
+  deleteEdge(edgeOrSrcVertexKey: EO | VertexKey, destVertexKey?: VertexKey): EO | undefined {
     let removed: EO | undefined = undefined;
-    const src = this._getVertex(edge.src);
-    const dest = this._getVertex(edge.dest);
+    let src: VO | undefined, dest: VO | undefined;
+    if (this.isVertexKey(edgeOrSrcVertexKey)) {
+      if (this.isVertexKey(destVertexKey)) {
+        src = this._getVertex(edgeOrSrcVertexKey);
+        dest = this._getVertex(destVertexKey);
+      } else {
+        return;
+      }
+    } else {
+      src = this._getVertex(edgeOrSrcVertexKey.src);
+      dest = this._getVertex(edgeOrSrcVertexKey.dest);
+    }
+
     if (src && dest) {
       const srcOutEdges = this._outEdgeMap.get(src);
       if (srcOutEdges && srcOutEdges.length > 0) {
-        arrayRemove(srcOutEdges, (edge: EO) => edge.src === src.key);
+        arrayRemove(srcOutEdges, (edge: EO) => edge.src === src!.key && edge.dest === dest?.key);
       }
@@ -207,3 +223,3 @@
       if (destInEdges && destInEdges.length > 0) {
-        removed = arrayRemove(destInEdges, (edge: EO) => edge.dest === dest.key)[0];
+        removed = arrayRemove(destInEdges, (edge: EO) => edge.src === src!.key && edge.dest === dest!.key)[0];
       }
@@ -216,2 +232,35 @@ }
   /**
+   * Time Complexity: O(1) - Constant time for Map operations.
+   * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+   */
+
+  /**
+   * Time Complexity: O(1) - Constant time for Map operations.
+   * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+   *
+   * The `deleteVertex` function removes a vertex from a graph by its ID or by the vertex object itself.
+   * @param {VO | VertexKey} vertexOrKey - The parameter `vertexOrKey` can be either a vertex object (`VO`) or a vertex ID
+   * (`VertexKey`).
+   * @returns The method is returning a boolean value.
+   */
+  override deleteVertex(vertexOrKey: VO | VertexKey): boolean {
+    let vertexKey: VertexKey;
+    let vertex: VO | undefined;
+    if (this.isVertexKey(vertexOrKey)) {
+      vertex = this.getVertex(vertexOrKey);
+      vertexKey = vertexOrKey;
+    } else {
+      vertex = vertexOrKey;
+      vertexKey = this._getVertexKey(vertexOrKey)
+    }
+
+    if (vertex) {
+      this._outEdgeMap.delete(vertex)
+      this._inEdgeMap.delete(vertex)
+    }
+
+    return this._vertices.delete(vertexKey);
+  }
+
+  /**
    * Time Complexity: O(|E|) where |E| is the number of edges
@@ -218,0 +267,0 @@ * Space Complexity: O(1)

src/data-structures/graph/undirected-graph.ts

@@ -161,19 +161,87 @@ /**
   /**
-   * Time Complexity: O(|E|), where |E| is the number of edges incident to the given vertex.
+   * Time Complexity: O(E), where E is the number of edges incident to the given vertex.
    * Space Complexity: O(1)
    */
 
+
   /**
-   * Time Complexity: O(|E|), where |E| is the number of edges incident to the given vertex.
+   * Time Complexity: O(E), where E is the number of edges incident to the given vertex.
    * Space Complexity: O(1)
    *
-   * The deleteEdge function removes an edge between two vertices in a graph.
-   * @param {EO} edge - The parameter "edge" is of type EO, which represents an edge in a graph.
-   * @returns The method is returning either the removed edge (of type EO) or undefined if the edge was not found.
+   * The function `deleteEdge` deletes an edge between two vertices in a graph.
+   * @param {EO | VertexKey} edgeOrOneSideVertexKey - The parameter `edgeOrOneSideVertexKey` can be
+   * either an edge object or a vertex key.
+   * @param {VertexKey} [otherSideVertexKey] - The parameter `otherSideVertexKey` is an optional
+   * parameter that represents the key of the vertex on the other side of the edge. It is used when the
+   * `edgeOrOneSideVertexKey` parameter is a vertex key, and it specifies the key of the vertex on the
+   * other side of the
+   * @returns The `deleteEdge` function returns either the deleted edge object (EO) or `undefined`.
    */
-  deleteEdge(edge: EO): EO | undefined {
-    return this.deleteEdgeBetween(edge.vertices[0], edge.vertices[1]);
+  deleteEdge(edgeOrOneSideVertexKey: EO | VertexKey, otherSideVertexKey?: VertexKey): EO | undefined {
+    let oneSide: VO | undefined, otherSide: VO | undefined;
+    if (this.isVertexKey(edgeOrOneSideVertexKey)) {
+      if (this.isVertexKey(otherSideVertexKey)) {
+        oneSide = this._getVertex(edgeOrOneSideVertexKey);
+        otherSide = this._getVertex(otherSideVertexKey);
+      } else {
+        return;
+      }
+    } else {
+      oneSide = this._getVertex(edgeOrOneSideVertexKey.vertices[0]);
+      otherSide = this._getVertex(edgeOrOneSideVertexKey.vertices[1]);
+    }
+
+    if (oneSide && otherSide) {
+      return this.deleteEdgeBetween(oneSide, otherSide);
+
+    } else {
+      return;
+    }
   }
 
   /**
+   * Time Complexity: O(1) - Constant time for Map operations.
+   * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+   */
+
+  /**
+   * Time Complexity: O(1) - Constant time for Map operations.
+   * Space Complexity: O(1) - Constant space, as it creates only a few variables.
+   *
+   * The `deleteVertex` function removes a vertex from a graph by its ID or by the vertex object itself.
+   * @param {VO | VertexKey} vertexOrKey - The parameter `vertexOrKey` can be either a vertex object (`VO`) or a vertex ID
+   * (`VertexKey`).
+   * @returns The method is returning a boolean value.
+   */
+  override deleteVertex(vertexOrKey: VO | VertexKey): boolean {
+    let vertexKey: VertexKey;
+    let vertex: VO | undefined;
+    if (this.isVertexKey(vertexOrKey)) {
+      vertex = this.getVertex(vertexOrKey);
+      vertexKey = vertexOrKey;
+    } else {
+      vertex = vertexOrKey;
+      vertexKey = this._getVertexKey(vertexOrKey)
+    }
+
+    const neighbors = this.getNeighbors(vertexOrKey)
+
+    if (vertex) {
+      neighbors.forEach(neighbor => {
+        const neighborEdges = this._edges.get(neighbor);
+        if (neighborEdges) {
+          const restEdges = neighborEdges.filter(edge => {
+            return !edge.vertices.includes(vertexKey);
+          });
+          this._edges.set(neighbor, restEdges);
+        }
+      })
+      this._edges.delete(vertex);
+
+    }
+
+    return this._vertices.delete(vertexKey);
+  }
+
+  /**
    * Time Complexity: O(1)
@@ -180,0 +248,0 @@ * Space Complexity: O(1)

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

1922953

increased by0.58%

Lines of code

36519

increased by0.71%

Dependency changes

• Updateddata-structure-typed@^1.48.4