ts-structures - npm Package Compare versions

Comparing version 0.5.4 to 0.5.5

graph/index.d.ts

@@ -0,26 +1,79 @@
+import type { Vertex, Edge } from './list-graph';
 import { ListGraph } from './list-graph';
-interface Graph<T extends number | string> {
-    get(vertex: Vertex<T>): EdgeSet | undefined;
-    getEdge(vertexA: Vertex<T>, vertexB: Vertex<T>): Edge | undefined;
-    addVertex(vertex: string): boolean;
-    removeVertex(vertex: string): boolean;
-    addEdge(vertexA: string, vertexB: string, weight: number): boolean;
-    removeEdge(vertexA: string, vertexB: string): boolean;
-    addDirectedEdge(from: string, to: string, weight: number): boolean;
-    removeDirectedEdge(from: string, to: string): boolean;
+interface Graph<T> {
+    /**
+     * Retrieves the vertex corresponding to given id.
+     *
+     * @param id - The vertex id.
+     * @returns - The matching `Vertex` or `undefined` if not found.
+     */
+    get(id: string): Vertex<T> | undefined;
+    /**
+     * Retrieves an edge connecting two vertices. The parameters order
+     * only matter in the case of a directed graph.
+     *
+     * @param id - The queried vertex id.
+     * @returns The matched `Vertex` or `undefined` if not found
+     */
+    getEdge(from: string, to: string): Edge | undefined;
+    /**
+     * Adds a new vertex, referenced with a **unique** id, holding given data.
+     * If the given id is already used, the insertion is aborted.
+     *
+     * @param id - The vertex ID.  **Must be unique**
+     * @param data - Additionnal data.
+     * @returns `true` or `false` if it failed to insert.
+     */
+    addVertex(id: string, data?: any): boolean;
+    /**
+     * Removes vertex qith given id and its related edges.
+     *
+     * @param id - id of the vertex to be removed.
+     * @returns `true` or `false` if the vertex is not found.
+     */
+    removeVertex(id: string): boolean;
+    /**
+     * Adds an edge between two vertices with an optional weight. The order of
+     * `from` and `to` parameters only matters if the graph is directed.
+     * It fails if a vertex is not found or when trying to add an already
+     * existing edge.
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @param weight - The edge weight.
+     * @returns `true` or `false` if insertion failed.
+     */
+    addEdge(from: string, to: string, weight: number): boolean;
+    /**
+     * Removes the edge between two vertices. The order of `from` and `to`
+     * parameters only matters if the graph is directed.
+     * It fails if a vertex is not found or when trying to remove an inexistent
+     * edge.
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @returns `true` or `false` if it failed to remove an edge.
+     */
+    removeEdge(from: string, to: string): boolean;
 }
-declare type Vertex<T extends string | number> = T;
-declare class Edge {
-    vertex: Vertex<string>;
-    weight: number;
-    constructor(vertex: Vertex<string>, weight: number);
-    setWeight(weight: number): boolean;
-}
-declare class EdgeSet extends Set<Edge> {
-    hasVertex(vertex: Vertex<string>): boolean;
-    getEdge(vertex: Vertex<string>): Edge | undefined;
-    deleteVertex(vertex: Vertex<string>): boolean;
-    private actionOnMatch;
-}
-export type { Vertex, };
-export { Graph, ListGraph, Edge, EdgeSet, };
+/**
+ * The possible options for a Graph.
+ */
+declare type GraphOptions = {
+    /**
+     * Whether edges should be added in both direction.
+     */
+    directed?: boolean;
+    /**
+     * Whether the edges should be assigner a weight value.
+     * Note: unused for now. A weight can be added no matter
+     * this value, and if not a default value is used.
+     */
+    weighted?: boolean;
+    /**
+     * The default weight value to add to the edges.
+     */
+    defaultWeight?: number;
+};
+export type { Vertex, GraphOptions, };
+export { Graph, ListGraph, };

graph/index.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
-exports.EdgeSet = exports.Edge = exports.ListGraph = void 0;
+exports.ListGraph = void 0;
 const list_graph_1 = require("./list-graph");
 Object.defineProperty(exports, "ListGraph", { enumerable: true, get: function () { return list_graph_1.ListGraph; } });
-class Edge {
-    constructor(vertex, weight) {
-        this.vertex = vertex;
-        this.weight = weight;
-    }
-    setWeight(weight) {
-        this.weight = weight;
-        return true;
-    }
-}
-exports.Edge = Edge;
-// Todo: change set to map?
-class EdgeSet extends Set {
-    hasVertex(vertex) {
-        var _a;
-        return (_a = this.actionOnMatch(vertex, () => true)) !== null && _a !== void 0 ? _a : false;
-    }
-    getEdge(vertex) {
-        return this.actionOnMatch(vertex, (edge) => edge);
-    }
-    deleteVertex(vertex) {
-        var _a;
-        return (_a = this.actionOnMatch(vertex, (edge) => this.delete(edge))) !== null && _a !== void 0 ? _a : false;
-    }
-    actionOnMatch(vertex, action) {
-        for (const edge of this)
-            if (edge.vertex === vertex)
-                return action(edge);
-        return undefined;
-    }
-}
-exports.EdgeSet = EdgeSet;

graph/list-graph.d.ts

@@ -1,18 +0,264 @@
-import type { Vertex } from '.';
-import { Graph, EdgeSet, Edge } from '.';
-declare class ListGraph implements Graph<string> {
-    data: Map<string, EdgeSet>;
+import type { ReduceFunction, TraverseCallback } from '../_shared/types';
+import type { Graph, GraphOptions } from '.';
+/**
+ * Represents a single weight connection from one vertex to another.
+ */
+declare class Edge {
+    /**
+     * The origin vertex.
+     */
+    from: string;
+    /**
+     * The destination vertex.
+     */
+    to: string;
+    /**
+     * The weight value.
+     */
+    weight: number;
+    /**
+     * Creates a new edge connecting two vertices with given weight.
+     *
+     * @param from - The origin vertex.
+     * @param to - The destination vertex.
+     * @param weight - The weight of the edge.
+     */
+    constructor(from: string, to: string, weight: number);
+    /**
+     * Sets the edge weight to the current value.
+     *
+     * @param weight - The new weight value.
+     */
+    setWeight(weight: number): void;
+}
+/**
+ * Represents a node in a graph. It consists of a unique id, an associated data
+ * and a collection of edges connecting it to other vertices.
+ */
+declare class Vertex<T> {
+    /**
+     * Unique identifier in a graph scope. It should never be modified.
+     */
+    id: string;
+    /**
+     * Data carried by the vertex.
+     */
+    data: T;
+    /**
+     * A collection of edges stored in a Map for quick access
+     * a insert/remove operations.
+     */
+    private _edges;
+    /**
+     * Returns a new `Vertex`with a **unique id** and associated data.
+     *
+     * @param id - Unique id in graph scope.
+     * @param data - The carried data.
+     */
+    constructor(id: string, data: T);
+    /**
+     * Prevents from altering the vertex once create.
+     * Might change strategy later?
+     */
+    private lock;
     get size(): number;
-    get(vertex: Vertex<string>): EdgeSet | undefined;
-    getEdge(from: Vertex<string>, to: Vertex<string>): Edge | undefined;
-    addVertex(vertex: Vertex<string>): boolean;
-    removeVertex(vertex: Vertex<string>): boolean;
-    resetVertex(vertex: Vertex<string>): boolean;
-    addEdge(vertexA: Vertex<string>, vertexB: Vertex<string>, weight?: number): boolean;
-    removeEdge(vertexA: Vertex<string>, vertexB: Vertex<string>): boolean;
-    addDirectedEdge(from: Vertex<string>, to: Vertex<string>, weight?: number): boolean;
-    removeDirectedEdge(from: Vertex<string>, to: Vertex<string>): boolean;
-    getEdgeWeight(from: Vertex<string>, to: Vertex<string>): number | undefined;
-    setEdgeWeight(from: Vertex<string>, to: Vertex<string>, weight: number): boolean;
+    /**
+     * Returns an array of the vertex edges.
+     */
+    edges(): Edge[];
+    /**
+     * Adds a new edge to the collection.
+     *
+     * @param edge - The edge to add.
+     */
+    addEdge(edge: Edge): boolean;
+    hasEdge(to: string): boolean;
+    getEdge(to: string): Edge | undefined;
+    removeEdge(to: string): boolean;
+    forEachEdge(callback: (edge: Edge, to: string) => void): void;
 }
+/**
+ * A Graph implementation based on an Adjacency list.
+ * In its current implementation, it is weighted (with a default value
+ * of `1`, allowing to not care about it if it is not needed), and
+ * can be optionnaly directed if specified in the constructor options.
+ */
+declare class ListGraph<T> implements Graph<T> {
+    /**
+     * The data source containing all vertices and edges, using
+     * a Map as adjacency list.
+     */
+    private data;
+    /**
+     * Whether edges should be added in both direction.
+     *
+     * @defaultValue `false`
+     */
+    private isDirected;
+    /**
+     * Whether the edges should be assigner a weight value.
+     * Note: unused for now. A weight can be added no matter
+     * this value, and if not a default value is used.
+     *
+     * @defaultValue `false`
+     */
+    private isWeighted;
+    /**
+     * The default weight value to add to the edges.
+     *
+     * @defaultValue `1`
+     */
+    private defaultWeight;
+    constructor(options?: GraphOptions | undefined);
+    /**
+     * The number of vertices.
+     */
+    get order(): number;
+    /**
+     * The number of edges.
+     */
+    get size(): number;
+    /**
+     * Sets the default weight on edge insertion to the given value.
+     *
+     * @param weight - The replacing weight value .
+     */
+    setDefaultWeight(weight: number): void;
+    /**
+     * Retrieves the vertex corresponding to given id.
+     *
+     * @param id - The vertex id.
+     * @returns - The matching `Vertex` or `undefined` if not found.
+     */
+    get(id: string): Vertex<T> | undefined;
+    /**
+     * Retrieves an edge connecting two vertices. The parameters order
+     * only matter in the case of a directed graph.
+     *
+     * @param from - The origin vertex id.
+     * @param to - The destination vertex id.
+     * @returns - The matching `Edge` or `undefined` if not found.
+     */
+    getEdge(from: string, to: string): Edge | undefined;
+    /**
+     * Returns an array of all vertices.
+     *
+     * @returns An array of `Vertex`.
+     */
+    vertices(): Vertex<T>[];
+    /**
+     * Returns an array of all edges.
+     *
+     * @returns An array of `Edge`.
+     */
+    edges(): Edge[];
+    /**
+     * Adds a new vertex, referenced with a **unique** id, holding given data.
+     * If the given id is already used, the insertion is aborted.
+     *
+     * @param id - The vertex ID.  **Must be unique**
+     * @param data - Additionnal data.
+     * @returns `true` or `false` if it failed to insert.
+     */
+    addVertex(id: string, data: T): boolean;
+    /**
+     * Removes vertex qith given id and its related edges.
+     *
+     * @param id - id of the vertex to be removed.
+     * @returns `true` or `false` if the vertex is not found.
+     */
+    removeVertex(id: string): boolean;
+    /**
+     * Removes all related edges to a vertex. The associated data persists.
+     *
+     * @param id - id if the vertex to be removed.
+     * @returns `true` or `false` if the vertex is not found.
+     */
+    resetVertex(id: string): boolean;
+    /**
+     * Adds an edge between two vertices with an optional weight. The order of
+     * `from` and `to` parameters only matters if the graph is directed.
+     * It fails if a vertex is not found or when trying to add an already
+     * existing edge.
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @param weight - The edge weight.
+     * @returns `true` or `false` if insertion failed.
+     */
+    addEdge(from: string, to: string, weight?: number): boolean;
+    /**
+     * Removes the edge between two vertices. The order of `from` and `to`
+     * parameters only matters if the graph is directed.
+     * It fails if a vertex is not found or when trying to remove an inexistent
+     * edge.
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @returns `true` or `false` if it failed to remove an edge.
+     */
+    removeEdge(from: string, to: string): boolean;
+    /**
+     * Retrieves the edge between two vertices and sets its weight.
+     * The order of `from` and `to` parameters only matters if the graph
+     * is directed.
+     * It fails if no edge is found (missing vertex or vertices not
+     * connected).
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @returns `true` or `false` if it failed to retrieve the edge.
+     */
+    setEdgeWeight(from: string, to: string, weight: number): boolean;
+    /**
+     * Retrieves the edge between two vertices and returns its weight.
+     * The order of `from` and `to` parameters only matters if the graph
+     * is directed.
+     * It fails if no edge is found (missing vertex or vertices not
+     * connected).
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @returns The weight value of the edge  or `undefined` if it failed
+     * to retrieve the edge.
+     */
+    getEdgeWeight(from: string, to: string): number | undefined;
+    /**
+     * Internal helper providing recurrent checks on a specific edge
+     * before performing an operation.
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @returns \{
+     *
+     * `srcVertex`: (*Vertex*) Vertex match for `from`
+     *
+     * `dstVertex`: (*Vertex*) Vertex match for `to`
+     *
+     * `isSafeAdd`: (*boolean*)
+     *
+     * `isSafeRem`: (*boolean*)
+     *
+     * \}
+     */
+    private checkEdgeOps;
+    /**
+     * Executes a callback on each vertex.
+     *
+     * @param callback - The callback to execute on each vertex.
+     */
+    walk(callback: (vertex: Vertex<T>, id: string) => void): void;
+    /**
+     * Reduces all vertices to a single value using the ginven `reduce`
+     * function.
+     *
+     * @param reduce - The `ReduceFunction` to apply on each vertex.
+     * @param initialValue - The starting value.
+     * @returns The value resulting of the result function.
+     */
+    reduce<R>(reduce: ReduceFunction<Vertex<T>, R>, initialValue: R): R;
+    traverseDFSRecursive(rootId: string, callback: TraverseCallback<Vertex<T>>): void;
+    traverseBFS(rootId: string, callback: TraverseCallback<Vertex<T>>): void;
+}
+export type { Vertex, Edge, };
 export { ListGraph };

graph/list-graph.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
 exports.ListGraph = void 0;
-const _1 = require(".");
+const queue_1 = require("../queue");
+// import { Stack } from '../stack'
+/**
+ * Represents a single weight connection from one vertex to another.
+ */
+class Edge {
+    /**
+     * Creates a new edge connecting two vertices with given weight.
+     *
+     * @param from - The origin vertex.
+     * @param to - The destination vertex.
+     * @param weight - The weight of the edge.
+     */
+    constructor(from, to, weight) {
+        this.from = from;
+        this.to = to;
+        this.weight = weight;
+    }
+    /**
+     * Sets the edge weight to the current value.
+     *
+     * @param weight - The new weight value.
+     */
+    setWeight(weight) {
+        this.weight = weight;
+    }
+}
+// TODO:
+// - method to retrieve an array of relations at level N
+// - method to retrieve an array of direct neighbours (level 1)
+/**
+ * Represents a node in a graph. It consists of a unique id, an associated data
+ * and a collection of edges connecting it to other vertices.
+ */
+class Vertex {
+    /**
+     * Returns a new `Vertex`with a **unique id** and associated data.
+     *
+     * @param id - Unique id in graph scope.
+     * @param data - The carried data.
+     */
+    constructor(id, data) {
+        this.id = id;
+        this.data = data;
+        this._edges = new Map();
+        this.lock();
+    }
+    /**
+     * Prevents from altering the vertex once create.
+     * Might change strategy later?
+     */
+    lock() {
+        Object.freeze(this);
+    }
+    get size() {
+        return this._edges.size;
+    }
+    /**
+     * Returns an array of the vertex edges.
+     */
+    edges() {
+        return [...this._edges.values()];
+    }
+    /**
+     * Adds a new edge to the collection.
+     *
+     * @param edge - The edge to add.
+     */
+    addEdge(edge) {
+        if (this._edges.has(edge.to))
+            return false;
+        this._edges.set(edge.to, edge);
+        return true;
+    }
+    // public setEdgeWeight(to: string, weight: number): boolean {
+    //     if (!this._edges.has(to)) return false
+    //     this._edges.get(to)?.setWeight(weight)
+    //     return true
+    // }
+    hasEdge(to) {
+        return this._edges.has(to);
+    }
+    getEdge(to) {
+        return this._edges.get(to);
+    }
+    removeEdge(to) {
+        return this._edges.delete(to);
+    }
+    forEachEdge(callback) {
+        this._edges.forEach((edge, to) => callback(edge, to));
+    }
+}
+/**
+ * A Graph implementation based on an Adjacency list.
+ * In its current implementation, it is weighted (with a default value
+ * of `1`, allowing to not care about it if it is not needed), and
+ * can be optionnaly directed if specified in the constructor options.
+ */
 class ListGraph {
-    constructor() {
+    constructor(options) {
+        var _a, _b, _c;
+        /**
+         * The data source containing all vertices and edges, using
+         * a Map as adjacency list.
+         */
         this.data = new Map();
-        // public traverseDFSRecursive(
-        //     start: Vertex<string>,
-        //     callback: TraverseCallback<Vertex<string>>,
-        // ) {
-        //     const visited = new Set<Vertex<string>>()
-        //     const recurse = (current: Vertex<string>) => {
-        //         if (!current) return
-        //         callback(current)
-        //         visited.add(current)
-        //         this.get(current)!.forEach((edge: Edge) => {
-        //             if (!visited.has(edge.vertex)) return recurse(edge.vertex)
-        //         })
-        //     }
-        //     recurse(start)
-        // }
+        /**
+         * Whether edges should be added in both direction.
+         *
+         * @defaultValue `false`
+         */
+        this.isDirected = false;
+        /**
+         * Whether the edges should be assigner a weight value.
+         * Note: unused for now. A weight can be added no matter
+         * this value, and if not a default value is used.
+         *
+         * @defaultValue `false`
+         */
+        this.isWeighted = false;
+        /**
+         * The default weight value to add to the edges.
+         *
+         * @defaultValue `1`
+         */
+        this.defaultWeight = 1;
+        if (options) {
+            this.isDirected = (_a = options.directed) !== null && _a !== void 0 ? _a : this.isDirected;
+            this.isWeighted = (_b = options.weighted) !== null && _b !== void 0 ? _b : this.isWeighted;
+            this.defaultWeight = (_c = options.defaultWeight) !== null && _c !== void 0 ? _c : this.defaultWeight;
+        }
     }
-    get size() {
+    /**
+     * The number of vertices.
+     */
+    get order() {
         return this.data.size;
     }
-    get(vertex) {
-        return this.data.get(vertex);
+    /**
+     * The number of edges.
+     */
+    get size() {
+        const total = this.reduce((sum, vtx) => sum + vtx.size, 0);
+        return this.isDirected ? total : total / 2;
     }
+    /**
+     * Sets the default weight on edge insertion to the given value.
+     *
+     * @param weight - The replacing weight value .
+     */
+    setDefaultWeight(weight) {
+        this.defaultWeight = weight;
+    }
+    /**
+     * Retrieves the vertex corresponding to given id.
+     *
+     * @param id - The vertex id.
+     * @returns - The matching `Vertex` or `undefined` if not found.
+     */
+    get(id) {
+        return this.data.get(id);
+    }
+    /**
+     * Retrieves an edge connecting two vertices. The parameters order
+     * only matter in the case of a directed graph.
+     *
+     * @param from - The origin vertex id.
+     * @param to - The destination vertex id.
+     * @returns - The matching `Edge` or `undefined` if not found.
+     */
     getEdge(from, to) {
@@ -34,54 +178,255 @@ var _a;
     }
-    addVertex(vertex) {
-        if (this.data.has(vertex))
+    /**
+     * Returns an array of all vertices.
+     *
+     * @returns An array of `Vertex`.
+     */
+    vertices() {
+        return this.reduce((arr, vertex) => {
+            arr.push(vertex);
+            return arr;
+        }, []);
+    }
+    // TODO?: in case of undirected graph, return only once each edge?
+    /**
+     * Returns an array of all edges.
+     *
+     * @returns An array of `Edge`.
+     */
+    edges() {
+        return this.reduce((arr, vertex) => {
+            arr.push(...vertex.edges());
+            return arr;
+        }, []);
+    }
+    /**
+     * Adds a new vertex, referenced with a **unique** id, holding given data.
+     * If the given id is already used, the insertion is aborted.
+     *
+     * @param id - The vertex ID.  **Must be unique**
+     * @param data - Additionnal data.
+     * @returns `true` or `false` if it failed to insert.
+     */
+    addVertex(id, data) {
+        if (this.data.has(id))
             return false;
-        this.data.set(vertex, new _1.EdgeSet());
+        this.data.set(id, new Vertex(id, data));
         return true;
     }
-    removeVertex(vertex) {
-        const vertexIsDeleted = this.data.delete(vertex);
-        if (!vertexIsDeleted)
+    /**
+     * Removes vertex qith given id and its related edges.
+     *
+     * @param id - id of the vertex to be removed.
+     * @returns `true` or `false` if the vertex is not found.
+     */
+    removeVertex(id) {
+        if (!this.data.delete(id))
             return false;
-        this.data.forEach((edgeSet) => edgeSet.deleteVertex(vertex));
+        this.data.forEach((vertex) => vertex.removeEdge(id));
         return true;
     }
-    resetVertex(vertex) {
-        return this.removeVertex(vertex) && this.addVertex(vertex);
+    /**
+     * Removes all related edges to a vertex. The associated data persists.
+     *
+     * @param id - id if the vertex to be removed.
+     * @returns `true` or `false` if the vertex is not found.
+     */
+    resetVertex(id) {
+        const vertex = this.get(id);
+        if (!vertex)
+            return false;
+        return this.removeVertex(id) && this.addVertex(vertex.id, vertex.data);
     }
-    // TODO: reconsider behaviour when one of the two directions already exists.
-    // Let's not forget the weight: should it be replaced in such case?
-    // Maybe just block any addition as soon as a connection exists.
-    addEdge(vertexA, vertexB, weight = 1) {
-        const edgeAddedA = this.addDirectedEdge(vertexA, vertexB, weight);
-        const edgeAddedB = this.addDirectedEdge(vertexB, vertexA, weight);
-        return edgeAddedA || edgeAddedB;
+    /**
+     * Adds an edge between two vertices with an optional weight. The order of
+     * `from` and `to` parameters only matters if the graph is directed.
+     * It fails if a vertex is not found or when trying to add an already
+     * existing edge.
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @param weight - The edge weight.
+     * @returns `true` or `false` if insertion failed.
+     */
+    addEdge(from, to, weight = this.defaultWeight) {
+        const { srcVertex, dstVertex, isSafeAdd, } = this.checkEdgeOps(from, to);
+        if (!isSafeAdd)
+            return false;
+        const srcAdded = srcVertex === null || srcVertex === void 0 ? void 0 : srcVertex.addEdge(new Edge(from, to, weight));
+        return this.isDirected
+            ? !!srcAdded
+            : !!srcAdded && !!(dstVertex === null || dstVertex === void 0 ? void 0 : dstVertex.addEdge(new Edge(to, from, weight)));
+        // return !!srcAdded && (this.isDirected
+        //     ? true
+        //     : !!dstVertex?.addEdge(new Edge(to, from, weight)))
     }
-    removeEdge(vertexA, vertexB) {
-        const edgeRemovedA = this.removeDirectedEdge(vertexA, vertexB);
-        const edgeRemovedB = this.removeDirectedEdge(vertexB, vertexA);
-        return edgeRemovedA || edgeRemovedB;
-    }
-    addDirectedEdge(from, to, weight = 1) {
-        const srcEdges = this.data.get(from);
-        const dstEdges = this.data.get(to);
-        if (!srcEdges || !dstEdges || srcEdges.hasVertex(to))
+    /**
+     * Removes the edge between two vertices. The order of `from` and `to`
+     * parameters only matters if the graph is directed.
+     * It fails if a vertex is not found or when trying to remove an inexistent
+     * edge.
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @returns `true` or `false` if it failed to remove an edge.
+     */
+    removeEdge(from, to) {
+        const { srcVertex, dstVertex, isSafeRem, } = this.checkEdgeOps(from, to);
+        if (!isSafeRem)
             return false;
-        return !!srcEdges.add(new _1.Edge(to, weight));
+        const srcRemoved = srcVertex === null || srcVertex === void 0 ? void 0 : srcVertex.removeEdge(to);
+        if (this.isDirected)
+            return !!srcRemoved;
+        const dstRemoved = dstVertex === null || dstVertex === void 0 ? void 0 : dstVertex.removeEdge(from);
+        return !!srcRemoved && !!dstRemoved;
     }
-    removeDirectedEdge(from, to) {
-        const srcEdges = this.data.get(from);
-        const dstEdges = this.data.get(to);
-        if (!srcEdges || !dstEdges || !srcEdges.hasVertex(to))
+    /**
+     * Retrieves the edge between two vertices and sets its weight.
+     * The order of `from` and `to` parameters only matters if the graph
+     * is directed.
+     * It fails if no edge is found (missing vertex or vertices not
+     * connected).
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @returns `true` or `false` if it failed to retrieve the edge.
+     */
+    setEdgeWeight(from, to, weight) {
+        const srcEdge = this.getEdge(from, to);
+        const dstEdge = this.getEdge(to, from);
+        if (!srcEdge || (!this.isDirected && !dstEdge))
             return false;
-        return srcEdges.deleteVertex(to);
+        srcEdge.setWeight(weight);
+        if (!this.isDirected)
+            dstEdge.setWeight(weight);
+        return true;
     }
+    /**
+     * Retrieves the edge between two vertices and returns its weight.
+     * The order of `from` and `to` parameters only matters if the graph
+     * is directed.
+     * It fails if no edge is found (missing vertex or vertices not
+     * connected).
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @returns The weight value of the edge  or `undefined` if it failed
+     * to retrieve the edge.
+     */
     getEdgeWeight(from, to) {
-        var _a, _b;
-        return (_b = (_a = this.data.get(from)) === null || _a === void 0 ? void 0 : _a.getEdge(to)) === null || _b === void 0 ? void 0 : _b.weight;
+        const edge = this.getEdge(from, to);
+        if (!edge)
+            return undefined;
+        return edge.weight;
     }
-    setEdgeWeight(from, to, weight) {
-        var _a, _b;
-        return !!((_b = (_a = this.data.get(from)) === null || _a === void 0 ? void 0 : _a.getEdge(to)) === null || _b === void 0 ? void 0 : _b.setWeight(weight));
+    /**
+     * Internal helper providing recurrent checks on a specific edge
+     * before performing an operation.
+     *
+     * @param from - The origin vertex of the edge.
+     * @param to - The destination vertex of the edge.
+     * @returns \{
+     *
+     * `srcVertex`: (*Vertex*) Vertex match for `from`
+     *
+     * `dstVertex`: (*Vertex*) Vertex match for `to`
+     *
+     * `isSafeAdd`: (*boolean*)
+     *
+     * `isSafeRem`: (*boolean*)
+     *
+     * \}
+     */
+    checkEdgeOps(from, to) {
+        const srcVertex = this.get(from);
+        const dstVertex = this.get(to);
+        const verticesExist = !!srcVertex && !!dstVertex;
+        const isSafeAdd = verticesExist
+            && !srcVertex.hasEdge(to)
+            && (!this.isDirected ? !dstVertex.hasEdge(from) : true);
+        const isSafeRem = verticesExist
+            && srcVertex.hasEdge(to)
+            && (!this.isDirected ? dstVertex.hasEdge(from) : true);
+        return { srcVertex, dstVertex, isSafeAdd, isSafeRem };
     }
+    /**
+     * Executes a callback on each vertex.
+     *
+     * @param callback - The callback to execute on each vertex.
+     */
+    walk(callback) {
+        this.data.forEach((vertex, id) => callback(vertex, id));
+    }
+    /**
+     * Reduces all vertices to a single value using the ginven `reduce`
+     * function.
+     *
+     * @param reduce - The `ReduceFunction` to apply on each vertex.
+     * @param initialValue - The starting value.
+     * @returns The value resulting of the result function.
+     */
+    reduce(reduce, initialValue) {
+        let accumulator = initialValue;
+        this.walk((vertex) => { accumulator = reduce(accumulator, vertex); });
+        return accumulator;
+    }
+    // CHECKPOINT REFACTO
+    traverseDFSRecursive(rootId, callback) {
+        const visited = new Set();
+        const recurse = (currentId) => {
+            const currentVertex = this.get(currentId);
+            if (!currentVertex)
+                return;
+            callback(currentVertex);
+            visited.add(currentVertex.id);
+            currentVertex.forEachEdge(({ to }) => {
+                if (!visited.has(to))
+                    recurse(to);
+            });
+        };
+        recurse(rootId);
+    }
+    // public traverseDFSIterative(
+    //     rootId: string,
+    //     callback: TraverseCallback<Vertex<T>>,
+    // ) {
+    //     const rootVertex = this.get(rootId)
+    //     if (!rootVertex) return
+    //     const stack = new Stack<string>()
+    //     const visited = new Set<string>()
+    //     stack.push(rootId)
+    //     visited.add(rootId)
+    //     let currentId: string | undefined = rootId
+    //     while (currentId = stack.pop()) { // eslint-disable-line no-cond-assign
+    //         const currentVertex = this.get(currentId)!
+    //         currentVertex.forEachEdge(({ to }) => {
+    //             if (!visited.has(to)) {
+    //                 stack.push(to)
+    //                 visited.add(to)
+    //             }
+    //         })
+    //         callback(currentVertex)
+    //     }
+    // }
+    traverseBFS(rootId, callback) {
+        const rootVertex = this.get(rootId);
+        if (!rootVertex)
+            return;
+        const queue = new queue_1.Queue();
+        const visited = new Set();
+        queue.enqueue(rootId);
+        visited.add(rootId);
+        let currentId = rootId;
+        while (currentId = queue.dequeue()) { // eslint-disable-line no-cond-assign
+            const currentVertex = this.get(currentId);
+            currentVertex.forEachEdge(({ to }) => {
+                if (!visited.has(to)) {
+                    queue.enqueue(to);
+                    visited.add(to);
+                }
+            });
+            callback(currentVertex);
+        }
+    }
 }
 exports.ListGraph = ListGraph;

package.json

 {
   "name": "ts-structures",
-  "version": "0.5.4",
+  "version": "0.5.5",
   "description": "TypeScript implementation of common data structures",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -51,3 +51,3 @@ # TypeScript Datastructures
 - [Graph](https://gregoryalbouy-ts-datastructures.netlify.app/interfaces/_graph_index_.graph.html)
-    - [List Graph](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_graph_list_graph_.listgraph.html) (Adjacency list based graph, optionnally directed or weighted): still needs massive refacto & documentation
+    - [List Graph](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_graph_list_graph_.listgraph.html) (Adjacency list based graph, optionnally directed or weighted)
     - Matrix Graph (Adjacency matrix based graph): *in progress*
@@ -58,5 +58,4 @@
 - Graph implementation
-    - Refacto
-    - Documentation
+    - Refacto *in progress*
     - MatrixGraph
 - More data structures

stack/stack.d.ts

@@ -23,3 +23,3 @@ import { CappedStructure } from '../_shared';
     capacity: number;
-    front?: StackNode<T>;
+    private _front?;
     /**
@@ -33,2 +33,6 @@ * Constructor takes an optional `capacity` parameter. If set,
     /**
+     * Returns the stack's top element without popping it.
+     */
+    pike(): StackNode<T> | undefined;
+    /**
      * Adds an element to the front of the stack and returns its length.
@@ -35,0 +39,0 @@ * If the length already reached the (optional) capacity, push is not

stack/stack.js

@@ -47,2 +47,8 @@ "use strict";
     /**
+     * Returns the stack's top element without popping it.
+     */
+    pike() {
+        return this._front;
+    }
+    /**
      * Adds an element to the front of the stack and returns its length.
@@ -57,4 +63,4 @@ * If the length already reached the (optional) capacity, push is not
     push(value) {
-        const node = new StackNode(value, this.front);
-        this.front = node;
+        const node = new StackNode(value, this._front);
+        this._front = node;
         return ++this.length;
@@ -69,6 +75,6 @@ }
     pop() {
-        if (!this.front)
+        if (!this._front)
             return undefined;
-        const value = this.front.value;
-        this.front = this.front.next;
+        const value = this._front.value;
+        this._front = this._front.next;
         this.length--;
@@ -75,0 +81,0 @@ return value;

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

95885

increased by25.34%

Lines of code

2558

increased by32.13%

Worsened metrics

Number of lines in readme file

59

decreased by-1.67%

No dependency changes