🚀 Socket Launch Week 🚀 Day 5: Introducing Socket Fix.Learn More →
tarjan-graph
Advanced tools
tarjan-graph - npm Package Compare versions
Comparing version 2.0.0 to 3.0.0
@@ -1,27 +0,27 @@ | ||
| interface Vertex { | ||
| name: string; | ||
| successors: Vertex[]; | ||
| index: number; | ||
| lowLink: number; | ||
| onStack: boolean; | ||
| visited: boolean; | ||
| reset: () => void; | ||
| export declare class Vertex { | ||
| readonly name: string; | ||
| successors: Vertex[]; | ||
| index: number; | ||
| lowLink: number; | ||
| onStack: boolean; | ||
| visited: boolean; | ||
| constructor(name: string, successors?: Vertex[]); | ||
| reset(): void; | ||
| } | ||
| declare class Graph { | ||
| vertices: { [key: string]: Vertex }; | ||
| add(key: string, descendants: string[] | string): Graph; | ||
| reset(): void; | ||
| addAndVerify(key: string, descendants: string[] | string): Graph; | ||
| dfs(key: string, visitor: (v: Vertex) => void): void; | ||
| getDescendants(key: string): string[]; | ||
| hasCycle(): boolean; | ||
| getStronglyConnectedComponents(): Vertex[][]; | ||
| getCycles(): Vertex[][]; | ||
| clone(): Graph; | ||
| toDot(): string | ||
| export declare class CycleError extends Error { | ||
| readonly cycles: any[]; | ||
| constructor(message: string, cycles: any[]); | ||
| } | ||
| export { | ||
| Graph | ||
| export default class Graph { | ||
| private readonly vertices; | ||
| add(key: string, descendants: string | string[]): this; | ||
| reset(): void; | ||
| addAndVerify(key: string, descendants: string | string[]): this; | ||
| dfs(key: string, visitor: (v: Vertex) => void): void; | ||
| getDescendants(key: string): string[]; | ||
| hasCycle(): boolean; | ||
| getStronglyConnectedComponents(): Vertex[][]; | ||
| getCycles(): Vertex[][]; | ||
| clone(): Graph; | ||
| toDot(): string; | ||
| } |
368
index.js
@@ -0,197 +1,179 @@ | ||
| "use strict"; | ||
| Object.defineProperty(exports, "__esModule", { value: true }); | ||
| exports.CycleError = exports.Vertex = void 0; | ||
| class Vertex { | ||
| constructor(name, successors) { | ||
| this.name = name; | ||
| this.successors = successors; | ||
| this.reset(); | ||
| } | ||
| reset() { | ||
| this.index = -1; | ||
| this.lowLink = -1; | ||
| this.onStack = false; | ||
| this.visited = false; | ||
| } | ||
| constructor(name, successors) { | ||
| this.index = -1; | ||
| this.lowLink = -1; | ||
| this.onStack = false; | ||
| this.visited = false; | ||
| this.name = name; | ||
| this.successors = successors || []; | ||
| this.reset(); | ||
| } | ||
| reset() { | ||
| this.index = -1; | ||
| this.lowLink = -1; | ||
| this.onStack = false; | ||
| this.visited = false; | ||
| } | ||
| } | ||
| exports.Vertex = Vertex; | ||
| class CycleError extends Error { | ||
| constructor(message, cycles) { | ||
| super(message); | ||
| this.cycles = cycles; | ||
| } | ||
| } | ||
| exports.CycleError = CycleError; | ||
| class Graph { | ||
| constructor() { | ||
| this.vertices = {}; | ||
| } | ||
| add(key, descendants) { | ||
| descendants = Array.isArray(descendants) ? descendants : [descendants]; | ||
| const successors = descendants.map((key) => { | ||
| if (!this.vertices[key]) { | ||
| this.vertices[key] = new Vertex(key, []); | ||
| } | ||
| return this.vertices[key]; | ||
| }); | ||
| if (!this.vertices[key]) { | ||
| this.vertices[key] = new Vertex(key); | ||
| } | ||
| this.vertices[key].successors = successors.concat([]).reverse(); | ||
| return this; | ||
| } | ||
| reset() { | ||
| Object.keys(this.vertices).forEach((key) => { | ||
| this.vertices[key].reset(); | ||
| }); | ||
| } | ||
| addAndVerify(key, descendants) { | ||
| this.add(key, descendants); | ||
| const cycles = this.getCycles(); | ||
| if (cycles.length) { | ||
| let message = `Detected ${cycles.length} cycle${cycles.length === 1 ? '' : 's'}:`; | ||
| message += '\n' + cycles.map((scc) => { | ||
| const names = scc.map(v => v.name); | ||
| return ` ${names.join(' -> ')} -> ${names[0]}`; | ||
| }).join('\n'); | ||
| const err = new Error(message); | ||
| err.cycles = cycles; | ||
| throw err; | ||
| } | ||
| return this; | ||
| } | ||
| dfs(key, visitor) { | ||
| this.reset(); | ||
| const stack = [this.vertices[key]]; | ||
| let v; | ||
| while (v = stack.pop()) { | ||
| if (v.visited) { | ||
| continue; | ||
| } | ||
| //pre-order traversal | ||
| visitor(v); | ||
| v.visited = true; | ||
| v.successors.forEach(w => stack.push(w)); | ||
| } | ||
| } | ||
| getDescendants(key) { | ||
| const descendants = []; | ||
| let ignore = true; | ||
| this.dfs(key, (v) => { | ||
| if (ignore) { | ||
| //ignore the first node | ||
| ignore = false; | ||
| return; | ||
| } | ||
| descendants.push(v.name); | ||
| }); | ||
| return descendants; | ||
| } | ||
| hasCycle() { | ||
| return this.getCycles().length > 0; | ||
| } | ||
| getStronglyConnectedComponents() { | ||
| const V = Object.keys(this.vertices).map((key) => { | ||
| this.vertices[key].reset(); | ||
| return this.vertices[key]; | ||
| }); | ||
| let index = 0; | ||
| const stack = []; | ||
| const components = []; | ||
| const stronglyConnect = (v) => { | ||
| v.index = index; | ||
| v.lowLink = index; | ||
| index++; | ||
| stack.push(v); | ||
| v.onStack = true; | ||
| v.successors.forEach((w) => { | ||
| if (w.index < 0) { | ||
| stronglyConnect(w); | ||
| v.lowLink = Math.min(v.lowLink, w.lowLink); | ||
| } else if (w.onStack) { | ||
| v.lowLink = Math.min(v.lowLink, w.index); | ||
| } | ||
| }); | ||
| if (v.lowLink === v.index) { | ||
| const scc = []; | ||
| let w; | ||
| do { | ||
| w = stack.pop(); | ||
| w.onStack = false; | ||
| scc.push(w); | ||
| } while (w !== v); | ||
| components.push(scc); | ||
| } | ||
| }; | ||
| V.forEach(function(v) { | ||
| if (v.index < 0) { | ||
| stronglyConnect(v); | ||
| } | ||
| }); | ||
| return components; | ||
| } | ||
| getCycles() { | ||
| return this.getStronglyConnectedComponents().filter((scc) => { | ||
| if (scc.length > 1) { | ||
| return true; | ||
| } | ||
| const startNode = scc[0]; | ||
| return startNode && startNode.successors.some(node => node === startNode); | ||
| }); | ||
| } | ||
| clone() { | ||
| const graph = new Graph(); | ||
| Object.keys(this.vertices).forEach((key) => { | ||
| const v = this.vertices[key]; | ||
| graph.add(v.name, v.successors.map((w) => { | ||
| return w.name; | ||
| })); | ||
| }); | ||
| return graph; | ||
| } | ||
| toDot() { | ||
| const V = this.vertices; | ||
| const lines = [ 'digraph {' ]; | ||
| this.getCycles().forEach((scc, i) => { | ||
| lines.push(' subgraph cluster' + i + ' {'); | ||
| lines.push(' color=red;'); | ||
| lines.push(' ' + scc.map(v => v.name).join('; ') + ';'); | ||
| lines.push(' }'); | ||
| }); | ||
| Object.keys(V).forEach((key) => { | ||
| const v = V[key]; | ||
| if (v.successors.length) { | ||
| v.successors.forEach((w) => { | ||
| lines.push(` ${v.name} -> ${w.name}`); | ||
| }); | ||
| } | ||
| }); | ||
| lines.push('}'); | ||
| return lines.join('\n') + '\n'; | ||
| } | ||
| constructor() { | ||
| this.vertices = {}; | ||
| } | ||
| add(key, descendants) { | ||
| descendants = Array.isArray(descendants) ? descendants : [descendants]; | ||
| const successors = descendants.map((key) => { | ||
| if (!this.vertices[key]) { | ||
| this.vertices[key] = new Vertex(key, []); | ||
| } | ||
| return this.vertices[key]; | ||
| }); | ||
| if (!this.vertices[key]) { | ||
| this.vertices[key] = new Vertex(key); | ||
| } | ||
| this.vertices[key].successors = successors.concat([]).reverse(); | ||
| return this; | ||
| } | ||
| reset() { | ||
| Object.keys(this.vertices).forEach((key) => { | ||
| this.vertices[key].reset(); | ||
| }); | ||
| } | ||
| addAndVerify(key, descendants) { | ||
| this.add(key, descendants); | ||
| const cycles = this.getCycles(); | ||
| if (cycles.length) { | ||
| let message = `Detected ${cycles.length} cycle${cycles.length === 1 ? '' : 's'}:`; | ||
| message += '\n' + cycles.map((scc) => { | ||
| const names = scc.map(v => v.name); | ||
| return ` ${names.join(' -> ')} -> ${names[0]}`; | ||
| }).join('\n'); | ||
| throw new CycleError(message, cycles); | ||
| } | ||
| return this; | ||
| } | ||
| dfs(key, visitor) { | ||
| this.reset(); | ||
| const stack = [this.vertices[key]]; | ||
| let v; | ||
| while (v = stack.pop()) { | ||
| if (v.visited) { | ||
| continue; | ||
| } | ||
| //pre-order traversal | ||
| visitor(v); | ||
| v.visited = true; | ||
| v.successors.forEach(w => stack.push(w)); | ||
| } | ||
| } | ||
| getDescendants(key) { | ||
| const descendants = []; | ||
| let ignore = true; | ||
| this.dfs(key, (v) => { | ||
| if (ignore) { | ||
| //ignore the first node | ||
| ignore = false; | ||
| return; | ||
| } | ||
| descendants.push(v.name); | ||
| }); | ||
| return descendants; | ||
| } | ||
| hasCycle() { | ||
| return this.getCycles().length > 0; | ||
| } | ||
| getStronglyConnectedComponents() { | ||
| const V = Object.keys(this.vertices).map((key) => { | ||
| this.vertices[key].reset(); | ||
| return this.vertices[key]; | ||
| }); | ||
| let index = 0; | ||
| const stack = []; | ||
| const components = []; | ||
| const stronglyConnect = (v) => { | ||
| v.index = index; | ||
| v.lowLink = index; | ||
| index++; | ||
| stack.push(v); | ||
| v.onStack = true; | ||
| v.successors.forEach((w) => { | ||
| if (w.index < 0) { | ||
| stronglyConnect(w); | ||
| v.lowLink = Math.min(v.lowLink, w.lowLink); | ||
| } | ||
| else if (w.onStack) { | ||
| v.lowLink = Math.min(v.lowLink, w.index); | ||
| } | ||
| }); | ||
| if (v.lowLink === v.index) { | ||
| const scc = []; | ||
| let w; | ||
| do { | ||
| w = stack.pop(); | ||
| if (!w) { | ||
| break; | ||
| } | ||
| w.onStack = false; | ||
| scc.push(w); | ||
| } while (w !== v); | ||
| components.push(scc); | ||
| } | ||
| }; | ||
| V.forEach(function (v) { | ||
| if (v.index < 0) { | ||
| stronglyConnect(v); | ||
| } | ||
| }); | ||
| return components; | ||
| } | ||
| getCycles() { | ||
| return this.getStronglyConnectedComponents().filter((scc) => { | ||
| if (scc.length > 1) { | ||
| return true; | ||
| } | ||
| const startNode = scc[0]; | ||
| return startNode && startNode.successors.some(node => node === startNode); | ||
| }); | ||
| } | ||
| clone() { | ||
| const graph = new Graph(); | ||
| Object.keys(this.vertices).forEach((key) => { | ||
| const v = this.vertices[key]; | ||
| graph.add(v.name, v.successors.map((w) => { | ||
| return w.name; | ||
| })); | ||
| }); | ||
| return graph; | ||
| } | ||
| toDot() { | ||
| const V = this.vertices; | ||
| const lines = ['digraph {']; | ||
| this.getCycles().forEach((scc, i) => { | ||
| lines.push(' subgraph cluster' + i + ' {'); | ||
| lines.push(' color=red;'); | ||
| lines.push(' ' + scc.map(v => v.name).join('; ') + ';'); | ||
| lines.push(' }'); | ||
| }); | ||
| Object.keys(V).forEach((key) => { | ||
| const v = V[key]; | ||
| if (v.successors.length) { | ||
| v.successors.forEach((w) => { | ||
| lines.push(` ${v.name} -> ${w.name}`); | ||
| }); | ||
| } | ||
| }); | ||
| lines.push('}'); | ||
| return lines.join('\n') + '\n'; | ||
| } | ||
| } | ||
| module.exports = Graph; | ||
| exports.default = Graph; |
| { | ||
| "name": "tarjan-graph", | ||
| "version": "2.0.0", | ||
| "version": "3.0.0", | ||
| "license": "MIT", | ||
| "scripts": { | ||
| "build": "node_modules/.bin/tsc --project .", | ||
| "test": "node_modules/.bin/mocha -R spec tests" | ||
@@ -17,7 +18,8 @@ }, | ||
| "devDependencies": { | ||
| "mocha": "5.2.0", | ||
| "@types/node": "16.11.7", | ||
| "mocha": "9.2.0", | ||
| "should": "13.2.3", | ||
| "typescript": "3.0.1" | ||
| "typescript": "4.5.5" | ||
| }, | ||
| "types": "./index.d.ts" | ||
| } |
@@ -15,4 +15,4 @@ # tarjan-graph | ||
| ## Installation | ||
| Note: as of v1.0.0 this library requires node >= v8.0.0. | ||
| Use v0.3.0 for node < v8.0.0. | ||
| Install using `npm`: | ||
| ``` | ||
@@ -22,4 +22,28 @@ npm install tarjan-graph | ||
| * Note: as of v1.0.0 this library requires node >= v8.0.0. | ||
| Use v0.3.0 for node < v8.0.0. | ||
| * Note: as of v3.0.0 this library was ported to TypeScript and the default | ||
| export changed to get with the times. So now instead of this: | ||
| ```typescript | ||
| const Graph = require('tarjan-graph'); // js | ||
| import Graph = require('tarjan-graph'); // ts | ||
| ``` | ||
| you now do this: | ||
| ```typescript | ||
| const Graph = require('tarjan-graph').default; // js | ||
| import Graph from 'tarjan-graph'; // ts | ||
| ``` | ||
| ## Usage | ||
| JavaScript: | ||
| ```javascript | ||
| const Graph = require('tarjan-graph').default; | ||
| ``` | ||
| TypeScript: | ||
| ```typescript | ||
| import Graph from 'tarjan-graph'; | ||
| ``` | ||
| All examples use the following graph: | ||
@@ -29,3 +53,3 @@ | ||
| node -e " | ||
| const Graph = require('tarjan-graph'); | ||
| const Graph = require('tarjan-graph').default; | ||
@@ -46,3 +70,3 @@ const graph = new Graph() | ||
| console.log(graph.toDot()); | ||
| " | dot -o docs/example-graph.png -Tpng | ||
| " | dot -o docs/example-graph.png -Tpng` | ||
| ``` | ||
@@ -49,0 +73,0 @@  |
No alert changes
Improved metrics
- Total package byte prevSize
9729
34.99%- Lines of code
206
10.16%- Number of lines in readme file
157
18.05%Worsened metrics
- Dev dependency count
4
33.33%No dependency changes