New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

undirected-graph-typed

Package Overview
Dependencies
Maintainers
1
Versions
173
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

undirected-graph-typed - npm Package Compare versions

Comparing version 1.42.1 to 1.42.2

48

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

@@ -255,6 +255,2 @@ import type { DijkstraResult, VertexKey } from '../../types';

* The Floyd-Warshall algorithm is used to find the shortest paths between all pairs of nodes in a graph. It employs dynamic programming to compute the shortest paths from any node to any other node. The Floyd-Warshall algorithm's advantage lies in its ability to handle graphs with negative-weight edges, and it can simultaneously compute shortest paths between any two nodes.
*/
/**
* Floyd algorithm time: O(VO^3) space: O(VO^2), not support graph with negative weight cycle
* all pairs
* /

@@ -268,3 +264,3 @@

* graph.
* @returns The function `floyd()` returns an object with two properties: `costs` and `predecessor`. The `costs`
* @returns The function `floydWarshall()` returns an object with two properties: `costs` and `predecessor`. The `costs`
* property is a 2D array of numbers representing the shortest path costs between vertices in a graph. The

@@ -274,3 +270,3 @@ * `predecessor` property is a 2D array of vertices (or `null`) representing the predecessor vertices in the shortest

*/
floyd(): {
floydWarshall(): {
costs: number[][];

@@ -295,3 +291,3 @@ predecessor: (VO | null)[][];

* strongly connected components (SCCs), and cycles in a graph.
* @param {boolean} [needArticulationPoints] - A boolean value indicating whether or not to calculate and return the
* @param {boolean} [needCutVertexes] - A boolean value indicating whether or not to calculate and return the
* articulation points in the graph. Articulation points are the vertices in a graph whose removal would increase the

@@ -309,10 +305,44 @@ * number of connected components in the graph.

*/
tarjan(needArticulationPoints?: boolean, needBridges?: boolean, needSCCs?: boolean, needCycles?: boolean): {
tarjan(needCutVertexes?: boolean, needBridges?: boolean, needSCCs?: boolean, needCycles?: boolean): {
dfnMap: Map<VO, number>;
lowMap: Map<VO, number>;
bridges: EO[];
articulationPoints: VO[];
cutVertexes: VO[];
SCCs: Map<number, VO[]>;
cycles: Map<number, VO[]>;
};
/**
* The function returns a map that associates each vertex object with its corresponding depth-first
* number.
* @returns A Map object with keys of type VO and values of type number.
*/
getDFNMap(): Map<VO, number>;
/**
* The function returns a Map object that contains the low values of each vertex in a Tarjan
* algorithm.
* @returns The method `getLowMap()` is returning a `Map` object with keys of type `VO` and values of
* type `number`.
*/
getLowMap(): Map<VO, number>;
/**
* The function `getCycles` returns a map of cycles found using the Tarjan algorithm.
* @returns The function `getCycles()` is returning a `Map<number, VO[]>`.
*/
getCycles(): Map<number, VO[]>;
/**
* The function "getCutVertexes" returns an array of cut vertexes using the Tarjan algorithm.
* @returns an array of VO objects, specifically the cut vertexes.
*/
getCutVertexes(): VO[];
/**
* The function "getSCCs" returns a map of strongly connected components (SCCs) using the Tarjan
* algorithm.
* @returns a map where the keys are numbers and the values are arrays of VO objects.
*/
getSCCs(): Map<number, VO[]>;
/**
* The function "getBridges" returns an array of bridges using the Tarjan algorithm.
* @returns the bridges found using the Tarjan algorithm.
*/
getBridges(): EO[];
protected abstract _addEdgeOnly(edge: EO): boolean;

@@ -319,0 +349,0 @@ protected _addVertexOnly(newVertex: VO): boolean;

70

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

@@ -707,6 +707,2 @@ "use strict";

* The Floyd-Warshall algorithm is used to find the shortest paths between all pairs of nodes in a graph. It employs dynamic programming to compute the shortest paths from any node to any other node. The Floyd-Warshall algorithm's advantage lies in its ability to handle graphs with negative-weight edges, and it can simultaneously compute shortest paths between any two nodes.
*/
/**
* Floyd algorithm time: O(VO^3) space: O(VO^2), not support graph with negative weight cycle
* all pairs
* /

@@ -720,3 +716,3 @@

* graph.
* @returns The function `floyd()` returns an object with two properties: `costs` and `predecessor`. The `costs`
* @returns The function `floydWarshall()` returns an object with two properties: `costs` and `predecessor`. The `costs`
* property is a 2D array of numbers representing the shortest path costs between vertices in a graph. The

@@ -726,3 +722,3 @@ * `predecessor` property is a 2D array of vertices (or `null`) representing the predecessor vertices in the shortest

*/
floyd() {
floydWarshall() {
var _a;

@@ -774,3 +770,3 @@ const idAndVertices = [...this._vertices];

* strongly connected components (SCCs), and cycles in a graph.
* @param {boolean} [needArticulationPoints] - A boolean value indicating whether or not to calculate and return the
* @param {boolean} [needCutVertexes] - A boolean value indicating whether or not to calculate and return the
* articulation points in the graph. Articulation points are the vertices in a graph whose removal would increase the

@@ -788,3 +784,3 @@ * number of connected components in the graph.

*/
tarjan(needArticulationPoints, needBridges, needSCCs, needCycles) {
tarjan(needCutVertexes = false, needBridges = false, needSCCs = true, needCycles = false) {
// !! in undirected graph we will not let child visit parent when dfs

@@ -794,4 +790,4 @@ // !! articulation point(in dfs search tree not in graph): (cur !== root && cur.has(child)) && (low(child) >= dfn(cur)) || (cur === root && cur.children() >= 2)

const defaultConfig = false;
if (needArticulationPoints === undefined)
needArticulationPoints = defaultConfig;
if (needCutVertexes === undefined)
needCutVertexes = defaultConfig;
if (needBridges === undefined)

@@ -811,3 +807,3 @@ needBridges = defaultConfig;

const [root] = vertices.values();
const articulationPoints = [];
const cutVertexes = [];
const bridges = [];

@@ -835,6 +831,6 @@ let dfn = 0;

if (childLow !== undefined && curFromMap !== undefined) {
if (needArticulationPoints) {
if (needCutVertexes) {
if ((cur === root && childCount >= 2) || (cur !== root && childLow >= curFromMap)) {
// todo not ensure the logic if (cur === root && childCount >= 2 || ((cur !== root) && (childLow >= curFromMap))) {
articulationPoints.push(cur);
cutVertexes.push(cur);
}

@@ -884,4 +880,50 @@ }

}
return { dfnMap, lowMap, bridges, articulationPoints, SCCs, cycles };
return { dfnMap, lowMap, bridges, cutVertexes, SCCs, cycles };
}
/**
* The function returns a map that associates each vertex object with its corresponding depth-first
* number.
* @returns A Map object with keys of type VO and values of type number.
*/
getDFNMap() {
return this.tarjan(false, false, false, false).dfnMap;
}
/**
* The function returns a Map object that contains the low values of each vertex in a Tarjan
* algorithm.
* @returns The method `getLowMap()` is returning a `Map` object with keys of type `VO` and values of
* type `number`.
*/
getLowMap() {
return this.tarjan(false, false, false, false).lowMap;
}
/**
* The function `getCycles` returns a map of cycles found using the Tarjan algorithm.
* @returns The function `getCycles()` is returning a `Map<number, VO[]>`.
*/
getCycles() {
return this.tarjan(false, false, false, true).cycles;
}
/**
* The function "getCutVertexes" returns an array of cut vertexes using the Tarjan algorithm.
* @returns an array of VO objects, specifically the cut vertexes.
*/
getCutVertexes() {
return this.tarjan(true, false, false, false).cutVertexes;
}
/**
* The function "getSCCs" returns a map of strongly connected components (SCCs) using the Tarjan
* algorithm.
* @returns a map where the keys are numbers and the values are arrays of VO objects.
*/
getSCCs() {
return this.tarjan(false, false, true, false).SCCs;
}
/**
* The function "getBridges" returns an array of bridges using the Tarjan algorithm.
* @returns the bridges found using the Tarjan algorithm.
*/
getBridges() {
return this.tarjan(false, true, false, false).bridges;
}
_addVertexOnly(newVertex) {

@@ -888,0 +930,0 @@ if (this.hasVertex(newVertex)) {

4

package.json
{
"name": "undirected-graph-typed",
"version": "1.42.1",
"version": "1.42.2",
"description": "Undirected Graph. Javascript & Typescript Data Structure.",

@@ -148,4 +148,4 @@ "main": "dist/index.js",

"dependencies": {
"data-structure-typed": "^1.42.1"
"data-structure-typed": "^1.42.2"
}
}

102

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

@@ -67,4 +67,3 @@ /**

EO extends AbstractEdge<E> = AbstractEdge<E>
> implements IGraph<V, E, VO, EO>
{
> implements IGraph<V, E, VO, EO> {
protected _vertices: Map<VertexKey, VO> = new Map<VertexKey, VO>();

@@ -240,6 +239,6 @@

const stack: { vertex: VO, path: VO[] }[] = [];
stack.push({ vertex: vertex1, path: [vertex1] });
stack.push({vertex: vertex1, path: [vertex1]});
while (stack.length > 0) {
const { vertex, path } = stack.pop()!;
const {vertex, path} = stack.pop()!;

@@ -255,3 +254,3 @@ if (vertex === vertex2) {

const newPath = [...path, neighbor];
stack.push({ vertex: neighbor, path: newPath });
stack.push({vertex: neighbor, path: newPath});
}

@@ -264,4 +263,2 @@ }

/**

@@ -529,10 +526,10 @@ * The function calculates the sum of weights along a given path.

getMinDist &&
distMap.forEach((d, v) => {
if (v !== srcVertex) {
if (d < minDist) {
minDist = d;
if (genPaths) minDest = v;
}
distMap.forEach((d, v) => {
if (v !== srcVertex) {
if (d < minDist) {
minDist = d;
if (genPaths) minDest = v;
}
});
}
});

@@ -599,3 +596,3 @@ genPaths && getPaths(minDest);

const heap = new PriorityQueue<{key: number; value: VO}>({comparator: (a, b) => a.key - b.key});
const heap = new PriorityQueue<{ key: number; value: VO }>({comparator: (a, b) => a.key - b.key});
heap.add({key: 0, value: srcVertex});

@@ -811,7 +808,2 @@

* The Floyd-Warshall algorithm is used to find the shortest paths between all pairs of nodes in a graph. It employs dynamic programming to compute the shortest paths from any node to any other node. The Floyd-Warshall algorithm's advantage lies in its ability to handle graphs with negative-weight edges, and it can simultaneously compute shortest paths between any two nodes.
*/
/**
* Floyd algorithm time: O(VO^3) space: O(VO^2), not support graph with negative weight cycle
* all pairs
* /

@@ -825,3 +817,3 @@

* graph.
* @returns The function `floyd()` returns an object with two properties: `costs` and `predecessor`. The `costs`
* @returns The function `floydWarshall()` returns an object with two properties: `costs` and `predecessor`. The `costs`
* property is a 2D array of numbers representing the shortest path costs between vertices in a graph. The

@@ -831,3 +823,3 @@ * `predecessor` property is a 2D array of vertices (or `null`) representing the predecessor vertices in the shortest

*/
floyd(): {costs: number[][]; predecessor: (VO | null)[][]} {
floydWarshall(): { costs: number[][]; predecessor: (VO | null)[][] } {
const idAndVertices = [...this._vertices];

@@ -883,3 +875,3 @@ const n = idAndVertices.length;

* strongly connected components (SCCs), and cycles in a graph.
* @param {boolean} [needArticulationPoints] - A boolean value indicating whether or not to calculate and return the
* @param {boolean} [needCutVertexes] - A boolean value indicating whether or not to calculate and return the
* articulation points in the graph. Articulation points are the vertices in a graph whose removal would increase the

@@ -897,3 +889,3 @@ * number of connected components in the graph.

*/
tarjan(needArticulationPoints?: boolean, needBridges?: boolean, needSCCs?: boolean, needCycles?: boolean) {
tarjan(needCutVertexes: boolean = false, needBridges: boolean = false, needSCCs: boolean = true, needCycles: boolean = false) {
// !! in undirected graph we will not let child visit parent when dfs

@@ -904,3 +896,3 @@ // !! articulation point(in dfs search tree not in graph): (cur !== root && cur.has(child)) && (low(child) >= dfn(cur)) || (cur === root && cur.children() >= 2)

const defaultConfig = false;
if (needArticulationPoints === undefined) needArticulationPoints = defaultConfig;
if (needCutVertexes === undefined) needCutVertexes = defaultConfig;
if (needBridges === undefined) needBridges = defaultConfig;

@@ -920,3 +912,3 @@ if (needSCCs === undefined) needSCCs = defaultConfig;

const articulationPoints: VO[] = [];
const cutVertexes: VO[] = [];
const bridges: EO[] = [];

@@ -945,6 +937,6 @@ let dfn = 0;

if (childLow !== undefined && curFromMap !== undefined) {
if (needArticulationPoints) {
if (needCutVertexes) {
if ((cur === root && childCount >= 2) || (cur !== root && childLow >= curFromMap)) {
// todo not ensure the logic if (cur === root && childCount >= 2 || ((cur !== root) && (childLow >= curFromMap))) {
articulationPoints.push(cur);
cutVertexes.push(cur);
}

@@ -1000,5 +992,57 @@ }

return {dfnMap, lowMap, bridges, articulationPoints, SCCs, cycles};
return {dfnMap, lowMap, bridges, cutVertexes, SCCs, cycles};
}
/**
* The function returns a map that associates each vertex object with its corresponding depth-first
* number.
* @returns A Map object with keys of type VO and values of type number.
*/
getDFNMap(): Map<VO, number> {
return this.tarjan(false, false, false, false).dfnMap;
}
/**
* The function returns a Map object that contains the low values of each vertex in a Tarjan
* algorithm.
* @returns The method `getLowMap()` is returning a `Map` object with keys of type `VO` and values of
* type `number`.
*/
getLowMap(): Map<VO, number> {
return this.tarjan(false, false, false, false).lowMap;
}
/**
* The function `getCycles` returns a map of cycles found using the Tarjan algorithm.
* @returns The function `getCycles()` is returning a `Map<number, VO[]>`.
*/
getCycles(): Map<number, VO[]> {
return this.tarjan(false, false, false, true).cycles;
}
/**
* The function "getCutVertexes" returns an array of cut vertexes using the Tarjan algorithm.
* @returns an array of VO objects, specifically the cut vertexes.
*/
getCutVertexes(): VO[] {
return this.tarjan(true, false, false, false).cutVertexes;
}
/**
* The function "getSCCs" returns a map of strongly connected components (SCCs) using the Tarjan
* algorithm.
* @returns a map where the keys are numbers and the values are arrays of VO objects.
*/
getSCCs(): Map<number, VO[]> {
return this.tarjan(false, false, true, false).SCCs;
}
/**
* The function "getBridges" returns an array of bridges using the Tarjan algorithm.
* @returns the bridges found using the Tarjan algorithm.
*/
getBridges() {
return this.tarjan(false, true, false, false).bridges;
}
protected abstract _addEdgeOnly(edge: EO): boolean;

@@ -1005,0 +1049,0 @@

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