graphology-traversal - npm Package Compare versions

Comparing version 0.2.2 to 0.3.0

bfs.d.ts

 import Graph, {Attributes} from 'graphology-types';
-import {TraversalCallback} from './types';
+import {TraversalCallback, TraversalOptions} from './types';
 
-export function bfs<N extends Attributes = Attributes>(graph: Graph<N>, callback: TraversalCallback<N>): void;
-export function bfsFromNode<N extends Attributes = Attributes>(graph: Graph<N>, node: unknown, callback: TraversalCallback<N>): void;
+export function bfs<N extends Attributes = Attributes>(
+  graph: Graph<N>,
+  callback: TraversalCallback<N>,
+  options?: TraversalOptions
+): void;
+export function bfsFromNode<N extends Attributes = Attributes>(
+  graph: Graph<N>,
+  node: unknown,
+  callback: TraversalCallback<N>,
+  options?: TraversalOptions
+): void;

bfs.js

@@ -8,48 +8,72 @@ /**
 var isGraph = require('graphology-utils/is-graph');
-var FixedDeque = require('mnemonist/fixed-deque');
-var TraversalRecord = require('./utils').TraversalRecord;
+var BFSQueue = require('graphology-indices/bfs-queue');
+var utils = require('./utils');
 
+var TraversalRecord = utils.TraversalRecord;
+var capitalize = utils.capitalize;
+
 /**
  * BFS traversal in the given graph using a callback function
  *
- * @param {Graph}    graph    - Target graph.
- * @param {function} callback - Iteration callback.
+ * @param {Graph}    graph        - Target graph.
+ * @param {string}   startingNode - Optional Starting node.
+ * @param {function} callback     - Iteration callback.
+ * @param {object}   options      - Options:
+ * @param {string}     mode         - Traversal mode.
  */
-function bfs(graph, callback) {
+function abstractBfs(graph, startingNode, callback, options) {
+  options = options || {};
+
   if (!isGraph(graph))
-    throw new Error('graphology-traversal/bfs: expecting a graphology instance.');
+    throw new Error(
+      'graphology-traversal/bfs: expecting a graphology instance.'
+    );
 
   if (typeof callback !== 'function')
-    throw new Error('graphology-traversal/bfs: given callback is not a function.');
+    throw new Error(
+      'graphology-traversal/bfs: given callback is not a function.'
+    );
 
   // Early termination
-  if (graph.order === 0)
-    return;
+  if (graph.order === 0) return;
 
-  var seen = new Set();
-  var queue = new FixedDeque(Array, graph.order);
-  var record, depth;
+  var forEachNeighbor =
+    graph['forEach' + capitalize(options.mode || 'outbound') + 'Neighbor'].bind(
+      graph
+    );
 
-  function neighborCallback(neighbor, attr) {
-    if (seen.has(neighbor))
-      return;
+  var forEachNode;
 
-    seen.add(neighbor);
-    queue.push(new TraversalRecord(neighbor, attr, depth + 1));
+  if (startingNode === null) {
+    forEachNode = graph.forEachNode.bind(graph);
+  } else {
+    forEachNode = function (fn) {
+      startingNode = '' + startingNode;
+      fn(startingNode, graph.getNodeAttributes(startingNode));
+    };
   }
 
-  graph.forEachNode(function(node, attr) {
-    if (seen.has(node))
-      return;
+  var queue = new BFSQueue(graph.order);
+  var record, stop;
 
-    seen.add(node);
-    queue.push(new TraversalRecord(node, attr, 0));
+  function visit(neighbor, attr) {
+    queue.pushWith(
+      neighbor,
+      new TraversalRecord(neighbor, attr, record.depth + 1)
+    );
+  }
 
+  forEachNode(function (node, attr) {
+    if (queue.has(node)) return;
+
+    queue.pushWith(node, new TraversalRecord(node, attr, 0));
+
     while (queue.size !== 0) {
       record = queue.shift();
-      depth = record.depth;
 
-      callback(record.node, record.attributes, depth);
+      stop = callback(record.node, record.attributes, record.depth);
 
-      graph.forEachOutboundNeighbor(record.node, neighborCallback);
+      if (stop === true) continue;
+
+      forEachNeighbor(record.node, visit);
     }
@@ -59,49 +83,5 @@ });
 
-/**
- * BFS traversal in the given graph, starting from the given node, using a
- * callback function.
- *
- * @param {Graph}    graph    - Target graph.
- * @param {string}   node     - Starting node.
- * @param {function} callback - Iteration callback.
- */
-function bfsFromNode(graph, node, callback) {
-  if (!isGraph(graph))
-    throw new Error('graphology-traversal/dfs: expecting a graphology instance.');
-
-  if (typeof callback !== 'function')
-    throw new Error('graphology-traversal/dfs: given callback is not a function.');
-
-  // Early termination
-  if (graph.order === 0)
-    return;
-
-  node = '' + node;
-
-  var seen = new Set();
-  var queue = new FixedDeque(Array, graph.order);
-  var depth, record;
-
-  function neighborCallback(neighbor, attr) {
-    if (seen.has(neighbor))
-      return;
-
-    seen.add(neighbor);
-    queue.push(new TraversalRecord(neighbor, attr, depth + 1));
-  }
-
-  seen.add(node);
-  queue.push(new TraversalRecord(node, graph.getNodeAttributes(node), 0));
-
-  while (queue.size !== 0) {
-    record = queue.shift();
-    depth = record.depth;
-
-    callback(record.node, record.attributes, depth);
-
-    graph.forEachOutboundNeighbor(record.node, neighborCallback);
-  }
-}
-
-exports.bfs = bfs;
-exports.bfsFromNode = bfsFromNode;
+exports.bfs = function (graph, callback, options) {
+  return abstractBfs(graph, null, callback, options);
+};
+exports.bfsFromNode = abstractBfs;

dfs.d.ts

 import Graph, {Attributes} from 'graphology-types';
-import {TraversalCallback} from './types';
+import {TraversalCallback, TraversalOptions} from './types';
 
-export function dfs<N extends Attributes = Attributes>(graph: Graph<N>, callback: TraversalCallback<N>): void;
-export function dfsFromNode<N extends Attributes = Attributes>(graph: Graph<N>, node: unknown, callback: TraversalCallback<N>): void;
+export function dfs<N extends Attributes = Attributes>(
+  graph: Graph<N>,
+  callback: TraversalCallback<N>,
+  options?: TraversalOptions
+): void;
+export function dfsFromNode<N extends Attributes = Attributes>(
+  graph: Graph<N>,
+  node: unknown,
+  callback: TraversalCallback<N>,
+  options?: TraversalOptions
+): void;

dfs.js

@@ -8,47 +8,72 @@ /**
 var isGraph = require('graphology-utils/is-graph');
-var TraversalRecord = require('./utils').TraversalRecord;
+var DFSStack = require('graphology-indices/dfs-stack');
+var utils = require('./utils');
 
+var TraversalRecord = utils.TraversalRecord;
+var capitalize = utils.capitalize;
+
 /**
  * DFS traversal in the given graph using a callback function
  *
- * @param {Graph}    graph    - Target graph.
- * @param {function} callback - Iteration callback.
+ * @param {Graph}    graph        - Target graph.
+ * @param {string}   startingNode - Optional Starting node.
+ * @param {function} callback     - Iteration callback.
+ * @param {object}   options      - Options:
+ * @param {string}     mode         - Traversal mode.
  */
-function dfs(graph, callback) {
+function abstractDfs(graph, startingNode, callback, options) {
+  options = options || {};
+
   if (!isGraph(graph))
-    throw new Error('graphology-traversal/dfs: expecting a graphology instance.');
+    throw new Error(
+      'graphology-traversal/dfs: expecting a graphology instance.'
+    );
 
   if (typeof callback !== 'function')
-    throw new Error('graphology-traversal/dfs: given callback is not a function.');
+    throw new Error(
+      'graphology-traversal/dfs: given callback is not a function.'
+    );
 
   // Early termination
-  if (graph.order === 0)
-    return;
+  if (graph.order === 0) return;
 
-  var seen = new Set();
-  var stack = [];
-  var depth, record;
+  var forEachNeighbor =
+    graph['forEach' + capitalize(options.mode || 'outbound') + 'Neighbor'].bind(
+      graph
+    );
 
-  function neighborCallback(neighbor, attr) {
-    if (seen.has(neighbor))
-      return;
+  var forEachNode;
 
-    seen.add(neighbor);
-    stack.push(new TraversalRecord(neighbor, attr, depth + 1));
+  if (startingNode === null) {
+    forEachNode = graph.forEachNode.bind(graph);
+  } else {
+    forEachNode = function (fn) {
+      startingNode = '' + startingNode;
+      fn(startingNode, graph.getNodeAttributes(startingNode));
+    };
   }
 
-  graph.forEachNode(function(node, attr) {
-    if (seen.has(node))
-      return;
+  var stack = new DFSStack(graph.order);
+  var record, stop;
 
-    seen.add(node);
-    stack.push(new TraversalRecord(node, attr, 0));
+  function visit(neighbor, attr) {
+    stack.pushWith(
+      neighbor,
+      new TraversalRecord(neighbor, attr, record.depth + 1)
+    );
+  }
 
-    while (stack.length !== 0) {
+  forEachNode(function (node, attr) {
+    if (stack.has(node)) return;
+
+    stack.pushWith(node, new TraversalRecord(node, attr, 0));
+
+    while (stack.size !== 0) {
       record = stack.pop();
-      depth = record.depth;
 
-      callback(record.node, record.attributes, depth);
+      stop = callback(record.node, record.attributes, record.depth);
 
-      graph.forEachOutboundNeighbor(record.node, neighborCallback);
+      if (stop === true) continue;
+
+      forEachNeighbor(record.node, visit);
     }
@@ -58,49 +83,5 @@ });
 
-/**
- * DFS traversal in the given graph, starting from the given node, using a
- * callback function.
- *
- * @param {Graph}    graph    - Target graph.
- * @param {string}   node     - Starting node.
- * @param {function} callback - Iteration callback.
- */
-function dfsFromNode(graph, node, callback) {
-  if (!isGraph(graph))
-    throw new Error('graphology-traversal/dfs: expecting a graphology instance.');
-
-  if (typeof callback !== 'function')
-    throw new Error('graphology-traversal/dfs: given callback is not a function.');
-
-  // Early termination
-  if (graph.order === 0)
-    return;
-
-  node = '' + node;
-
-  var seen = new Set();
-  var stack = [];
-  var depth, record;
-
-  function neighborCallback(neighbor, attr) {
-    if (seen.has(neighbor))
-      return;
-
-    seen.add(neighbor);
-    stack.push(new TraversalRecord(neighbor, attr, depth + 1));
-  }
-
-  seen.add(node);
-  stack.push(new TraversalRecord(node, graph.getNodeAttributes(node), 0));
-
-  while (stack.length !== 0) {
-    record = stack.pop();
-    depth = record.depth;
-
-    callback(record.node, record.attributes, depth);
-
-    graph.forEachOutboundNeighbor(record.node, neighborCallback);
-  }
-}
-
-exports.dfs = dfs;
-exports.dfsFromNode = dfsFromNode;
+exports.dfs = function (graph, callback, options) {
+  return abstractDfs(graph, null, callback, options);
+};
+exports.dfsFromNode = abstractDfs;

index.js

 var bfsModule = require('./bfs.js');
 var dfsModule = require('./dfs.js');
 
-var k;
-
-for (k in bfsModule)
-  exports[k] = bfsModule[k];
-
-for (k in dfsModule)
-  exports[k] = dfsModule[k];
+exports.bfs = bfsModule.bfs;
+exports.bfsFromNode = bfsModule.bfsFromNode;
+exports.dfs = dfsModule.dfs;
+exports.dfsFromNode = dfsModule.dfsFromNode;

package.json

 {
   "name": "graphology-traversal",
-  "version": "0.2.2",
+  "version": "0.3.0",
   "description": "Traversal functions for graphology.",
@@ -15,4 +15,3 @@ "main": "index.js",
   "scripts": {
-    "lint": "eslint '**/*.js'",
-    "prepublishOnly": "npm run lint && npm test",
+    "prepublishOnly": "npm test",
     "test": "mocha test.js"
@@ -22,3 +21,3 @@ },
     "type": "git",
-    "url": "git+https://github.com/graphology/graphology-traversal.git"
+    "url": "git+https://github.com/graphology/graphology.git"
   },
@@ -40,8 +39,5 @@ "keywords": [
   "bugs": {
-    "url": "https://github.com/graphology/graphology-traversal/issues"
+    "url": "https://github.com/graphology/graphology/issues"
   },
-  "homepage": "https://github.com/graphology/graphology-traversal#readme",
-  "eslintConfig": {
-    "extends": "@yomguithereal/eslint-config"
-  },
+  "homepage": "https://github.com/graphology/graphology#readme",
   "peerDependencies": {
@@ -51,5 +47,5 @@ "graphology-types": ">=0.20.0"
   "dependencies": {
-    "graphology-utils": "^2.0.0",
-    "mnemonist": "^0.38.3"
+    "graphology-indices": "^0.16.4",
+    "graphology-utils": "^2.0.0"
   }
 }

README.md

@@ -1,3 +0,1 @@
-[![Build Status](https://travis-ci.org/graphology/graphology-traversal.svg)](https://travis-ci.org/graphology/graphology-traversal)
-
 # Graphology Traversal
@@ -15,6 +13,6 @@
 
-* [bfs](#bfs)
-* [bfsFromNode](#bfsfromnode)
-* [dfs](#dfs)
-* [dfsFromNode](#bfsfromnode)
+- [bfs](#bfs)
+- [bfsFromNode](#bfsfromnode)
+- [dfs](#dfs)
+- [dfsFromNode](#bfsfromnode)
 
@@ -30,11 +28,18 @@ ### bfs
 
-bfs(graph, function(node, attr, depth) {
+bfs(graph, function (node, attr, depth) {
   console.log(node, attr, depth);
 });
+
+// Stopping at depth 3
+bfs(graph, function (node, attr, depth) {
+  return depth >= 3;
+});
 ```
 
-*Arguments*
+_Arguments_
 
-* **graph** *Graph*: a graphology instance.
-* **callback** *function*: iteration callback taking the traversed node, its attributes and the traversal's depth.
+- **graph** _Graph_: a graphology instance.
+- **callback** _function_: iteration callback taking the traversed node, its attributes and the traversal's depth. Returning `true` will prevent the traversal from following the next neighbors.
+- **options** _?object_: traversal options:
+  - **mode** _?string_ [`outbound`]: type of neighbors to traverse.
 
@@ -50,12 +55,19 @@ ### bfsFromNode
 
-bfsFromNode(graph, 'node1', function(node, attr, depth) {
+bfsFromNode(graph, 'node1', function (node, attr, depth) {
   console.log(node, attr, depth);
 });
+
+// Stopping at depth 3
+bfsFromNode(graph, function (node, attr, depth) {
+  return depth >= 3;
+});
 ```
 
-*Arguments*
+_Arguments_
 
-* **graph** *Graph*: a graphology instance.
-* **node** *string|number*: starting node.
-* **callback** *function*: iteration callback taking the traversed node, its attributes and the traversal's depth.
+- **graph** _Graph_: a graphology instance.
+- **node** _string\|number_: starting node.
+- **callback** _function_: iteration callback taking the traversed node, its attributes and the traversal's depth. Returning `true` will prevent the traversal from following the next neighbors.
+- **options** _?object_: traversal options:
+  - **mode** _?string_ [`outbound`]: type of neighbors to traverse.
 
@@ -71,11 +83,18 @@ ### dfs
 
-dfs(graph, function(node, attr, depth) {
+dfs(graph, function (node, attr, depth) {
   console.log(node, attr, depth);
 });
+
+// Stopping at depth 3
+dfs(graph, function (node, attr, depth) {
+  return depth >= 3;
+});
 ```
 
-*Arguments*
+_Arguments_
 
-* **graph** *Graph*: a graphology instance.
-* **callback** *function*: iteration callback taking the traversed node, its attributes and the traversal's depth.
+- **graph** _Graph_: a graphology instance.
+- **callback** _function_: iteration callback taking the traversed node, its attributes and the traversal's depth. Returning `true` will prevent the traversal from following the next neighbors.
+- **options** _?object_: traversal options:
+  - **mode** _?string_ [`outbound`]: type of neighbors to traverse.
 
@@ -91,11 +110,18 @@ ### dfsFromNode
 
-dfsFromNode(graph, 'node1', function(node, attr, depth) {
+dfsFromNode(graph, 'node1', function (node, attr, depth) {
   console.log(node, attr, depth);
 });
+
+// Stopping at depth 3
+dfsFromNode(graph, function (node, attr, depth) {
+  return depth >= 3;
+});
 ```
 
-*Arguments*
+_Arguments_
 
-* **graph** *Graph*: a graphology instance.
-* **node** *string|number*: starting node.
-* **callback** *function*: iteration callback taking the traversed node, its attributes and the traversal's depth.
+- **graph** _Graph_: a graphology instance.
+- **node** _string\|number_: starting node.
+- **callback** _function_: iteration callback taking the traversed node, its attributes and the traversal's depth. Returning `true` will prevent the traversal from following the next neighbors.
+- **options** _?object_: traversal options:
+  - **mode** _?string_ [`outbound`]: type of neighbors to traverse.

types.d.ts

 import {Attributes} from 'graphology-types';
 
-export type TraversalCallback<N extends Attributes = Attributes> = (key: string, attributes: N, depth: number) => void;
+export type TraversalCallback<NodeAttributes extends Attributes = Attributes> =
+  (key: string, attributes: NodeAttributes, depth: number) => boolean | void;
+
+export type TraversalMode =
+  | 'in'
+  | 'out'
+  | 'directed'
+  | 'undirected'
+  | 'inbound'
+  | 'outbound';
+
+export type TraversalOptions = {
+  mode?: TraversalMode;
+};

utils.js

@@ -14,2 +14,7 @@ /**
 
+function capitalize(string) {
+  return string[0].toUpperCase() + string.slice(1);
+}
+
 exports.TraversalRecord = TraversalRecord;
+exports.capitalize = capitalize;

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

No bug tracker

Maintenance

Package does not have a linked bug tracker in package.json.

Found 1 instance in 1 package

No website

Quality

Package does not have a website.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

11924

increased by4.58%

Lines of code

199

increased by2.58%

Number of low maintenance alerts

0

decreased by-100%

Number of low quality alerts

1

decreased by-50%

Number of lines in readme file

123

increased by26.8%

Worsened metrics

Number of medium supply chain risk alerts

1

increased byInfinity%

Dependency changes

• + Addedgraphology-indices@^0.16.4

• + Addedgraphology-indices@0.16.6(transitive)

• + Addedmnemonist@0.39.8(transitive)

• - Removedmnemonist@^0.38.3

• - Removedmnemonist@0.38.5(transitive)