Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
structurae
Advanced tools
structurae - npm Package Compare versions
Comparing version 0.0.24 to 0.0.25
@@ -244,8 +244,13 @@ // Type definitions for structurae | ||
| export declare class UnweightedGraph extends BinaryGrid { | ||
| interface UnweightedMatrixOptions { | ||
| size: number; | ||
| directed?: boolean; | ||
| } | ||
| export declare class UnweightedAdjacencyMatrix extends BinaryGrid { | ||
| size: number; | ||
| colors: BinaryGrid; | ||
| directed: boolean; | ||
| constructor(options?: GridOptions, ...args: any); | ||
| constructor(options?: UnweightedMatrixOptions, ...args: any); | ||
| addEdge(x: number, y: number): this; | ||
@@ -268,8 +273,46 @@ removeEdge(x: number, y: number): this; | ||
| declare class WeightedGraph { | ||
| interface UnweightedListOptions { | ||
| vertices: number; | ||
| edges: number; | ||
| directed?: boolean; | ||
| } | ||
| export declare class UnweightedAdjacencyList extends Uint32Array { | ||
| vertices: number; | ||
| edges: number; | ||
| colors: BinaryGrid; | ||
| directed: boolean; | ||
| constructor(options?: UnweightedListOptions, ...args: any); | ||
| addEdge(x: number, y: number): this; | ||
| removeEdge(x: number, y: number): this; | ||
| hasEdge(x: number, y: number): boolean; | ||
| private setEdge(x: number, y: number): this; | ||
| private unsetEdge(x: number, y: number): this; | ||
| outEdges(x: number): number[]; | ||
| inEdges(x: number): number[]; | ||
| private setOffsets(): void; | ||
| isGray(x: number): boolean; | ||
| setGray(x: number): this; | ||
| isBlack(x: number): boolean; | ||
| setBlack(x: number): this; | ||
| traverse(isDFS?: boolean, start?: number, gray?: boolean, white?: boolean, black?: boolean): number; | ||
| path(start: number, end?: number): number[]; | ||
| tree(start?: number): number[]; | ||
| isAcyclic(): boolean; | ||
| topologicalSort(): number[]; | ||
| static getLength(vertices: number, edges: number): number; | ||
| } | ||
| interface WeightedMatrixOptions { | ||
| size: number; | ||
| pad?: any; | ||
| } | ||
| declare class WeightedAdjacencyMatrix { | ||
| size: number; | ||
| colors: BinaryGrid; | ||
| directed: boolean; | ||
| constructor(options?: GridOptions, ...args: any); | ||
| constructor(options?: WeightedMatrixOptions, ...args: any); | ||
| addEdge(x: number, y: number): this; | ||
@@ -295,2 +338,2 @@ removeEdge(x: number, y: number): this; | ||
| export declare function WeightedGraphMixin<T extends Collection>(Base: Constructor<T>, directed?: boolean): Constructor<T & WeightedGraph> | ||
| export declare function WeightedAdjacencyMatrixMixin<T extends Collection>(Base: Constructor<T>, directed?: boolean): Constructor<T & WeightedAdjacencyMatrix> |
10
index.js
@@ -10,4 +10,5 @@ const BitField = require('./lib/bit-field'); | ||
| const SymmetricGridMixin = require('./lib/symmetric-grid'); | ||
| const UnweightedGraph = require('./lib/unweighted-graph'); | ||
| const WeightedGraphMixin = require('./lib/weighted-graph'); | ||
| const UnweightedAdjacencyList = require('./lib/unweighted-adjacency-list'); | ||
| const UnweightedAdjacencyMatrix = require('./lib/unweighted-adjacency-matrix'); | ||
| const WeightedAdjacencyMatrixMixin = require('./lib/weighted-adjacency-matrix'); | ||
@@ -39,4 +40,5 @@ /** | ||
| SymmetricGridMixin, | ||
| UnweightedGraph, | ||
| WeightedGraphMixin, | ||
| UnweightedAdjacencyList, | ||
| UnweightedAdjacencyMatrix, | ||
| WeightedAdjacencyMatrixMixin, | ||
| }; |
| { | ||
| "name": "structurae", | ||
| "version": "0.0.24", | ||
| "version": "0.0.25", | ||
| "description": "Data structures for performance-sensitive modern JavaScript applications.", | ||
@@ -5,0 +5,0 @@ "main": "index.js", |
@@ -11,4 +11,4 @@ # Structurae | ||
| - [Graphs](https://github.com/zandaqo/structurae#Graphs): | ||
| - [UnweightedGraph](https://github.com/zandaqo/structurae#UnweightedGraph) - implements Adjacency Matrix using [BinaryGrid](https://github.com/zandaqo/structurae#BinaryGrid) to handle unweighted graphs. | ||
| - [WeightedGraph](https://github.com/zandaqo/structurae#WeightedGraph) - implements Adjacency Matrix using [Grid](https://github.com/zandaqo/structurae#Grid) or [SymmetricGrid](https://github.com/zandaqo/structurae#SymmetricGrid) to handle weighted graphs. | ||
| - [UnweightedAdjacencyMatrix](https://github.com/zandaqo/structurae#UnweightedAdjacencyMatrix) - implements Adjacency Matrix using [BinaryGrid](https://github.com/zandaqo/structurae#BinaryGrid) to handle unweighted graphs. | ||
| - [WeightedAdjacencyMatrix](https://github.com/zandaqo/structurae#WeightedAdjacencyMatrix) - implements Adjacency Matrix using [Grid](https://github.com/zandaqo/structurae#Grid) or [SymmetricGrid](https://github.com/zandaqo/structurae#SymmetricGrid) to handle weighted graphs. | ||
| - [Grids](https://github.com/zandaqo/structurae#Grids): | ||
@@ -201,3 +201,3 @@ - [BinaryGrid](https://github.com/zandaqo/structurae#BinaryGrid) - creates a grid or 2D matrix of bits. | ||
| ### Graphs | ||
| UnweightedGraph and WeightedGraph classes implement Adjacency Matrix data structure to handle unweighted and weighted graphs respectively, | ||
| UnweightedAdjacencyMatrix and WeightedAdjacencyMatrix classes implement Adjacency Matrix data structure to handle unweighted and weighted graphs respectively, | ||
| both directed and undirected. Graph classes extend Grids which in turn rely on TypedArrays, thus, allowing us to store a whole graph in a single ArrayBuffer. | ||
@@ -207,10 +207,10 @@ The classes provide methods to operate on edges (`addEdge`, `removeEdge`, `hasEdge`, `inEdges`, `outEdges`) as well as to traverse the graphs using BFS or DFS (`traverse`) | ||
| #### UnweightedGraph | ||
| UnweightedGraph extends [BinaryGrid](https://github.com/zandaqo/structurae#BinaryGrid) to represent | ||
| #### UnweightedAdjacencyMatrix | ||
| UnweightedAdjacencyMatrix extends [BinaryGrid](https://github.com/zandaqo/structurae#BinaryGrid) to represent | ||
| an unweighted graph in the densest possible way: each edge of a graph is represented as a single bit in an underlying ArrayBuffer. | ||
| For example, to represent a graph with 80 nodes as an Adjacency Matrix we need 80 * 80 bits or 800 bytes. UnweightedGraph will | ||
| For example, to represent a graph with 80 nodes as an Adjacency Matrix we need 80 * 80 bits or 800 bytes. UnweightedAdjacencyMatrix will | ||
| will create an ArrayBuffer of that size, "view" it as Uint16Array (of length 400) and operate on edges using bitwise operations. | ||
| ```javascript | ||
| graph = new UnweightedGraph({ size: 6, directed: true }); | ||
| graph = new UnweightedAdjacencyMatrix({ size: 6, directed: true }); | ||
| graph.addEdge(0, 1) | ||
@@ -242,11 +242,11 @@ .addEdge(0, 2) | ||
| #### WeightedGraph | ||
| WeightedGraph extends [Grid](https://github.com/zandaqo/structurae#Grid) (for directed graphs) | ||
| #### WeightedAdjacencyMatrix | ||
| WeightedAdjacencyMatrix extends [Grid](https://github.com/zandaqo/structurae#Grid) (for directed graphs) | ||
| or [SymmetricGrid](https://github.com/zandaqo/structurae#SymmetricGrid) (for undirected) to handle weighted graphs. | ||
| As UnweightedGraph it stores all edges in a single ArrayBuffer and offers the same API: | ||
| As UnweightedAdjacencyMatrix it stores all edges in a single ArrayBuffer and offers the same API: | ||
| ```javascript | ||
| const WeightedGraph = WeightedGraphMixin(Int32Array, true); | ||
| const WeightedAdjacencyMatrix = WeightedAdjacencyMatrixMixin(Int32Array, true); | ||
| // creates a class for directed graphs that use Int32Array for edge weights | ||
| graph = new WeightedGraph({ size: 6, pad: -1 }); | ||
| graph = new WeightedAdjacencyMatrix({ size: 6, pad: -1 }); | ||
| graph.addEdge(0, 1, 3) | ||
@@ -274,3 +274,3 @@ .addEdge(0, 2, 2) | ||
| For path finding WeightedGraph uses DFS based search for acyclic graphs, Dijkstra for graph with no negative edges, and | ||
| For path finding WeightedAdjacencyMatrix uses DFS based search for acyclic graphs, Dijkstra for graph with no negative edges, and | ||
| Bellman-Ford for all other cases. You can choose the algorithm for a particular search by supplying extra arguments to the `path` method: | ||
@@ -277,0 +277,0 @@ |
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
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
Improved metrics
- Total package byte prevSize
- increased by7.66%
136264
- Number of package files
- increased by5.88%
18
- Lines of code
- increased by9.96%
3831
No dependency changes