Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

@datastructures-js/graph

Package Overview
Dependencies
Maintainers
1
Versions
19
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@datastructures-js/graph - npm Package Compare versions

Comparing version 4.0.1 to 5.0.0

10

CHANGELOG.md

@@ -9,2 +9,12 @@ # Changelog

## [v5.0.0] - 2021-04-15
### Changed
- `addVertex` & `addEdge` now can be chained.
- remove `Vertex` class overhead, simply use key-value.
- getters.
### Fixed
- `.getWeight` now returns `Infinity` for two vertices that are not connected.
- README
## [v4.0.1] - 2020-04-10

@@ -11,0 +21,0 @@ ### Fixed

2

package.json
{
"name": "@datastructures-js/graph",
"version": "4.0.1",
"version": "5.0.0",
"description": "graph & directed graph implementation in javascript",

@@ -5,0 +5,0 @@ "main": "index.js",

597

README.md

@@ -16,9 +16,9 @@ # @datastructures-js/graph

* [import](#import)
* [Creating a Graph](#create-a-graph)
* [new](#new)
* [.addVertex(key, value)](#addvertexkey-value)
* [.hasVertex(key)](#hasvvertex-key)
* [.verticesCount()](#verticescount)
* [.getVerticesCount()](#getverticescount)
* [.addEdge(srcKey, destKey, weight)](#addedgesrckey-destkey-weight)
* [.hasEdge(srcKey, destKey)](#hasedgesrckey-destkey)
* [.edgesCount()](#edgescount)
* [.getEdgesCount()](#getedgescount)
* [.getWeight(srcKey, destKey)](#getweightsrcKey-destKey)

@@ -30,3 +30,2 @@ * [.removeVertex(key)](#removevertexkey)

* [.clear()](#clear)
* [Vertex](#vertex)
* [Build](#build)

@@ -54,7 +53,5 @@ * [License](#license)

### create a graph
creates an empty graph
### new
Creates a new graph
#### Example
```js

@@ -67,70 +64,55 @@ const directedGraph = new DirectedGraph();

### .addVertex(key, value)
adds a vertex to the graph.
Adds a vertex to the graph.
<table>
<tr><th align="center" colspan="2">params</th></tr>
<tr><td><b>name</b></td><td align="center"><b>type</b></td></tr>
<tr><td>key</td><td>number or string</td></tr>
<tr><td>value</td><td>object</td></tr>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
key: number | string
<br />
value: any
</td>
<td align="center">Graph | DirectedGraph</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr><th>return</th></tr>
<tr>
<td><a href="#vertex">Vertex</a></td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js
directedGraph.addVertex('v1', 1);
directedGraph.addVertex('v1', 1);
directedGraph.addVertex('v2', 2);
directedGraph.addVertex('v3', 3);
directedGraph.addVertex('v4', 4);
directedGraph.addVertex('v5', 5);
directedGraph
.addVertex('v1', 1)
.addVertex('v2', 2)
.addVertex('v3', 3)
.addVertex('v4', 4)
.addVertex('v5', 5);
graph.addVertex('v1', true);
graph.addVertex('v2', true);
graph.addVertex('v3', true);
graph.addVertex('v4', true);
graph.addVertex('v5', true);
graph
.addVertex('v1', true)
.addVertex('v2', true)
.addVertex('v3', true)
.addVertex('v4', true)
.addVertex('v5', true);
```
### .hasVertex(key)
checks if the graph has a vertex by its key.
<table>
<tr><th align="center" colspan="2">params</th></tr>
<tr><td><b>name</b></td><td align="center"><b>type</b></td></tr>
<tr><td>key</td><td>number or string</td></tr>
</table>
Checks if the graph has a vertex by its key.
<table>
<tr><th>return</th></tr>
<tr>
<td>boolean</td>
</tr>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
key: number | string
</td>
<td align="center">boolean</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js

@@ -141,96 +123,83 @@ console.log(directedGraph.hasVertex('v7')); // false

### .verticesCount()
gets the number of vertices in the graph.
### .getVerticesCount()
Gets the number of vertices in the graph.
<table>
<tr><th>return</th></tr>
<tr>
<td>number</td>
</tr>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">number</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js
console.log(directedGraph.verticesCount()); // 5
console.log(graph.verticesCount()); // 5
console.log(directedGraph.getVerticesCount()); // 5
console.log(graph.getVerticesCount()); // 5
```
### .addEdge(srcKey, destKey, weight)
adds an edge with a weight between two existings vertices. Default weight is 1 if not defined. The edge is a direction from source to destination when added in a directed graph, and a connecting two-way edge when added in a graph.
Adds a weighted edge between two existings vertices. Default weight is 1 if not defined. The single edge is a direction from source to destination in a directed graph, and a two-way connection in a graph.
<table>
<tr><th align="center" colspan="3">params</th></tr>
<tr><td><b>name</b></td><td align="center"><b>type</b></td><td><b>description</b></td></tr>
<tr><td>srcKey</td><td>number or string</td><td>the source vertex key</td></tr>
<tr><td>destKey</td><td>number or string</td><td>the destination vertex key</td></tr>
<tr><td>weight</td><td>number</td><td>the weight of the edge</td></tr>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
srcKey: number | string
<br />
destKey: number | string
<br />
weight: number
</td>
<td align="center">Graph | DirectedGraph</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js
directedGraph.addEdge('v1', 'v2', 2);
directedGraph.addEdge('v1', 'v3', 3);
directedGraph.addEdge('v1', 'v4', 1);
directedGraph.addEdge('v2', 'v4', 1);
directedGraph.addEdge('v3', 'v5', 2);
directedGraph.addEdge('v4', 'v3', 1);
directedGraph.addEdge('v4', 'v5', 4);
directedGraph
.addEdge('v1', 'v2', 2)
.addEdge('v1', 'v3', 3)
.addEdge('v1', 'v4', 1)
.addEdge('v2', 'v4', 1)
.addEdge('v3', 'v5', 2)
.addEdge('v4', 'v3', 1)
.addEdge('v4', 'v5', 4);
graph.addEdge('v1', 'v2', 2);
graph.addEdge('v2', 'v3', 3);
graph.addEdge('v1', 'v3', 6);
graph.addEdge('v2', 'v4', 1);
graph.addEdge('v4', 'v3', 1);
graph.addEdge('v4', 'v5', 4);
graph.addEdge('v3', 'v5', 2);
graph
.addEdge('v1', 'v2', 2)
.addEdge('v2', 'v3', 3)
.addEdge('v1', 'v3', 6)
.addEdge('v2', 'v4', 1)
.addEdge('v4', 'v3', 1)
.addEdge('v4', 'v5', 4)
.addEdge('v3', 'v5', 2);
```
### .hasEdge(srcKey, destKey)
checks if the graph has an edge between two existing vertices. In directed graph, it returns true only if there is a direction from source to destination.
Checks if the graph has an edge between two existing vertices. In directed graph, it returns true only if there is a direction from source to destination.
<table>
<tr><th align="center" colspan="3">params</th></tr>
<tr><td><b>name</b></td><td align="center"><b>type</b></td><td><b>description</b></td></tr>
<tr><td>srcKey</td><td>number or string</td><td>the source vertex key</td></tr>
<tr><td>destKey</td><td>number or string</td><td>the destination vertex key</td></tr>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
srcKey: number | string
<br />
destKey: number | string
</td>
<td align="center">boolean</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr><th>return</th></tr>
<tr>
<td>boolean</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js

@@ -244,60 +213,44 @@ console.log(directedGraph.hasEdge('v1', 'v2')); // true

### .edgesCount()
gets the number of edges in the graph.
### .getEdgesCount()
Gets the number of edges in the graph.
<table>
<tr><th>return</th></tr>
<tr>
<td>number</td>
</tr>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">number</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js
console.log(directedGraph.edgesCount()); // 7
console.log(graph.edgesCount()); // 7
console.log(directedGraph.getEdgesCount()); // 7
console.log(graph.getEdgesCount()); // 7
```
### .getWeight(srcKey, destKey)
gets the edge's weight between two vertices in the graph. If there is no direct edge between the two vertices, it returns null. It also returns 0 if the source key is equal to destination key.
Gets the edge's weight between two vertices. If there is no direct edge between the two vertices, it returns `Infinity`. It also returns 0 if the source key is equal to destination key.
<table>
<tr><th align="center" colspan="3">params</th></tr>
<tr><td><b>name</b></td><td align="center"><b>type</b></td><td><b>description</b></td></tr>
<tr><td>srcKey</td><td>number or string</td><td>the source vertex key</td></tr>
<tr><td>destKey</td><td>number or string</td><td>the destination vertex key</td></tr>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
srcKey: number | string
<br />
destKey: number | string
</td>
<td align="center">number</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr><th>return</th></tr>
<tr>
<td>number</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js
console.log(directedGraph.getWeight('v1', 'v2')); // 2
console.log(directedGraph.getWeight('v2', 'v1')); // null
console.log(directedGraph.getWeight('v2', 'v1')); // Infinity
console.log(directedGraph.getWeight('v1', 'v1')); // 0

@@ -308,154 +261,141 @@

console.log(graph.getWeight('v1', 'v1')); // 0
console.log(graph.getWeight('v1', 'v4')); // null
console.log(graph.getWeight('v1', 'v4')); // Infinity
```
### .removeVertex(key)
removes a vertex with all its edges from the graph by its key.
Removes a vertex with all its edges from the graph.
<table>
<tr><th align="center" colspan="3">params</th></tr>
<tr><td><b>name</b></td><td align="center"><b>type</b></td><td><b>description</b></td></tr>
<tr><td>key</td><td>number or string</td><td>the vertex key</td></tr>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
key: number | string
</td>
<td align="center">boolean</td>
<td>
Graph: O(K) : K = number of connected edges to the vertex
<br />
DirectedGraph: O(E) : E = number of edges in the graph
</td>
</tr>
</table>
<table>
<tr><th>return</th></tr>
<tr>
<td>boolean</td>
</tr>
</table>
<table>
<tr>
<th colspan="2">runtime</th>
</tr>
<tr><td>Graph</td><td>O(K) : K = number of connected edges to the vertex</td></tr>
<tr><td>Directed Graph</td><td>O(E) : E = number of edges in the graph</td></tr>
</table>
#### Example
```js
directedGraph.removeVertex('v5');
console.log(directedGraph.verticesCount()); // 4
console.log(directedGraph.edgesCount()); // 5
console.log(directedGraph.getVerticesCount()); // 4
console.log(directedGraph.getEdgesCount()); // 5
graph.removeVertex('v5');
console.log(graph.verticesCount()); // 4
console.log(graph.edgesCount()); // 5
console.log(graph.getVerticesCount()); // 4
console.log(graph.getEdgesCount()); // 5
```
### .removeEdge(srcKey, destKey)
removes an edge between two existing vertices
Removes an edge between two existing vertices
<table>
<tr><th align="center" colspan="3">params</th></tr>
<tr><td><b>name</b></td><td align="center"><b>type</b></td><td><b>description</b></td></tr>
<tr><td>srcKey</td><td>number or string</td><td>the source vertex key</td></tr>
<tr><td>destKey</td><td>number or string</td><td>the destination vertex key</td></tr>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
srcKey: number | string
<br />
destKey: number | string
</td>
<td align="center">boolean</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr><th>return</th></tr>
<tr>
<td>boolean</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js
directedGraph.removeEdge('v1', 'v3'); // true
console.log(directedGraph.edgesCount()); // 4
console.log(directedGraph.getEdgesCount()); // 4
graph.removeEdge('v2', 'v3'); // true
console.log(graph.edgesCount()); // 4
console.log(graph.getEdgesCount()); // 4
```
### .removeEdges(key)
removes all connected edges to a vertex by its key.
Removes all connected edges to a vertex and returns the number of removed edges.
<table>
<tr><th align="center" colspan="3">params</th></tr>
<tr><td><b>name</b></td><td align="center"><b>type</b></td><td><b>description</b></td></tr>
<tr><td>key</td><td>number or string</td><td>the vertex key</td></tr>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
key: number | string
</td>
<td align="center">number</td>
<td>
Graph: O(K) : K = number of connected edges to the vertex
<br />
DirectedGraph: O(E) : E = number of edges in the graph
</td>
</tr>
</table>
<table>
<tr><th>return</th><th>description</th></tr>
<tr>
<td>number</td><td>number of removed edges</td>
</tr>
</table>
<table>
<tr>
<th colspan="2">runtime</th>
</tr>
<tr><td>Graph</td><td>O(K) : K = number of connected edges to the vertex</td></tr>
<tr><td>Directed Graph</td><td>O(E) : E = number of edges in the graph</td></tr>
</table>
#### Example
```js
const dg = new DirectedGraph();
dg.addVertex('v1');
dg.addVertex('v2');
dg.addVertex('v3');
dg.addEdge('v1', 'v2');
dg.addEdge('v2', 'v1'); // this is counted as a direction in directed graph.
dg.addEdge('v1', 'v3');
dg.removeEdges('v1'); // 3
const dg = new DirectedGraph()
.addVertex('v1')
.addVertex('v2')
.addVertex('v3')
.addEdge('v1', 'v2')
.addEdge('v2', 'v1')
.addEdge('v1', 'v3')
.removeEdges('v1'); // 3
const g = new Graph();
g.addVertex('v1');
g.addVertex('v2');
g.addVertex('v3');
g.addEdge('v1', 'v2');
g.addEdge('v1', 'v3');
g.removeEdges('v1'); // 2
const g = new Graph()
.addVertex('v1')
.addVertex('v2')
.addVertex('v3')
.addEdge('v1', 'v2')
.addEdge('v1', 'v3')
.removeEdges('v1'); // 2
```
### .traverseDfs(srcKey, cb)
traverses the graph using the depth-first recursive search.
Traverses the graph using the depth-first recursive search.
<table>
<tr><th align="center" colspan="3">params</th></tr>
<tr><td><b>name</b></td><td align="center"><b>type</b></td><td align="center"><b>description</b></td></tr>
<tr><td>srcKey</td><td>number or string</td><td>the starting vertex key</td></tr>
<tr><td>cb</td><td>function</td><td>the callback that is called with each vertex</td></tr>
<tr>
<th align="center">params</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
srcKey: number | string
<br />
cb: function
</td>
<td>
O(V) : V = number of vertices in the graph
</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr><td>O(V) : V = the number of vertices in the graph</td></tr>
</table>
#### Example
```js
directedGraph.traverseDfs('v1', (v) => console.log(`${v.getKey()}:${v.getValue()}`));
directedGraph.traverseDfs('v1', (key, value) => console.log(`${key}: ${value}`));
/*
v1:1
v2:2
v4:4
v3:3
v1: 1
v2: 2
v4: 4
v3: 3
*/
graph.traverseDfs('v1', (v) => console.log(v.serialize()));
graph.traverseDfs('v1', (key, value) => console.log(`${key}: ${value}`));
/*
{ key: 'v1', value: true }
{ key: 'v2', value: true }
{ key: 'v4', value: true }
{ key: 'v3', value: true }
v1: true
v2: true
v4: true
v3: true
*/

@@ -465,35 +405,36 @@ ```

### .traverseBfs(srcKey, cb)
traverses the graph using the breadth-first search with a queue.
Traverses the graph using the breadth-first search with a queue.
<table>
<tr><th align="center" colspan="3">params</th></tr>
<tr><td><b>name</b></td><td align="center"><b>type</b></td><td align="center"><b>description</b></td></tr>
<tr><td>srcKey</td><td>number or string</td><td>the starting vertex key</td></tr>
<tr><td>cb</td><td>function</td><td>the callback that is called with each vertex</td></tr>
<tr>
<th align="center">params</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
srcKey: number | string
<br />
cb: function
</td>
<td>
O(V) : V = number of vertices in the graph
</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr><td>O(V) : V = the number of vertices in the graph</td></tr>
</table>
#### Example
```js
directedGraph.traverseBfs('v1', (v) => console.log(`${v.getKey()}:${v.getValue()}`));
directedGraph.traverseBfs('v1', (key, value) => console.log(`${key}: ${value}`));
/*
v1:1
v2:2
v4:4
v3:3
v1: 1
v2: 2
v4: 4
v3: 3
*/
graph.traverseBfs('v1', (v) => console.log(v.serialize()));
graph.traverseBfs('v1', (key, value) => console.log(`${key}: ${value}`));
/*
{ key: 'v1', value: true }
{ key: 'v2', value: true }
{ key: 'v3', value: true }
{ key: 'v4', value: true }
v1: true
v2: true
v3: true
v4: true
*/

@@ -503,3 +444,3 @@ ```

### .clear()
clears all vertices and edges in the graph.
Clears all vertices and edges in the graph.

@@ -515,32 +456,12 @@ <table>

#### Example
```js
directedGraph.clear();
console.log(directedGraph.verticesCount()); // 0
console.log(directedGraph.edgesCount()); // 0
console.log(directedGraph.getVerticesCount()); // 0
console.log(directedGraph.getEdgesCount()); // 0
graph.clear();
console.log(graph.verticesCount()); // 0
console.log(graph.edgesCount()); // 0
console.log(graph.getVerticesCount()); // 0
console.log(graph.getEdgesCount()); // 0
```
### Vertex
#### .getKey()
returns the vertex key.
<table>
<tr><th>return</th></tr>
<tr><td>string or number</td></tr>
</table>
#### .getValue()
returns the vertex associated value.
<table>
<tr><th>return</th></tr>
<tr><td>object</td></tr>
</table>
## Build

@@ -547,0 +468,0 @@ ```

101

src/directedGraph.js
/**
* @datastructures-js/graph
* datastructures-js/graph
* @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>

@@ -8,7 +8,5 @@ * @license MIT

const Queue = require('@datastructures-js/queue');
const Vertex = require('./vertex');
/**
* @class DirectedGraph
* A graph with a directed path between vertices
* @class
*/

@@ -23,19 +21,19 @@ class DirectedGraph {

/**
* Adds a vertex to the graph
* @public
* adds a vertex to the graph
* @param {number|string} key
* @param {object} value
* @returns {Vertex}
* @return {DirectedGraph}
*/
addVertex(key, value) {
this._vertices.set(key, new Vertex(key, value));
this._vertices.set(key, value);
if (!this._edges.has(key)) {
this._edges.set(key, new Map());
}
return this._vertices.get(key);
return this;
}
/**
* Checks if the graph has a vertex
* @public
* checks if the graph has a vertex by its key
* @param {number|string} key

@@ -49,5 +47,6 @@ * @return {boolean}

/**
* Removes a vertex and all its edges from the graph
* @public
* remove a vertex and all its in and out edges
* @param {number|string} key
* @return {boolean}
*/

@@ -64,7 +63,7 @@ removeVertex(key) {

/**
* Returns the number of vertices in the graph
* @public
* the number of vertices in the graph
* @returns {number}
* @return {number}
*/
verticesCount() {
getVerticesCount() {
return this._vertices.size;

@@ -74,8 +73,7 @@ }

/**
* Adds a directed edge from a source vertex to a destination
* @public
* add a direction from source to destination
* @param {number|string} srcKey
* @param {number|string} destKey
* @param {number} weight
* @throws {Error} if a vertex key does not exist
* @param {number} [weight] - default 1
*/

@@ -91,9 +89,15 @@ addEdge(srcKey, destKey, weight) {

this._edges.get(srcKey).set(destKey, +weight || 1);
if (weight && Number.isNaN(+weight)) {
throw new Error('addEdge: expects a numberic weight');
}
const w = Number.isNaN(+weight) ? 1 : +weight;
this._edges.get(srcKey).set(destKey, w);
this._edgesCount += 1;
return this;
}
/**
* Checks if there is a direction between two nodes
* @public
* checks if there is a direction from source to destination
* @param {number|string} srcKey

@@ -110,4 +114,4 @@ * @param {number|string} destKey

/**
* Gets the weight of an edge if exists
* @public
* get the weight of an edge if exists
* @param {number|string} srcKey

@@ -118,4 +122,10 @@ * @param {number|string} destKey

getWeight(srcKey, destKey) {
if (this.hasVertex(srcKey) && srcKey === destKey) return 0;
if (!this.hasEdge(srcKey, destKey)) return null;
if (this.hasVertex(srcKey) && srcKey === destKey) {
return 0;
}
if (!this.hasEdge(srcKey, destKey)) {
return Infinity;
}
return this._edges.get(srcKey).get(destKey);

@@ -125,4 +135,4 @@ }

/**
* Removes the direction from source to destination
* @public
* removes the direction from source to destination
* @param {number|string} srcKey

@@ -132,3 +142,5 @@ * @param {number|string} destKey

removeEdge(srcKey, destKey) {
if (!this.hasEdge(srcKey, destKey)) return false;
if (!this.hasEdge(srcKey, destKey)) {
return false;
}

@@ -141,4 +153,4 @@ this._edges.get(srcKey).delete(destKey);

/**
* Removes in and out directions of a vertex
* @public
* removes all directions from and to a vertex
* @param {number|string} key

@@ -148,24 +160,26 @@ * @return {number} number of removed edges

removeEdges(key) {
if (!this.hasVertex(key)) return 0;
if (!this.hasVertex(key)) {
return 0;
}
let removed = 0;
let removedEdgesCount = 0;
this._edges.forEach((destEdges, srcKey) => {
if (destEdges.has(key)) {
this.removeEdge(srcKey, key);
removed += 1;
removedEdgesCount += 1;
}
});
removed += this._edges.get(key).size;
removedEdgesCount += this._edges.get(key).size;
this._edgesCount -= this._edges.get(key).size;
this._edges.set(key, new Map());
return removed;
return removedEdgesCount;
}
/**
* Returns the number of edges in the graph
* @public
* the number of directions in the graph
* @returns {number}
*/
edgesCount() {
getEdgesCount() {
return this._edgesCount;

@@ -175,5 +189,5 @@ }

/**
* Traverse all vertices in the graph using depth-first search
* @public
* traverse all vertices in the graph using depth-first search
* @param {number|string} srcKey
* @param {number|string} srcKey - starting node
* @param {function} cb

@@ -184,3 +198,3 @@ */

cb(this._vertices.get(srcKey));
cb(srcKey, this._vertices.get(srcKey));
visited.add(srcKey);

@@ -194,5 +208,5 @@

/**
* Traverse all vertices in the graph using breadth-first search
* @public
* traverse all vertices in the graph using breadth-first search
* @param {number|string} srcKey
* @param {number|string} srcKey - starting node
* @param {function} cb

@@ -207,8 +221,9 @@ */

while (!queue.isEmpty()) {
const vertex = this._vertices.get(queue.dequeue());
cb(vertex);
this._edges.get(vertex.getKey()).forEach((weight, destKey) => {
if (visited.has(destKey)) return;
queue.enqueue(destKey);
visited.add(destKey);
const nextKey = queue.dequeue();
cb(nextKey, this._vertices.get(nextKey));
this._edges.get(nextKey).forEach((weight, destKey) => {
if (!visited.has(destKey)) {
queue.enqueue(destKey);
visited.add(destKey);
}
});

@@ -219,4 +234,4 @@ }

/**
* Clears the graph
* @public
* clears the graph
*/

@@ -223,0 +238,0 @@ clear() {

32

src/graph.js
/**
* @datastructures-js/graph
* datastructures-js/graph
* @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>

@@ -12,19 +12,20 @@ * @license MIT

* @extends DirectedGraph
* A graph with a connecting edge between vertices
*/
class Graph extends DirectedGraph {
/**
* Removes all edges connected to a vertex
* @public
* @override
* removes all edges of a vertex
* @param {number|string} key
* @return {number} number of removed edges
* @return {number} number of removedEdgesCount edges
*/
removeEdges(key) {
if (!this.hasVertex(key)) return 0;
if (!this.hasVertex(key)) {
return 0;
}
let removed = 0;
let removedEdgesCount = 0;
this._edges.get(key).forEach((weight, destKey) => {
this.removeEdge(destKey, key);
removed += 1;
removedEdgesCount += 1;
});

@@ -34,23 +35,22 @@

this._edges.set(key, new Map());
return removed;
return removedEdgesCount;
}
/**
* Adds an edge between two existing vertices
* @public
* @override
* add a connecting edge between two vertices
* @param {number|string} srcKey
* @param {number|string} destKey
* @param {number} weight
* @throws {Error} if a vertex key does not exist
* @param {number} [weight] - default 1
*/
addEdge(sourceKey, destKey, weight) {
super.addEdge(sourceKey, destKey, weight);
super.addEdge(destKey, sourceKey, weight);
return super.addEdge(destKey, sourceKey, weight);
}
/**
* Removes the connecting edge between two vertices
* @public
* @override
* removes the connecting edge between two vertices
* @param {number|string} srcKey

@@ -66,9 +66,9 @@ * @param {number|string} destKey

/**
* Gets the number of edges in the graph
* @public
* @override
* the number of connecting edges in the graph
* @returns {number}
*/
edgesCount() {
return super.edgesCount() / 2;
getEdgesCount() {
return super.getEdgesCount() / 2;
}

@@ -75,0 +75,0 @@ }

src/vertex.js
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc