feat: ts for algs

stjordanis · Apr 28, 2021 · 128ff6b · 128ff6b
1 parent 1b1e65e
commit 128ff6b
Show file tree

Hide file tree

Showing 23 changed files with 97 additions and 118 deletions.
diff --git a/lib/alg/components.js → lib/alg/components.ts b/lib/alg/components.js → lib/alg/components.ts
@@ -1,10 +1,9 @@
-const _ = require('../lodash');
+import type { Graph } from '..';
+import * as _ from '../lodash';
 
-module.exports = components;
-
-function components(g) {
+export function components(g: Graph) {
   const visited = {};
-  const cmpts = [];
+  const cmpts: any[][] = [];
   let cmpt;
 
   function dfs(v) {

diff --git a/lib/alg/dfs.js → lib/alg/dfs.ts b/lib/alg/dfs.js → lib/alg/dfs.ts
@@ -1,6 +1,5 @@
-const _ = require('../lodash');
-
-module.exports = dfs;
+import type { Graph } from '..';
+import * as _ from '../lodash';
 
 /*
  * A helper that preforms a pre- or post-order traversal on the input graph
@@ -10,11 +9,7 @@ module.exports = dfs;
  *
  * Order must be one of "pre" or "post".
  */
-function dfs(g, vs, order) {
-  if (!_.isArray(vs)) {
-    vs = [vs];
-  }
-
+export function dfs(g: Graph, vs: string[], order: 'pre' | 'post'): string[] {
   const navigation = (g.isDirected() ? g.successors : g.neighbors).bind(g);
 
   const acc = [];

diff --git a/lib/alg/dijkstra-all.js b/lib/alg/dijkstra-all.js
diff --git a/lib/alg/dijkstra-all.ts b/lib/alg/dijkstra-all.ts
@@ -0,0 +1,13 @@
+import { Graph } from '..';
+import * as _ from '../lodash';
+import { dijkstra } from './dijkstra';
+
+export function dijkstraAll(g: Graph, weightFunc?, edgeFunc?) {
+  return _.transform(
+    g.nodes(),
+    function (acc, v) {
+      acc[v] = dijkstra(g, v, weightFunc, edgeFunc);
+    },
+    {},
+  );
+}
diff --git a/lib/alg/dijkstra.js → lib/alg/dijkstra.ts b/lib/alg/dijkstra.js → lib/alg/dijkstra.ts
@@ -1,11 +1,10 @@
-const _ = require('../lodash');
+import type { Graph } from '..';
+import * as _ from '../lodash';
 const PriorityQueue = require('../data/priority-queue');
 
-module.exports = dijkstra;
-
 const DEFAULT_WEIGHT_FUNC = _.constant(1);
 
-function dijkstra(g, source, weightFn, edgeFn) {
+export function dijkstra(g: Graph, source, weightFn?, edgeFn?) {
   return runDijkstra(
     g,
     String(source),

diff --git a/lib/alg/find-cycles.js → lib/alg/find-cycles.ts b/lib/alg/find-cycles.js → lib/alg/find-cycles.ts
@@ -1,9 +1,8 @@
-const _ = require('../lodash');
-const tarjan = require('./tarjan');
+import { Graph } from '..';
+import * as _ from '../lodash';
+import { tarjan } from './tarjan';
 
-module.exports = findCycles;
-
-function findCycles(g) {
+export function findCycles(g: Graph) {
   return _.filter(tarjan(g), function (cmpt) {
     return (
       cmpt.length > 1 || (cmpt.length === 1 && g.hasEdge(cmpt[0], cmpt[0]))

diff --git a/lib/alg/floyd-warshall.js → lib/alg/floyd-warshall.ts b/lib/alg/floyd-warshall.js → lib/alg/floyd-warshall.ts
@@ -1,10 +1,9 @@
-const _ = require('../lodash');
-
-module.exports = floydWarshall;
+import { Graph } from '..';
+import * as _ from '../lodash';
 
 const DEFAULT_WEIGHT_FUNC = _.constant(1);
 
-function floydWarshall(g, weightFn, edgeFn) {
+export function floydWarshall(g: Graph, weightFn?, edgeFn?) {
   return runFloydWarshall(
     g,
     weightFn || DEFAULT_WEIGHT_FUNC,

diff --git a/lib/alg/index.js b/lib/alg/index.js
diff --git a/lib/alg/index.ts b/lib/alg/index.ts
@@ -0,0 +1,11 @@
+export { components } from './components';
+export { dijkstra } from './dijkstra';
+export { dijkstraAll } from './dijkstra-all';
+export { findCycles } from './find-cycles';
+export { floydWarshall } from './floyd-warshall';
+export { isAcyclic } from './is-acyclic';
+export { postorder } from './postorder';
+export { preorder } from './preorder';
+export { prim } from './prim';
+export { tarjan } from './tarjan';
+export { topsort, CycleException } from './topsort';
diff --git a/lib/alg/is-acyclic.js b/lib/alg/is-acyclic.js
diff --git a/lib/alg/is-acyclic.ts b/lib/alg/is-acyclic.ts
@@ -0,0 +1,14 @@
+import type { Graph } from '..';
+import { CycleException, topsort } from './topsort';
+
+export function isAcyclic(g: Graph) {
+  try {
+    topsort(g);
+  } catch (e) {
+    if (e instanceof CycleException) {
+      return false;
+    }
+    throw e;
+  }
+  return true;
+}
diff --git a/lib/alg/postorder.js b/lib/alg/postorder.js
diff --git a/lib/alg/postorder.ts b/lib/alg/postorder.ts
@@ -0,0 +1,6 @@
+import type { Graph } from '..';
+import { dfs } from './dfs';
+
+export function postorder(g: Graph, vs: string[]): string[] {
+  return dfs(g, vs, 'post');
+}
diff --git a/lib/alg/preorder.js b/lib/alg/preorder.js
diff --git a/lib/alg/preorder.ts b/lib/alg/preorder.ts
@@ -0,0 +1,6 @@
+import { Graph } from '..';
+import { dfs } from './dfs';
+
+export function preorder(g: Graph, vs: string[]) {
+  return dfs(g, vs, 'pre');
+}
diff --git a/lib/alg/prim.js → lib/alg/prim.ts b/lib/alg/prim.js → lib/alg/prim.ts
@@ -1,10 +1,8 @@
-const _ = require('../lodash');
-const Graph = require('../graph');
-const PriorityQueue = require('../data/priority-queue');
+import * as _ from '../lodash';
+import Graph from '../graph';
+import PriorityQueue from '../data/priority-queue';
 
-module.exports = prim;
-
-function prim(g, weightFunc) {
+export function prim(g: Graph, weightFunc) {
   const result = new Graph();
   const parents = {};
   const pq = new PriorityQueue();

diff --git a/lib/alg/tarjan.js → lib/alg/tarjan.ts b/lib/alg/tarjan.js → lib/alg/tarjan.ts
@@ -1,12 +1,11 @@
-const _ = require('../lodash');
+import type { Graph } from '..';
+import * as _ from '../lodash';
 
-module.exports = tarjan;
-
-function tarjan(g) {
+export function tarjan(g: Graph) {
   let index = 0;
-  const stack = [];
+  const stack: any[] = [];
   const visited = {}; // node id -> { onStack, lowlink, index }
-  const results = [];
+  const results: any[] = [];
 
   function dfs(v) {
     const entry = (visited[v] = {
@@ -26,8 +25,8 @@ function tarjan(g) {
     });
 
     if (entry.lowlink === entry.index) {
-      const cmpt = [];
-      var w;
+      const cmpt: any[] = [];
+      let w;
       do {
         w = stack.pop();
         visited[w].onStack = false;

diff --git a/lib/alg/topsort.js → lib/alg/topsort.ts b/lib/alg/topsort.js → lib/alg/topsort.ts
@@ -1,12 +1,10 @@
-const _ = require('../lodash');
+import * as _ from '../lodash';
+import type { Graph } from '..';
 
-module.exports = topsort;
-topsort.CycleException = CycleException;
-
-function topsort(g) {
+export function topsort(g: Graph): string[] {
   const visited = {};
   const stack = {};
-  const results = [];
+  const results: any[] = [];
 
   function visit(node) {
     if (_.has(stack, node)) {
@@ -31,5 +29,4 @@ function topsort(g) {
   return results;
 }
 
-function CycleException() {}
-CycleException.prototype = new Error(); // must be an instance of Error to pass testing
+export class CycleException extends Error {}
diff --git a/lib/index.ts b/lib/index.ts
@@ -1,5 +1,5 @@
 export * as json from './json';
-import alg from './alg';
+export * as alg from './alg';
 import Graph from './graph';
 
-export { Graph, alg };
+export { Graph };
diff --git a/test/alg/is-acyclic.test.ts b/test/alg/is-acyclic.test.ts
@@ -23,7 +23,7 @@ describe('alg.isAcyclic', function () {
 
   it('rethrows non-CycleException errors', function () {
     expect(function () {
-      isAcyclic(undefined);
+      isAcyclic(undefined as any);
     }).toThrow();
   });
 });
diff --git a/test/alg/postorder.test.ts b/test/alg/postorder.test.ts
@@ -7,15 +7,15 @@ describe('alg.postorder', function () {
   it('returns the root for a singleton graph', function () {
     const g = new Graph();
     g.setNode('a');
-    expect(postorder(g, 'a')).toEqual(['a']);
+    expect(postorder(g, ['a'])).toEqual(['a']);
   });
 
   it('visits each node in the graph once', function () {
     const g = new Graph();
     g.setPath(['a', 'b', 'd', 'e']);
     g.setPath(['a', 'c', 'd', 'e']);
 
-    const nodes = postorder(g, 'a');
+    const nodes = postorder(g, ['a']);
     expect(_.sortBy(nodes)).toEqual(['a', 'b', 'c', 'd', 'e']);
   });
 
@@ -25,7 +25,7 @@ describe('alg.postorder', function () {
     g.setPath(['a', 'c', 'd']);
     g.setEdge('c', 'e');
 
-    const nodes = postorder(g, 'a');
+    const nodes = postorder(g, ['a']);
     expect(_.sortBy(nodes)).toEqual(['a', 'b', 'c', 'd', 'e']);
     expect(nodes.indexOf('b')).toBeLessThan(nodes.indexOf('a'));
     expect(nodes.indexOf('c')).toBeLessThan(nodes.indexOf('a'));
@@ -63,7 +63,7 @@ describe('alg.postorder', function () {
     const g = new Graph();
     g.setNode('a');
     expect(function () {
-      postorder(g, 'b');
+      postorder(g, ['b']);
     }).toThrow();
   });
 });
diff --git a/test/alg/preorder.test.ts b/test/alg/preorder.test.ts
@@ -7,15 +7,15 @@ describe('alg.preorder', function () {
   it('returns the root for a singleton graph', function () {
     const g = new Graph();
     g.setNode('a');
-    expect(preorder(g, 'a')).toEqual(['a']);
+    expect(preorder(g, ['a'])).toEqual(['a']);
   });
 
   it('visits each node in the graph once', function () {
     const g = new Graph();
     g.setPath(['a', 'b', 'd', 'e']);
     g.setPath(['a', 'c', 'd', 'e']);
 
-    const nodes = preorder(g, 'a');
+    const nodes = preorder(g, ['a']);
     expect(_.sortBy(nodes)).toEqual(['a', 'b', 'c', 'd', 'e']);
   });
 
@@ -25,7 +25,7 @@ describe('alg.preorder', function () {
     g.setPath(['a', 'c', 'd']);
     g.setEdge('c', 'e');
 
-    const nodes = preorder(g, 'a');
+    const nodes = preorder(g, ['a']);
     expect(_.sortBy(nodes)).toEqual(['a', 'b', 'c', 'd', 'e']);
     expect(nodes.indexOf('b')).toBeGreaterThan(nodes.indexOf('a'));
     expect(nodes.indexOf('c')).toBeGreaterThan(nodes.indexOf('a'));
@@ -50,7 +50,7 @@ describe('alg.preorder', function () {
     const g = new Graph();
     g.setNode('a');
     expect(function () {
-      preorder(g, 'b');
+      preorder(g, ['b']);
     }).toThrow();
   });
 });
diff --git a/test/alg/topsort.test.ts b/test/alg/topsort.test.ts
@@ -31,7 +31,7 @@ describe('alg.topsort', function () {
     g.setPath(['b', 'c', 'a', 'b']);
     expect(function () {
       topsort(g);
-    }).toThrow(topsort.CycleException);
+    }).toThrow(alg.CycleException);
   });
 
   it('throws CycleException if there is a cycle #2', function () {
@@ -40,7 +40,7 @@ describe('alg.topsort', function () {
     g.setEdge('b', 'd');
     expect(function () {
       topsort(g);
-    }).toThrow(topsort.CycleException);
+    }).toThrow(alg.CycleException);
   });
 
   it('throws CycleException if there is a cycle #3', function () {
@@ -49,6 +49,6 @@ describe('alg.topsort', function () {
     g.setNode('d');
     expect(function () {
       topsort(g);
-    }).toThrow(topsort.CycleException);
+    }).toThrow(alg.CycleException);
   });
 });