structurae - npm Package Compare versions

Comparing version 0.0.25 to 0.0.26

index.d.ts

@@ -270,2 +270,3 @@ // Type definitions for structurae
     static getLength(size: number): number;
+    static fromList(list: UnweightedAdjacencyList): UnweightedAdjacencyMatrix;
 }
@@ -294,2 +295,4 @@
     private setOffsets(): void;
+    isFull(): boolean;
+    grow(vertices?: number, edges?: number): UnweightedAdjacencyList;
     isGray(x: number): boolean;
@@ -305,2 +308,3 @@ setGray(x: number): this;
     static getLength(vertices: number, edges: number): number;
+    static fromGrid(grid: Grid): UnweightedAdjacencyList;
 }
@@ -307,0 +311,0 @@

lib/unweighted-adjacency-list.js

 const BinaryGrid = require('./binary-grid');
 
+/**
+ * Implements Adjacency List data structure for unweighted graphs.
+ *
+ * @extends Uint32Array
+ */
 class UnweightedAdjacencyList extends Uint32Array {
+  /**
+   * @param {Object} [options]
+   * @param {number} [options.vertices=2] the maximum amount of vertices in the graph
+   * @param {number} [options.edges=2] the maximum amount of edges in the graph
+   * @param {boolean} [options.directed=true] whether the graph is directed
+   * @param {...*} args
+   */
   constructor(options = {}, ...args) {
@@ -30,2 +42,5 @@ const { vertices = 2, edges = 2, directed = true } = options;
   addEdge(x, y) {
+    if (this.hasEdge(x, y)) return this;
+    // the list is full
+    if (this.isFull()) return this;
     this.setEdge(x, y);
@@ -105,2 +120,3 @@ if (!this.directed) this.setEdge(y, x);
         edgeIndex = i;
+        break;
       }
@@ -173,2 +189,39 @@ }
   /**
+   * Checks whether the list is full--all available edges are set.
+   *
+   * @returns {boolean}
+   */
+  isFull() {
+    return this[this.vertices] >= this.length;
+  }
+
+  /**
+   * Creates a larger copy of the graph with a space
+   * for a specified amount of additional vertices and edges.
+   *
+   * @param {number} [vertices=0] the amount of additional vertices
+   * @param {number} [edges=1] the amount of additional edges
+   * @returns {UnweightedAdjacencyList}
+   */
+  grow(vertices = 0, edges = 1) {
+    const copy = new this.constructor({
+      vertices: this.vertices + vertices,
+      edges: this.edges + edges,
+    });
+
+    if (!vertices) {
+      copy.set(this);
+    } else {
+      const offset = this[this.vertices];
+      const newSize = this.vertices + vertices;
+      const newOffset = offset + vertices;
+      for (let i = 0; i <= newSize; i++) {
+        copy[i] = i < this.vertices ? this[i] + vertices : newOffset;
+      }
+      copy.set(this.subarray(this.vertices + 1), newSize + 1);
+    }
+    return copy;
+  }
+
+  /**
    * Checks if a vertex is entered during a traversal.
@@ -336,4 +389,38 @@ *
   }
+
+  /**
+   * @type {CollectionConstructor}
+   */
+  static get [Symbol.species]() {
+    return Uint32Array;
+  }
+
+  /**
+   * Creates an adjacency list from a given grid or adjacency matrix.
+   *
+   * @param {Grid} grid
+   * @returns {UnweightedAdjacencyList}
+   */
+  static fromGrid(grid) {
+    const vertices = grid.rows;
+    const offset = vertices + 1;
+    const empty = grid.pad || 0;
+    const array = new Array(offset).fill(offset);
+    let edges = 0;
+    for (let i = 0; i < vertices; i++) {
+      array[i + 1] = i === 0 ? offset : array[i];
+      for (let j = 0; j < vertices; j++) {
+        if (grid.get(i, j) !== empty) {
+          array.push(j);
+          array[i + 1] += 1;
+          edges++;
+        }
+      }
+    }
+    const graph = new this({ vertices, edges });
+    graph.set(array);
+    return graph;
+  }
 }
 
 module.exports = UnweightedAdjacencyList;

lib/unweighted-adjacency-matrix.js

@@ -260,4 +260,24 @@ const BinaryGrid = require('./binary-grid');
   }
+
+  /**
+   * Creates an adjacency matrix from a given adjacency list.
+   *
+   * @param {UnweightedAdjacencyList} list
+   * @returns {UnweightedAdjacencyMatrix}
+   */
+  static fromList(list) {
+    const { vertices, directed } = list;
+    const graph = new this({ size: vertices, directed });
+    for (let i = 0; i < vertices; i++) {
+      const offset = list[i];
+      const nextOffset = list[i + 1];
+      if (offset === nextOffset) continue;
+      for (let j = nextOffset - 1; j >= offset; j--) {
+        graph.addEdge(i, list[j]);
+      }
+    }
+    return graph;
+  }
 }
 
 module.exports = UnweightedAdjacencyMatrix;

package.json

 {
   "name": "structurae",
-  "version": "0.0.25",
+  "version": "0.0.26",
   "description": "Data structures for performance-sensitive modern JavaScript applications.",
@@ -16,3 +16,5 @@ "main": "index.js",
     "matrix",
-    "heap"
+    "heap",
+    "list",
+    "adjacency"
   ],
@@ -19,0 +21,0 @@ "scripts": {

No alert changes

Improved metrics

Total package byte prevSize

139471

2.35%

Lines of code

3936

2.74%

No dependency changes