@atlaspack/graph - npm Package Compare versions

Comparing version 3.2.1-dev.3520 to 3.2.1-dev.3565

lib/AdjacencyList.js

@@ -453,12 +453,29 @@ "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);
+      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);
+        }
+      }
+      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 to = this.#edges.to(edge);
-        if (fn(to)) {
+        let from = this.#edges.from(edge);
+        if (fn(from)) {
           return;
         }
-        edge = this.#edges.prevOut(edge);
+        edge = this.#edges.nextIn(edge);
       }
@@ -817,2 +834,3 @@ node = this.#nodes.next(node);
   /*:: @@iterator(): Iterator<TAddress> { return ({}: any); } */
+
   // $FlowFixMe[unsupported-syntax]
@@ -819,0 +837,0 @@ *[Symbol.iterator]() {

lib/Graph.js

@@ -34,3 +34,6 @@ "use strict";
     let adjacencyList = opts === null || opts === void 0 ? void 0 : opts.adjacencyList;
-    this.adjacencyList = adjacencyList ? _AdjacencyList.default.deserialize(adjacencyList) : new _AdjacencyList.default();
+    let initialCapacity = opts === null || opts === void 0 ? void 0 : opts.initialCapacity;
+    this.adjacencyList = adjacencyList ? _AdjacencyList.default.deserialize(adjacencyList) : new _AdjacencyList.default(typeof initialCapacity === 'number' ? {
+      initialCapacity
+    } : undefined);
   }
@@ -86,2 +89,13 @@ setRootNodeId(id) {
   }
+  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) {
@@ -88,0 +102,0 @@ this._assertHasNodeId(nodeId);

package.json

 {
   "name": "@atlaspack/graph",
-  "version": "3.2.1-dev.3520+8a5346e28",
+  "version": "3.2.1-dev.3565+b31bc6b33",
   "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-dev.3520+8a5346e28",
+    "@atlaspack/feature-flags": "2.12.1-dev.3565+b31bc6b33",
     "nullthrows": "^1.1.1"
   },
-  "gitHead": "8a5346e28c1bb3b9cd40f1c4e77c66dd6666f1e4"
+  "gitHead": "b31bc6b33de40c158b9f4d8ff177238be0de409d"
 }

src/AdjacencyList.js

@@ -601,12 +601,33 @@ // @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);
+      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);
+        }
+      }
+      node = this.#nodes.next(node);
+    }
+  }
+
+  forEachNodeIdConnectedTo(to: NodeId, fn: (nodeId: NodeId) => boolean | void) {
+    let node = this.#nodes.head(to);
+    while (node !== null) {
+      let edge = this.#nodes.firstIn(node);
       while (edge !== null) {
-        let to = this.#edges.to(edge);
-        if (fn(to)) {
+        let from = this.#edges.from(edge);
+        if (fn(from)) {
           return;
         }
-        edge = this.#edges.prevOut(edge);
+        edge = this.#edges.nextIn(edge);
       }
@@ -977,2 +998,3 @@ node = this.#nodes.next(node);
   /*:: @@iterator(): Iterator<TAddress> { return ({}: any); } */
+
   // $FlowFixMe[unsupported-syntax]
@@ -1091,2 +1113,3 @@ *[Symbol.iterator](): Iterator<TAddress> {
   }
+
   set nextId(nextId: NodeId) {
@@ -1093,0 +1116,0 @@ this.data[NodeTypeMap.#NEXT_ID] = fromNodeId(nextId);

src/Graph.js

@@ -20,2 +20,3 @@ // @flow strict-local
   rootNodeId?: ?NodeId,
+  initialCapacity?: number,
 |};
@@ -88,5 +89,8 @@
     let adjacencyList = opts?.adjacencyList;
+    let initialCapacity = opts?.initialCapacity;
     this.adjacencyList = adjacencyList
       ? AdjacencyList.deserialize(adjacencyList)
-      : new AdjacencyList<TEdgeType>();
+      : new AdjacencyList<TEdgeType>(
+          typeof initialCapacity === 'number' ? {initialCapacity} : undefined,
+        );
   }
@@ -164,2 +168,25 @@
 
+  forEachNodeIdConnectedTo(to: NodeId, fn: (nodeId: NodeId) => boolean | 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(
@@ -166,0 +193,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,176 @@ 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('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, d);
+      graph.addEdge(b, d);
+      graph.addEdge(c, d);
+
+      const nodeIds = [];
+      graph.forEachNodeIdConnectedTo(d, (nodeId) => {
+        nodeIds.push(nodeId);
+        return true;
+      });
+
+      assert.deepEqual(nodeIds, [a]);
+    });
+
+    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 +452,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

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

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

199394

increased by4.28%

Lines of code

5596

increased by4.75%

Dependency changes

• Updated@atlaspack/feature-flags@2.12.1-dev.3565+b31bc6b33