@atlaspack/graph - npm Package Compare versions

Comparing version 3.2.1-canary.3561 to 3.2.1-canary.3562

lib/AdjacencyList.js

@@ -453,12 +453,15 @@ "use strict";
   }
-  forEachNodeIdConnectedFromReverse(from, fn) {
+  forEachNodeIdConnectedFromReverse(from, fn, type = _Graph.ALL_EDGE_TYPES) {
+    const matches = node => type === _Graph.ALL_EDGE_TYPES || type === this.#nodes.typeOf(node);
     let node = this.#nodes.head(from);
     while (node !== null) {
-      let edge = this.#nodes.lastOut(node);
-      while (edge !== null) {
-        let to = this.#edges.to(edge);
-        if (fn(to)) {
-          return;
+      if (matches(node)) {
+        let edge = this.#nodes.lastOut(node);
+        while (edge !== null) {
+          let to = this.#edges.to(edge);
+          if (fn(to)) {
+            return;
+          }
+          edge = this.#edges.prevOut(edge);
         }
-        edge = this.#edges.prevOut(edge);
       }
@@ -468,2 +471,14 @@ node = this.#nodes.next(node);
   }
+  forEachNodeIdConnectedTo(to, fn) {
+    let node = this.#nodes.head(to);
+    while (node !== null) {
+      let edge = this.#nodes.firstIn(node);
+      while (edge !== null) {
+        let from = this.#edges.from(edge);
+        fn(from);
+        edge = this.#edges.nextIn(edge);
+      }
+      node = this.#nodes.next(node);
+    }
+  }
 
@@ -818,2 +833,3 @@ /**
   /*:: @@iterator(): Iterator<TAddress> { return ({}: any); } */
+
   // $FlowFixMe[unsupported-syntax]
@@ -820,0 +836,0 @@ *[Symbol.iterator]() {

lib/Graph.js

@@ -88,2 +88,13 @@ "use strict";
   }
+  forEachNodeIdConnectedTo(to, fn) {
+    this._assertHasNodeId(to);
+    this.adjacencyList.forEachNodeIdConnectedTo(to, fn);
+  }
+  forEachNodeIdConnectedFrom(from, fn, type = ALL_EDGE_TYPES) {
+    this._assertHasNodeId(from);
+    this.adjacencyList.forEachNodeIdConnectedFromReverse(from, id => {
+      fn(id);
+      return false;
+    }, type);
+  }
   getNodeIdsConnectedTo(nodeId, type = 1) {
@@ -90,0 +101,0 @@ this._assertHasNodeId(nodeId);

package.json

 {
   "name": "@atlaspack/graph",
-  "version": "3.2.1-canary.3561+aa779b8f6",
+  "version": "3.2.1-canary.3562+57a3c749b",
   "description": "Blazing fast, zero configuration web application bundler",
@@ -19,6 +19,6 @@ "license": "(MIT OR Apache-2.0)",
   "dependencies": {
-    "@atlaspack/feature-flags": "2.12.1-canary.3561+aa779b8f6",
+    "@atlaspack/feature-flags": "2.12.1-canary.3562+57a3c749b",
     "nullthrows": "^1.1.1"
   },
-  "gitHead": "aa779b8f6e2024cbda41ae1adb197d68a700e45a"
+  "gitHead": "57a3c749b0e920504e795fc7b2135855ccdaa242"
 }

src/AdjacencyList.js

@@ -601,12 +601,18 @@ // @flow
     fn: (nodeId: NodeId) => boolean,
+    type: AllEdgeTypes | TEdgeType | NullEdgeType = ALL_EDGE_TYPES,
   ) {
+    const matches = (node) =>
+      type === ALL_EDGE_TYPES || type === this.#nodes.typeOf(node);
+
     let node = this.#nodes.head(from);
     while (node !== null) {
-      let edge = this.#nodes.lastOut(node);
-      while (edge !== null) {
-        let to = this.#edges.to(edge);
-        if (fn(to)) {
-          return;
+      if (matches(node)) {
+        let edge = this.#nodes.lastOut(node);
+        while (edge !== null) {
+          let to = this.#edges.to(edge);
+          if (fn(to)) {
+            return;
+          }
+          edge = this.#edges.prevOut(edge);
         }
-        edge = this.#edges.prevOut(edge);
       }
@@ -617,2 +623,15 @@ node = this.#nodes.next(node);
 
+  forEachNodeIdConnectedTo(to: NodeId, fn: (nodeId: NodeId) => void) {
+    let node = this.#nodes.head(to);
+    while (node !== null) {
+      let edge = this.#nodes.firstIn(node);
+      while (edge !== null) {
+        let from = this.#edges.from(edge);
+        fn(from);
+        edge = this.#edges.nextIn(edge);
+      }
+      node = this.#nodes.next(node);
+    }
+  }
+
   /**
@@ -978,2 +997,3 @@ * Get the list of node ids connected to this node.
   /*:: @@iterator(): Iterator<TAddress> { return ({}: any); } */
+
   // $FlowFixMe[unsupported-syntax]
@@ -1092,2 +1112,3 @@ *[Symbol.iterator](): Iterator<TAddress> {
   }
+
   set nextId(nextId: NodeId) {
@@ -1094,0 +1115,0 @@ this.data[NodeTypeMap.#NEXT_ID] = fromNodeId(nextId);

src/Graph.js

@@ -166,2 +166,25 @@ // @flow strict-local
 
+  forEachNodeIdConnectedTo(to: NodeId, fn: (nodeId: NodeId) => void) {
+    this._assertHasNodeId(to);
+
+    this.adjacencyList.forEachNodeIdConnectedTo(to, fn);
+  }
+
+  forEachNodeIdConnectedFrom(
+    from: NodeId,
+    fn: (nodeId: NodeId) => void,
+    type: AllEdgeTypes | TEdgeType | NullEdgeType = ALL_EDGE_TYPES,
+  ) {
+    this._assertHasNodeId(from);
+
+    this.adjacencyList.forEachNodeIdConnectedFromReverse(
+      from,
+      (id) => {
+        fn(id);
+        return false;
+      },
+      type,
+    );
+  }
+
   getNodeIdsConnectedTo(
@@ -168,0 +191,0 @@ nodeId: NodeId,

test/AdjacencyList.test.js

 // @flow strict-local
 
 import assert from 'assert';
+import sinon from 'sinon';
 import path from 'path';
@@ -275,2 +276,156 @@ import {Worker} from 'worker_threads';
 
+  describe('forEachNodeIdConnectedTo', () => {
+    it('iterates no edges if there are none', () => {
+      const graph = new AdjacencyList();
+      const a = graph.addNode();
+      const b = graph.addNode();
+      const c = graph.addNode();
+
+      graph.addEdge(a, b);
+      graph.addEdge(c, b);
+
+      const callback = sinon.spy(() => {});
+      graph.forEachNodeIdConnectedTo(c, callback);
+
+      assert.equal(callback.callCount, 0);
+    });
+
+    it('iterates incoming edges to a node', () => {
+      const graph = new AdjacencyList();
+      const a = graph.addNode();
+      const b = graph.addNode();
+      const c = graph.addNode();
+
+      graph.addEdge(a, b);
+      graph.addEdge(c, b);
+
+      const nodeIds = [];
+      graph.forEachNodeIdConnectedTo(b, (id) => {
+        nodeIds.push(id);
+      });
+
+      assert.deepEqual(nodeIds, [a, c]);
+    });
+
+    it('terminates if the graph is cyclic', () => {
+      const graph = new AdjacencyList();
+      const a = graph.addNode();
+      const b = graph.addNode();
+      const c = graph.addNode();
+
+      graph.addEdge(a, b);
+      graph.addEdge(c, b);
+      graph.addEdge(b, b);
+
+      const nodeIds = [];
+      graph.forEachNodeIdConnectedTo(b, (id) => {
+        nodeIds.push(id);
+      });
+
+      assert.deepEqual(nodeIds, [a, c, b]);
+    });
+  });
+
+  describe('forEachNodeIdConnectedFromReverse', () => {
+    it('iterates no edges if there are none', () => {
+      const graph = new AdjacencyList();
+      const a = graph.addNode();
+      const b = graph.addNode();
+      const c = graph.addNode();
+
+      graph.addEdge(a, b);
+      graph.addEdge(b, c);
+
+      const callback = sinon.spy(() => false);
+      graph.forEachNodeIdConnectedFromReverse(c, callback);
+
+      assert.equal(callback.callCount, 0);
+    });
+
+    it('iterates outgoing edges from a node', () => {
+      const graph = new AdjacencyList();
+      const a = graph.addNode();
+      const b = graph.addNode();
+      const c = graph.addNode();
+      const d = graph.addNode();
+      const e = graph.addNode();
+
+      graph.addEdge(a, b, 1);
+      graph.addEdge(a, c, 2);
+      graph.addEdge(b, d, 3);
+      graph.addEdge(c, e, 4);
+
+      const nodeIds = [];
+      graph.forEachNodeIdConnectedFromReverse(a, (nodeId) => {
+        nodeIds.push(nodeId);
+        return false;
+      });
+
+      assert.deepEqual(nodeIds, [b, c]);
+    });
+
+    it('terminates if the graph is cyclic', () => {
+      const graph = new AdjacencyList();
+      const a = graph.addNode();
+      const b = graph.addNode();
+      const c = graph.addNode();
+
+      graph.addEdge(a, b);
+      graph.addEdge(a, c);
+      graph.addEdge(a, a);
+
+      const nodeIds = [];
+      graph.forEachNodeIdConnectedFromReverse(a, (nodeId) => {
+        nodeIds.push(nodeId);
+        return false;
+      });
+
+      assert.deepEqual(nodeIds, [a, c, b]);
+    });
+
+    it('stops traversal if the return value is true', () => {
+      const graph = new AdjacencyList();
+      const a = graph.addNode();
+      const b = graph.addNode();
+      const c = graph.addNode();
+      const d = graph.addNode();
+
+      graph.addEdge(a, b);
+      graph.addEdge(a, c);
+      graph.addEdge(a, d);
+
+      const nodeIds = [];
+      graph.forEachNodeIdConnectedFromReverse(a, (nodeId) => {
+        nodeIds.push(nodeId);
+        return true;
+      });
+
+      assert.deepEqual(nodeIds, [d]);
+    });
+
+    it('filters edges by type', () => {
+      const graph = new AdjacencyList();
+      const a = graph.addNode();
+      const b = graph.addNode();
+      const c = graph.addNode();
+      const d = graph.addNode();
+
+      graph.addEdge(a, b, 2);
+      graph.addEdge(a, c, 2);
+      graph.addEdge(a, d);
+
+      const nodeIds = [];
+      graph.forEachNodeIdConnectedFromReverse(
+        a,
+        (nodeId) => {
+          nodeIds.push(nodeId);
+          return false;
+        },
+        2,
+      );
+
+      assert.deepEqual(nodeIds, [c, b]);
+    });
+  });
+
   describe('deserialize', function () {
@@ -277,0 +432,0 @@ this.timeout(10000);

test/Graph.test.js

@@ -559,2 +559,50 @@ // @flow strict-local
   });
+
+  describe('forEachNodeConnectedTo', () => {
+    it('calls the callback for each node connected to the given node', () => {
+      const graph = new Graph();
+      const a = graph.addNode('0');
+      const b = graph.addNode('1');
+      const c = graph.addNode('2');
+      const d = graph.addNode('3');
+      graph.addNode('disconnected-1');
+      graph.addNode('disconnected-2');
+      graph.addEdge(a, b);
+      graph.addEdge(b, c);
+      graph.addEdge(b, d);
+      graph.addEdge(a, c);
+      graph.addEdge(c, d);
+
+      const order = [];
+      graph.forEachNodeIdConnectedTo(d, (node) => {
+        order.push(node);
+      });
+
+      assert.deepEqual(order, [b, c]);
+    });
+  });
+
+  describe('forEachNodeConnectedFrom', () => {
+    it('calls the callback for each node connected from the given node', () => {
+      const graph = new Graph();
+      const a = graph.addNode('0');
+      const b = graph.addNode('1');
+      const c = graph.addNode('2');
+      const d = graph.addNode('3');
+      graph.addNode('disconnected-1');
+      graph.addNode('disconnected-2');
+      graph.addEdge(a, b);
+      graph.addEdge(b, c);
+      graph.addEdge(b, d);
+      graph.addEdge(a, c);
+      graph.addEdge(c, d);
+
+      const order = [];
+      graph.forEachNodeIdConnectedFrom(a, (node) => {
+        order.push(node);
+      });
+
+      assert.deepEqual(order, [c, b]);
+    });
+  });
 });

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

Manifest confusion

Supply chain risk

This package has inconsistent metadata. This could be malicious or caused by an error when publishing the package.

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

Manifest confusion

Supply chain risk

This package has inconsistent metadata. This could be malicious or caused by an error when publishing the package.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

198805

increased by3.79%

Lines of code

5576

increased by4.24%

Dependency changes

• Updated@atlaspack/feature-flags@2.12.1-canary.3562+57a3c749b