@antv/graphlib - npm Package Compare versions

Comparing version 2.0.0-alpha.2 to 2.0.0-alpha.3

__tests__/graph.spec.ts

@@ -12,3 +12,3 @@ import { Graph } from '../src/index';
   it('creates a Graph with options', () => {
-    const nodes = [
+    const nodes =[
       { id: 'Node1', data: {} },
@@ -254,2 +254,10 @@ { id: 'Node2', data: {} },
   expect(nodeIdList).toEqual([0, 1, 2, 3]);
+
+  // Abort on 1.
+  nodeIdList.length = 0;
+  graph.bfs(0, (node) => {
+    nodeIdList.push(node.id);
+    if (node.id === 1) return true;
+  });
+  expect(nodeIdList).toEqual([0, 1]);
 });
@@ -278,2 +286,10 @@
   expect(nodeIdList).toEqual([0, 1, 3, 2]);
+
+  // Abort on 1.
+  nodeIdList.length = 0;
+  graph.dfs(0, (node) => {
+    nodeIdList.push(node.id);
+    if (node.id === 1) return true;
+  });
+  expect(nodeIdList).toEqual([0, 1]);
 });
@@ -280,0 +296,0 @@

__tests__/tree.spec.ts

 import { Graph } from '../src';
 
-test('Tree related methods', () => {
-  /*
-        1    4
-       / \   |
-      2   3  5
-  */
+const initTreeGraph = () => {
+  //    1    4
+  //   / \   |
+  //  2   3  5
   const node2 = {
-    id: 'Node2',
+    id: 2,
     data: {},
   };
   const node3 = {
-    id: 'Node3',
+    id: 3,
     data: {},
   };
   const node1 = {
-    id: 'Node1',
+    id: 1,
     data: {},
@@ -23,46 +21,106 @@ children: [node2, node3],
   const node5 = {
-    id: 'Node5',
+    id: 5,
     data: {},
   };
   const node4 = {
-    id: 'Node4',
+    id: 4,
     data: {},
     children: [node5],
   };
-  const graph = new Graph({
+  return new Graph({
     tree: [node1, node4],
   });
-  expect(graph.getAllNodes()).toEqual([node1, node4, node2, node3, node5]);
-  expect(graph.getRoots()).toEqual([node1, node4]);
-  expect(graph.getParent('Node2')).toEqual(node1);
-  expect(graph.getParent('Node4')).toEqual(null);
-  expect(graph.getChildren('Node1')).toEqual([node2, node3]);
-  expect(graph.getChildren('Node2')).toEqual([]);
+};
 
-  // Attach another tree structure
-  expect(() => {
-    graph.getParent('Node2', 'TreeKey');
-  }).toThrow('Tree structure not found');
-  graph.attachTreeStructure('TreeKey');
-  expect(graph.getParent('Node2', 'TreeKey')).toEqual(null);
+describe('Tree related methods', () => {
+  test('Basic getter methods', () => {
+    const graph = initTreeGraph();
+    expect(graph.getAllNodes().map((n) => n.id)).toEqual([1, 4, 2, 3, 5]);
+    expect(graph.getRoots().map((n) => n.id)).toEqual([1, 4]);
+    expect(graph.getParent(2)?.id).toEqual(1);
+    expect(graph.getParent(4)).toEqual(null);
+    expect(graph.getChildren(1).map((n) => n.id)).toEqual([2, 3]);
+    expect(graph.getChildren(2).map((n) => n.id)).toEqual([]);
 
-  // Update parent
-  graph.setParent('Node2', 'Node4', 'TreeKey');
-  expect(graph.getParent('Node2', 'TreeKey')).toEqual(node4);
-  expect(graph.getChildren('Node4', 'TreeKey')).toEqual([node2]);
-  expect(graph.getParent('Node2')).toEqual(node1);
+    //    1
+    //   / \
+    //  2   3
+    //  |
+    //  4
+    //  |
+    //  5
+    graph.setParent(4, 2);
+    expect(graph.getAncestors(5).map(n => n.id)).toEqual([4, 2, 1]);
+  });
 
-  // Detach tree structure
-  graph.detachTreeStructure('TreeKey');
-  expect(() => {
-    graph.getParent('Node2', 'TreeKey');
-  }).toThrow('Tree structure not found');
+  test('Attaching and detaching tree structures', () => {
+    const graph = initTreeGraph();
+    expect(() => {
+      graph.getParent(2, 'TreeKey');
+    }).toThrow('Tree structure not found');
+    graph.attachTreeStructure('TreeKey');
+    expect(graph.getParent(2, 'TreeKey')).toEqual(null);
 
-  // Removing nodes
-  graph.removeNode('Node1');
-  expect(graph.getRoots()).toEqual([node4, node2, node3]);
-  expect(graph.getParent('Node2')).toEqual(null);
-  expect(() => {
-    graph.getChildren('Node1');
-  }).toThrow('Node not found');
+    graph.detachTreeStructure('TreeKey');
+    expect(() => {
+      graph.getParent(2, 'TreeKey');
+    }).toThrow('Tree structure not found');
+  });
+
+  test('Updating parent', () => {
+    const graph = initTreeGraph();
+    graph.setParent(2, 4);
+    expect(graph.getParent(2)?.id).toEqual(4);
+    expect(graph.getChildren(4).map((n) => n.id)).toEqual([5, 2]);
+    expect(graph.getChildren(1).map((n) => n.id)).toEqual([3]);
+  });
+
+  test('Removing nodes', () => {
+    const graph = initTreeGraph();
+    graph.removeNode(1);
+    expect(graph.getRoots().map((n) => n.id)).toEqual([4, 2, 3]);
+    expect(graph.getParent(2)).toEqual(null);
+    expect(() => {
+      graph.getChildren(1);
+    }).toThrow('Node not found');
+  });
+
+  test('Traversing', () => {
+    const graph = initTreeGraph();
+    graph.setParent(4, 2);
+    graph.setParent(5, 2);
+    //     1
+    //    / \
+    //   2   3
+    //  / \
+    // 4   5
+
+    const ids: number[] = [];
+
+    // dfs
+    graph.dfsTree(1, n => {
+      ids.push(Number(n.id));
+    });
+    expect(ids).toEqual([1, 2, 4, 5, 3]);
+    // dfs + abort
+    ids.length = 0;
+    graph.dfsTree(1, n => {
+      ids.push(Number(n.id));
+      if (n.id === 4) return true;
+    });
+    expect(ids).toEqual([1, 2, 4]);
+    // bfs
+    ids.length = 0;
+    graph.bfsTree(1, n => {
+      ids.push(Number(n.id));
+    });
+    expect(ids).toEqual([1, 2, 3, 4, 5]);
+    // bfs + abort
+    ids.length = 0;
+    graph.bfsTree(1, n => {
+      ids.push(Number(n.id));
+      if (n.id === 3) return true;
+    });
+    expect(ids).toEqual([1, 2, 3]);
+  });
 });

dist/index.umd.min.js

@@ -1,1 +0,1 @@
-!function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports):"function"==typeof define&&define.amd?define(["exports"],t):t((e="undefined"!=typeof globalThis?globalThis:e||self).GraphLib={})}(this,function(e){"use strict";e.Graph=class d{nodeMap=new Map;edgeMap=new Map;inEdgesMap=new Map;outEdgesMap=new Map;treeIndices=new Map;changes=[];batchCount=0;onChanged=()=>{};constructor(e){e&&(e.nodes&&this.addNodes(e.nodes),e.edges&&this.addEdges(e.edges),e.tree&&this.addTree(e.tree),e.onChanged)&&(this.onChanged=e.onChanged)}batch=e=>{this.batchCount+=1,e(),--this.batchCount,this.batchCount||this.commit()};commit(){var e=this.changes;this.changes=[],this.onChanged({graph:this,changes:e})}reduceChanges(e){let t=[];return e.forEach(a=>{switch(a.type){case"NodeRemoved":{let d=!1;t=t.filter(e=>{var t;return"NodeAdded"===e.type?((t=e.value.id===a.value.id)&&(d=!0),!t):"NodeDataUpdated"===e.type?e.id!==a.value.id:"TreeStructureChanged"!==e.type||e.nodeId!==a.value.id}),d||t.push(a);break}case"EdgeRemoved":{let d=!1;t=t.filter(e=>{var t;return"EdgeAdded"===e.type?((t=e.value.id===a.value.id)&&(d=!0),!t):"EdgeDataUpdated"!==e.type&&"EdgeUpdated"!==e.type||e.id!==a.value.id}),d||t.push(a);break}case"NodeDataUpdated":case"EdgeDataUpdated":case"EdgeUpdated":var e=t.find(e=>e.type===a.type&&e.id===a.id&&e.propertyName===a.propertyName);e?e.newValue=a.newValue:t.push(a);break;case"TreeStructureDetached":(t=t.filter(e=>"TreeStructureAttached"!==e.type&&"TreeStructureChanged"!==e.type||e.treeKey!==a.treeKey)).push(a);break;case"TreeStructureChanged":(e=t.find(e=>"TreeStructureChanged"===e.type&&e.treeKey===a.treeKey&&e.nodeId===a.nodeId))?e.newParentId=a.newParentId:t.push(a);break;default:t.push(a)}}),t}checkNodeExistence(e){if(!this.hasNode(e))throw new Error("Node not found for id: "+e)}hasNode(e){return this.nodeMap.has(e)}areNeighbors(t,e){return this.checkNodeExistence(t),this.getNeighbors(e).some(e=>e.id===t)}getNode(e){return this.checkNodeExistence(e),this.nodeMap.get(e)}getRelatedEdges(e,t){this.checkNodeExistence(e);var d=this.inEdgesMap.get(e),e=this.outEdgesMap.get(e);return"in"===t?Array.from(d):"out"===t?Array.from(e):(t=new Set([...d,...e]),Array.from(t))}getDegree(e,t){return this.getRelatedEdges(e,t).length}getSuccessors(e){return e=this.getRelatedEdges(e,"out").map(e=>e.target),Array.from(new Set(e)).map(e=>this.getNode(e))}getPredecessors(e){return e=this.getRelatedEdges(e,"in").map(e=>e.source),Array.from(new Set(e)).map(e=>this.getNode(e))}getNeighbors(e){var t=this.getPredecessors(e),e=this.getSuccessors(e);return Array.from(new Set([...t,...e]))}doAddNode(t){if(this.hasNode(t.id))throw new Error("Node already exists: "+t.id);this.nodeMap.set(t.id,t),this.inEdgesMap.set(t.id,new Set),this.outEdgesMap.set(t.id,new Set),this.treeIndices.forEach(e=>{e.childrenMap.set(t.id,new Set)}),this.changes.push({type:"NodeAdded",value:t})}addNodes(t){this.batch(()=>{for(const e of t)this.doAddNode(e)})}addNode(e){this.addNodes([e])}doRemoveNode(e){var t=this.getNode(e),d=this.inEdgesMap.get(e),a=this.outEdgesMap.get(e);d?.forEach(e=>this.doRemoveEdge(e.id)),a?.forEach(e=>this.doRemoveEdge(e.id)),this.nodeMap.delete(e),this.treeIndices.forEach(t=>{t.childrenMap.get(e)?.forEach(e=>{t.parentMap.delete(e.id)}),t.parentMap.delete(e),t.childrenMap.delete(e)}),this.changes.push({type:"NodeRemoved",value:t})}removeNodes(e){this.batch(()=>{e.forEach(e=>this.doRemoveNode(e))})}removeNode(e){this.removeNodes([e])}updateNodeDataProperty(d,a,s){const r=this.getNode(d);this.batch(()=>{var e=r.data[a],t=s;r.data[a]=t,this.changes.push({type:"NodeDataUpdated",id:d,propertyName:a,oldValue:e,newValue:t})})}mergeNodeData(d,e){this.batch(()=>{Object.entries(e).forEach(([e,t])=>{this.updateNodeDataProperty(d,e,t)})})}updateNodeData(...e){const a=e[0],s=this.getNode(a);if("string"==typeof e[1])this.updateNodeDataProperty(a,e[1],e[2]);else{let d;var t;"function"==typeof e[1]?(t=e[1],d=t(s.data)):"object"==typeof e[1]&&(d=e[1]),this.batch(()=>{var e=s.data,t=d;s.data=d,this.changes.push({type:"NodeDataUpdated",id:a,oldValue:e,newValue:t})})}}checkEdgeExistence(e){if(!this.hasEdge(e))throw new Error("Edge not found for id: "+e)}hasEdge(e){return this.edgeMap.has(e)}getEdge(e){return this.checkEdgeExistence(e),this.edgeMap.get(e)}getEdgeDetail(e){return{edge:e=this.getEdge(e),source:this.getNode(e.source),target:this.getNode(e.target)}}doAddEdge(e){if(this.hasEdge(e.id))throw new Error("Edge already exists: "+e.id);this.checkNodeExistence(e.source),this.checkNodeExistence(e.target),this.edgeMap.set(e.id,e);var t=this.inEdgesMap.get(e.target),d=this.outEdgesMap.get(e.source);t.add(e),d.add(e),this.changes.push({type:"EdgeAdded",value:e})}addEdges(t){this.batch(()=>{for(const e of t)this.doAddEdge(e)})}addEdge(e){this.addEdges([e])}doRemoveEdge(e){var t=this.getEdge(e),d=this.outEdgesMap.get(t.source),a=this.inEdgesMap.get(t.target);d.delete(t),a.delete(t),this.edgeMap.delete(e),this.changes.push({type:"EdgeRemoved",value:t})}removeEdges(e){this.batch(()=>{e.forEach(e=>this.doRemoveEdge(e))})}removeEdge(e){this.removeEdges([e])}updateEdgeSource(e,t){var d=this.getEdge(e);this.checkNodeExistence(t);const a=d.source,s=t;this.outEdgesMap.get(a).delete(d),this.outEdgesMap.get(s).add(d),d.source=t,this.batch(()=>{this.changes.push({type:"EdgeUpdated",id:e,propertyName:"source",oldValue:a,newValue:s})})}updateEdgeTarget(e,t){var d=this.getEdge(e);this.checkNodeExistence(t);const a=d.target,s=t;this.inEdgesMap.get(a).delete(d),this.inEdgesMap.get(s).add(d),d.target=t,this.batch(()=>{this.changes.push({type:"EdgeUpdated",id:e,propertyName:"target",oldValue:a,newValue:s})})}updateEdgeDataProperty(d,a,s){const r=this.getEdge(d);this.batch(()=>{var e=r.data[a],t=s;r.data[a]=t,this.changes.push({type:"EdgeDataUpdated",id:d,propertyName:a,oldValue:e,newValue:t})})}updateEdgeData(...e){const a=e[0],s=this.getEdge(a);if("string"==typeof e[1])this.updateEdgeDataProperty(a,e[1],e[2]);else{let d;var t;"function"==typeof e[1]?(t=e[1],d=t(s.data)):"object"==typeof e[1]&&(d=e[1]),this.batch(()=>{var e=s.data,t=d;s.data=d,this.changes.push({type:"EdgeDataUpdated",id:a,oldValue:e,newValue:t})})}}mergeEdgeData(d,e){this.batch(()=>{Object.entries(e).forEach(([e,t])=>{this.updateEdgeDataProperty(d,e,t)})})}checkTreeExistence(e){if(!this.treeIndices.has(e))throw new Error("Tree structure not found for treeKey: "+e)}attachTreeStructure(e){this.treeIndices.has(e)||(this.treeIndices.set(e,{parentMap:new Map,childrenMap:new Map}),this.batch(()=>{this.changes.push({type:"TreeStructureAttached",treeKey:e})}))}detachTreeStructure(e){this.checkTreeExistence(e),this.treeIndices.delete(e),this.batch(()=>{this.changes.push({type:"TreeStructureDetached",treeKey:e})})}addTree(a,s){this.batch(()=>{this.attachTreeStructure(s);for(var e=[],t=Array.isArray(a)?a:[a];t.length;){var d=t.shift();e.push(d),d.children&&t.push(...d.children)}this.addNodes(e),e.forEach(t=>{t.children?.forEach(e=>{this.setParent(e.id,t.id,s)})})})}getRoots(t){return this.checkTreeExistence(t),this.getAllNodes().filter(e=>!this.getParent(e.id,t))}getChildren(e,t){return this.checkNodeExistence(e),this.checkTreeExistence(t),t=this.treeIndices.get(t).childrenMap.get(e),Array.from(t||[])}getParent(e,t){return this.checkNodeExistence(e),this.checkTreeExistence(t),this.treeIndices.get(t).parentMap.get(e)||null}setParent(e,t,d){this.checkTreeExistence(d);var a=this.treeIndices.get(d),s=this.getNode(e);const r=a.parentMap.get(e),h=this.getNode(t);a.parentMap.set(e,h),r&&a.childrenMap.get(r.id)?.delete(s);let i=a.childrenMap.get(h.id);i||(i=new Set,a.childrenMap.set(h.id,i)),i.add(s),this.batch(()=>{this.changes.push({type:"TreeStructureChanged",treeKey:d,nodeId:e,oldParentId:r?.id,newParentId:h.id})})}getAllNodes(){return Array.from(this.nodeMap.values())}getAllEdges(){return Array.from(this.edgeMap.values())}doBFS(t,d,e){for(;t.length;){var a=t.shift();e(a),d.add(a.id),this.getSuccessors(a.id).forEach(e=>{d.has(e.id)||(d.add(e.id),t.push(e))})}}bfs(e,t){this.doBFS([this.getNode(e)],new Set,t)}doDFS(e,t,d){d(e),t.add(e.id),this.getSuccessors(e.id).forEach(e=>{t.has(e.id)||this.doDFS(e,t,d)})}dfs(e,t){this.doDFS(this.getNode(e),new Set,t)}clone(){var e=this.getAllNodes().map(e=>({...e,data:{...e.data}})),t=this.getAllEdges().map(e=>({...e,data:{...e.data}}));const r=new d({nodes:e,edges:t});return this.treeIndices.forEach(({parentMap:e,childrenMap:t},d)=>{const a=new Map,s=(e.forEach((e,t)=>{a.set(t,r.getNode(e.id))}),new Map);t.forEach((e,t)=>{s.set(t,new Set(Array.from(e).map(e=>r.getNode(e.id))))}),r.treeIndices.set(d,{parentMap:a,childrenMap:s})}),r}toJSON(){return JSON.stringify({nodes:this.getAllNodes(),edges:this.getAllEdges()})}},Object.defineProperty(e,"__esModule",{value:!0})});
+!function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports):"function"==typeof define&&define.amd?define(["exports"],t):t((e="undefined"!=typeof globalThis?globalThis:e||self).GraphLib={})}(this,function(e){"use strict";function t(){this._events={}}function d(t,s,e,d){for(;t.length;){var a=t.shift();if(e(a))return!0;s.add(a.id),d(a.id).forEach(e=>{s.has(e.id)||(s.add(e.id),t.push(e))})}return!1}function r(e,t,s,d){if(s(e))return!0;t.add(e.id);for(const a of d(e.id))if(!t.has(a.id)&&r(a,t,s,d))return!0;return!1}t.prototype.on=function(e,t,s){return this._events[e]||(this._events[e]=[]),this._events[e].push({callback:t,once:!!s}),this},t.prototype.once=function(e,t){return this.on(e,t,!0)},t.prototype.emit=function(r){for(var h=this,i=[],e=1;e<arguments.length;e++)i[e-1]=arguments[e];function t(e){for(var t,s,d=e.length,a=0;a<d;a++)e[a]&&(s=(t=e[a]).callback,t.once&&(e.splice(a,1),0===e.length&&delete h._events[r],d--,a--),s.apply(h,i))}var s=this._events[r]||[],d=this._events["*"]||[];t(s),t(d)},t.prototype.off=function(e,t){if(e)if(t){for(var s=this._events[e]||[],d=s.length,a=0;a<d;a++)s[a].callback===t&&(s.splice(a,1),d--,a--);0===s.length&&delete this._events[e]}else delete this._events[e];else this._events={};return this},t.prototype.getEvents=function(){return this._events};class s extends t{nodeMap=new Map;edgeMap=new Map;inEdgesMap=new Map;outEdgesMap=new Map;bothEdgesMap=new Map;treeIndices=new Map;changes=[];batchCount=0;onChanged=()=>{};constructor(e){super(),e&&(e.nodes&&this.addNodes(e.nodes),e.edges&&this.addEdges(e.edges),e.tree&&this.addTree(e.tree),e.onChanged)&&(this.onChanged=e.onChanged)}batch=e=>{this.batchCount+=1,e(),--this.batchCount,this.batchCount||this.commit()};commit(){var e=this.changes,e=(this.changes=[],{graph:this,changes:e});this.emit("changed",e),this.onChanged(e)}reduceChanges(e){let t=[];return e.forEach(d=>{switch(d.type){case"NodeRemoved":{let s=!1;t=t.filter(e=>{var t;return"NodeAdded"===e.type?((t=e.value.id===d.value.id)&&(s=!0),!t):"NodeDataUpdated"===e.type?e.id!==d.value.id:"TreeStructureChanged"!==e.type||e.nodeId!==d.value.id}),s||t.push(d);break}case"EdgeRemoved":{let s=!1;t=t.filter(e=>{var t;return"EdgeAdded"===e.type?((t=e.value.id===d.value.id)&&(s=!0),!t):"EdgeDataUpdated"!==e.type&&"EdgeUpdated"!==e.type||e.id!==d.value.id}),s||t.push(d);break}case"NodeDataUpdated":case"EdgeDataUpdated":case"EdgeUpdated":var e=t.find(e=>e.type===d.type&&e.id===d.id&&e.propertyName===d.propertyName);e?e.newValue=d.newValue:t.push(d);break;case"TreeStructureDetached":(t=t.filter(e=>"TreeStructureAttached"!==e.type&&"TreeStructureChanged"!==e.type||e.treeKey!==d.treeKey)).push(d);break;case"TreeStructureChanged":e=t.find(e=>"TreeStructureChanged"===e.type&&e.treeKey===d.treeKey&&e.nodeId===d.nodeId);e?e.newParentId=d.newParentId:t.push(d);break;default:t.push(d)}}),t}checkNodeExistence(e){this.getNode(e)}hasNode(e){return this.nodeMap.has(e)}areNeighbors(t,e){return this.getNeighbors(e).some(e=>e.id===t)}getNode(e){var t=this.nodeMap.get(e);if(t)return t;throw new Error("Node not found for id: "+e)}getRelatedEdges(e,t){var s;return this.checkNodeExistence(e),"in"===t?(s=this.inEdgesMap.get(e),Array.from(s)):"out"===t?(s=this.outEdgesMap.get(e),Array.from(s)):(t=this.bothEdgesMap.get(e),Array.from(t))}getDegree(e,t){return this.getRelatedEdges(e,t).length}getSuccessors(e){e=this.getRelatedEdges(e,"out").map(e=>this.getNode(e.target));return Array.from(new Set(e))}getPredecessors(e){e=this.getRelatedEdges(e,"in").map(e=>this.getNode(e.source));return Array.from(new Set(e))}getNeighbors(e){var t=this.getPredecessors(e),e=this.getSuccessors(e);return Array.from(new Set([...t,...e]))}doAddNode(t){if(this.hasNode(t.id))throw new Error("Node already exists: "+t.id);this.nodeMap.set(t.id,t),this.inEdgesMap.set(t.id,new Set),this.outEdgesMap.set(t.id,new Set),this.bothEdgesMap.set(t.id,new Set),this.treeIndices.forEach(e=>{e.childrenMap.set(t.id,new Set)}),this.changes.push({type:"NodeAdded",value:t})}addNodes(t){this.batch(()=>{for(const e of t)this.doAddNode(e)})}addNode(e){this.addNodes([e])}doRemoveNode(e){var t=this.getNode(e);this.bothEdgesMap.get(e)?.forEach(e=>this.doRemoveEdge(e.id)),this.nodeMap.delete(e),this.treeIndices.forEach(t=>{t.childrenMap.get(e)?.forEach(e=>{t.parentMap.delete(e.id)}),t.parentMap.delete(e),t.childrenMap.delete(e)}),this.changes.push({type:"NodeRemoved",value:t})}removeNodes(e){this.batch(()=>{e.forEach(e=>this.doRemoveNode(e))})}removeNode(e){this.removeNodes([e])}updateNodeDataProperty(s,d,a){const r=this.getNode(s);this.batch(()=>{var e=r.data[d],t=a;r.data[d]=t,this.changes.push({type:"NodeDataUpdated",id:s,propertyName:d,oldValue:e,newValue:t})})}mergeNodeData(s,e){this.batch(()=>{Object.entries(e).forEach(([e,t])=>{this.updateNodeDataProperty(s,e,t)})})}updateNodeData(...e){const d=e[0],a=this.getNode(d);if("string"==typeof e[1])this.updateNodeDataProperty(d,e[1],e[2]);else{let s;var t;"function"==typeof e[1]?(t=e[1],s=t(a.data)):"object"==typeof e[1]&&(s=e[1]),this.batch(()=>{var e=a.data,t=s;a.data=s,this.changes.push({type:"NodeDataUpdated",id:d,oldValue:e,newValue:t})})}}checkEdgeExistence(e){if(!this.hasEdge(e))throw new Error("Edge not found for id: "+e)}hasEdge(e){return this.edgeMap.has(e)}getEdge(e){return this.checkEdgeExistence(e),this.edgeMap.get(e)}getEdgeDetail(e){e=this.getEdge(e);return{edge:e,source:this.getNode(e.source),target:this.getNode(e.target)}}doAddEdge(e){if(this.hasEdge(e.id))throw new Error("Edge already exists: "+e.id);this.checkNodeExistence(e.source),this.checkNodeExistence(e.target),this.edgeMap.set(e.id,e);var t=this.inEdgesMap.get(e.target),s=this.outEdgesMap.get(e.source),d=this.bothEdgesMap.get(e.source),a=this.bothEdgesMap.get(e.target);t.add(e),s.add(e),d.add(e),a.add(e),this.changes.push({type:"EdgeAdded",value:e})}addEdges(t){this.batch(()=>{for(const e of t)this.doAddEdge(e)})}addEdge(e){this.addEdges([e])}doRemoveEdge(e){var t=this.getEdge(e),s=this.outEdgesMap.get(t.source),d=this.inEdgesMap.get(t.target),a=this.bothEdgesMap.get(t.source),r=this.bothEdgesMap.get(t.target);s.delete(t),d.delete(t),a.delete(t),r.delete(t),this.edgeMap.delete(e),this.changes.push({type:"EdgeRemoved",value:t})}removeEdges(e){this.batch(()=>{e.forEach(e=>this.doRemoveEdge(e))})}removeEdge(e){this.removeEdges([e])}updateEdgeSource(e,t){var s=this.getEdge(e);this.checkNodeExistence(t);const d=s.source,a=t;this.outEdgesMap.get(d).delete(s),this.bothEdgesMap.get(d).delete(s),this.outEdgesMap.get(a).add(s),this.bothEdgesMap.get(a).add(s),s.source=t,this.batch(()=>{this.changes.push({type:"EdgeUpdated",id:e,propertyName:"source",oldValue:d,newValue:a})})}updateEdgeTarget(e,t){var s=this.getEdge(e);this.checkNodeExistence(t);const d=s.target,a=t;this.inEdgesMap.get(d).delete(s),this.bothEdgesMap.get(d).delete(s),this.inEdgesMap.get(a).add(s),this.bothEdgesMap.get(a).add(s),s.target=t,this.batch(()=>{this.changes.push({type:"EdgeUpdated",id:e,propertyName:"target",oldValue:d,newValue:a})})}updateEdgeDataProperty(s,d,a){const r=this.getEdge(s);this.batch(()=>{var e=r.data[d],t=a;r.data[d]=t,this.changes.push({type:"EdgeDataUpdated",id:s,propertyName:d,oldValue:e,newValue:t})})}updateEdgeData(...e){const d=e[0],a=this.getEdge(d);if("string"==typeof e[1])this.updateEdgeDataProperty(d,e[1],e[2]);else{let s;var t;"function"==typeof e[1]?(t=e[1],s=t(a.data)):"object"==typeof e[1]&&(s=e[1]),this.batch(()=>{var e=a.data,t=s;a.data=s,this.changes.push({type:"EdgeDataUpdated",id:d,oldValue:e,newValue:t})})}}mergeEdgeData(s,e){this.batch(()=>{Object.entries(e).forEach(([e,t])=>{this.updateEdgeDataProperty(s,e,t)})})}checkTreeExistence(e){if(!this.hasTreeStructure(e))throw new Error("Tree structure not found for treeKey: "+e)}hasTreeStructure(e){return this.treeIndices.has(e)}attachTreeStructure(e){this.treeIndices.has(e)||(this.treeIndices.set(e,{parentMap:new Map,childrenMap:new Map}),this.batch(()=>{this.changes.push({type:"TreeStructureAttached",treeKey:e})}))}detachTreeStructure(e){this.checkTreeExistence(e),this.treeIndices.delete(e),this.batch(()=>{this.changes.push({type:"TreeStructureDetached",treeKey:e})})}addTree(d,a){this.batch(()=>{this.attachTreeStructure(a);for(var e=[],t=Array.isArray(d)?d:[d];t.length;){var s=t.shift();e.push(s),s.children&&t.push(...s.children)}this.addNodes(e),e.forEach(t=>{t.children?.forEach(e=>{this.setParent(e.id,t.id,a)})})})}getRoots(t){return this.checkTreeExistence(t),this.getAllNodes().filter(e=>!this.getParent(e.id,t))}getChildren(e,t){this.checkNodeExistence(e),this.checkTreeExistence(t);t=this.treeIndices.get(t).childrenMap.get(e);return Array.from(t||[])}getParent(e,t){return this.checkNodeExistence(e),this.checkTreeExistence(t),this.treeIndices.get(t).parentMap.get(e)||null}getAncestors(e,t){var s,d=[];let a=this.getNode(e);for(;s=this.getParent(a.id,t);)d.push(s),a=s;return d}setParent(e,t,s){this.checkTreeExistence(s);var d=this.treeIndices.get(s),a=this.getNode(e);const r=d.parentMap.get(e),h=this.getNode(t);d.parentMap.set(e,h),r&&d.childrenMap.get(r.id)?.delete(a);let i=d.childrenMap.get(h.id);i||(i=new Set,d.childrenMap.set(h.id,i)),i.add(a),this.batch(()=>{this.changes.push({type:"TreeStructureChanged",treeKey:s,nodeId:e,oldParentId:r?.id,newParentId:h.id})})}dfsTree(e,t,s){return r(this.getNode(e),new Set,t,e=>this.getChildren(e,s))}bfsTree(e,t,s){return d([this.getNode(e)],new Set,t,e=>this.getChildren(e,s))}getAllNodes(){return Array.from(this.nodeMap.values())}getAllEdges(){return Array.from(this.edgeMap.values())}bfs(e,t,s="out"){s={in:this.getPredecessors.bind(this),out:this.getSuccessors.bind(this),both:this.getNeighbors.bind(this)}[s];return d([this.getNode(e)],new Set,t,s)}dfs(e,t,s="out"){s={in:this.getPredecessors.bind(this),out:this.getSuccessors.bind(this),both:this.getNeighbors.bind(this)}[s];return r(this.getNode(e),new Set,t,s)}clone(){var e=this.getAllNodes().map(e=>({...e,data:{...e.data}})),t=this.getAllEdges().map(e=>({...e,data:{...e.data}}));const r=new s({nodes:e,edges:t});return this.treeIndices.forEach(({parentMap:e,childrenMap:t},s)=>{const d=new Map,a=(e.forEach((e,t)=>{d.set(t,r.getNode(e.id))}),new Map);t.forEach((e,t)=>{a.set(t,new Set(Array.from(e).map(e=>r.getNode(e.id))))}),r.treeIndices.set(s,{parentMap:d,childrenMap:a})}),r}toJSON(){return JSON.stringify({nodes:this.getAllNodes(),edges:this.getAllEdges()})}}const h=()=>!0;e.Graph=s,e.GraphView=class{graph;nodeFilter;edgeFilter;cacheEnabled;inEdgesMap=new Map;outEdgesMap=new Map;bothEdgesMap=new Map;allNodesMap=new Map;allEdgesMap=new Map;constructor(e){this.graph=e.graph;const d=e.nodeFilter||h,a=e.edgeFilter||h;this.nodeFilter=d,this.edgeFilter=e=>{var{source:t,target:s}=this.graph.getEdgeDetail(e.id);return!(!d(t)||!d(s))&&a(e,t,s)},"auto"===e.cache?(this.cacheEnabled=!0,this.startAutoCache()):"manual"===e.cache?this.cacheEnabled=!0:this.cacheEnabled=!1}clearCache=()=>{this.inEdgesMap.clear(),this.outEdgesMap.clear(),this.bothEdgesMap.clear(),this.allNodesMap.clear(),this.allEdgesMap.clear()};refreshCache=()=>{this.clearCache(),this.updateCache(this.graph.getAllNodes().map(e=>e.id))};updateCache=e=>{const a=new Set;e.forEach(e=>{var t,s,d=this.bothEdgesMap.get(e);d&&d.forEach(e=>a.add(e.id)),this.hasNode(e)?(d=this.graph.getRelatedEdges(e,"in").filter(this.edgeFilter),t=this.graph.getRelatedEdges(e,"out").filter(this.edgeFilter),(s=Array.from(new Set([...d,...t]))).forEach(e=>a.add(e.id)),this.inEdgesMap.set(e,d),this.outEdgesMap.set(e,t),this.bothEdgesMap.set(e,s),this.allNodesMap.set(e,this.graph.getNode(e))):(this.inEdgesMap.delete(e),this.outEdgesMap.delete(e),this.bothEdgesMap.delete(e),this.allNodesMap.delete(e))}),a.forEach(e=>{this.hasEdge(e)?this.allEdgesMap.set(e,this.graph.getEdge(e)):this.allEdgesMap.delete(e)})};startAutoCache(){this.refreshCache(),this.graph.on("changed",this.handleGraphChanged)}stopAutoCache(){this.graph.off("changed",this.handleGraphChanged)}handleGraphChanged=s=>{const d=new Set;s.changes.forEach(e=>{switch(e.type){case"NodeAdded":d.add(e.value.id);break;case"NodeDataUpdated":d.add(e.id);break;case"EdgeAdded":d.add(e.value.source),d.add(e.value.target);break;case"EdgeUpdated":"source"!==e.propertyName&&"target"!==e.propertyName||(d.add(e.oldValue),d.add(e.newValue));break;case"EdgeDataUpdated":var t;s.graph.hasEdge(e.id)&&(t=s.graph.getEdge(e.id),d.add(t.source),d.add(t.target));break;case"EdgeRemoved":d.add(e.value.source),d.add(e.value.target);break;case"NodeRemoved":d.add(e.value.id)}}),this.updateCache(d)};checkNodeExistence(e){this.getNode(e)}hasNode(e){return!!this.graph.hasNode(e)&&(e=this.graph.getNode(e),this.nodeFilter(e))}areNeighbors(t,e){return this.checkNodeExistence(t),this.getNeighbors(e).some(e=>e.id===t)}getNode(e){var t=this.graph.getNode(e);if(this.nodeFilter(t))return t;throw new Error("Node not found for id: "+e)}getRelatedEdges(e,t){return this.checkNodeExistence(e),this.cacheEnabled?("in"===t?this.inEdgesMap:"out"===t?this.outEdgesMap:this.bothEdgesMap).get(e):this.graph.getRelatedEdges(e,t).filter(this.edgeFilter)}getDegree(e,t){return this.getRelatedEdges(e,t).length}getSuccessors(e){e=this.getRelatedEdges(e,"out").map(e=>this.getNode(e.target));return Array.from(new Set(e))}getPredecessors(e){e=this.getRelatedEdges(e,"in").map(e=>this.getNode(e.source));return Array.from(new Set(e))}getNeighbors(e){var t=this.getPredecessors(e),e=this.getSuccessors(e);return Array.from(new Set([...t,...e]))}hasEdge(e){return!!this.graph.hasEdge(e)&&(e=this.graph.getEdge(e),this.edgeFilter(e))}getEdge(e){var t=this.graph.getEdge(e);if(this.edgeFilter(t))return t;throw new Error("Edge not found for id: "+e)}getEdgeDetail(e){e=this.getEdge(e);return{edge:e,source:this.getNode(e.source),target:this.getNode(e.target)}}hasTreeStructure(e){return this.graph.hasTreeStructure(e)}getRoots(e){return this.graph.getRoots(e).filter(this.nodeFilter)}getChildren(e,t){return this.checkNodeExistence(e),this.graph.getChildren(e,t).filter(this.nodeFilter)}getParent(e,t){this.checkNodeExistence(e);e=this.graph.getParent(e,t);return e&&this.nodeFilter(e)?e:null}getAllNodes(){return this.cacheEnabled?Array.from(this.allNodesMap.values()):this.graph.getAllNodes().filter(this.nodeFilter)}getAllEdges(){return this.cacheEnabled?Array.from(this.allEdgesMap.values()):this.graph.getAllEdges().filter(this.edgeFilter)}bfs(e,t,s="out"){s={in:this.getPredecessors.bind(this),out:this.getSuccessors.bind(this),both:this.getNeighbors.bind(this)}[s];d([this.getNode(e)],new Set,t,s)}dfs(e,t,s="out"){s={in:this.getPredecessors.bind(this),out:this.getSuccessors.bind(this),both:this.getNeighbors.bind(this)}[s];r(this.getNode(e),new Set,t,s)}},Object.defineProperty(e,"__esModule",{value:!0})});

esm/graph.d.ts

@@ -0,3 +1,4 @@
+import EventEmitter from '@antv/event-emitter';
 import { Node, Edge, GraphChange, GraphChangedEvent, GraphOptions, ID, TreeData, PlainObject } from './types';
-export declare class Graph<N extends PlainObject, E extends PlainObject> {
+export declare class Graph<N extends PlainObject, E extends PlainObject> extends EventEmitter {
     private nodeMap;
@@ -7,2 +8,3 @@ private edgeMap;
     private outEdgesMap;
+    private bothEdgesMap;
     private treeIndices;
@@ -292,2 +294,3 @@ private changes;
     private checkTreeExistence;
+    hasTreeStructure(treeKey: string | undefined): boolean;
     /**
@@ -409,2 +412,6 @@ * Attach a new tree structure representing the hierarchy of all nodes in the graph.
     /**
+     * Returns an array of all the ancestor nodes, staring from the parent to the root.
+     */
+    getAncestors(id: ID, treeKey?: string): Node<N>[];
+    /**
      * Set node parent. If this operation causes a circle, it fails with an error.
@@ -417,2 +424,4 @@ * @param id - ID of the child node.
     setParent(id: ID, parent: ID, treeKey?: string): void;
+    dfsTree(id: ID, fn: (node: Node<N>) => boolean | void, treeKey?: string): boolean;
+    bfsTree(id: ID, fn: (node: Node<N>) => boolean | void, treeKey?: string): boolean;
     /**
@@ -426,8 +435,6 @@ * Get all nodes in the graph as an array.
     getAllEdges(): Edge<E>[];
-    private doBFS;
-    bfs(id: ID, fn: (node: Node<N>) => void): void;
-    private doDFS;
-    dfs(id: ID, fn: (node: Node<N>) => void): void;
+    bfs(id: ID, fn: (node: Node<N>) => boolean | void, direction?: 'in' | 'out' | 'both'): boolean;
+    dfs(id: ID, fn: (node: Node<N>) => boolean | void, direction?: 'in' | 'out' | 'both'): boolean;
     clone(): Graph<N, E>;
     toJSON(): string;
 }

esm/graph.js

@@ -1,2 +0,4 @@
-export class Graph {
+import EventEmitter from '@antv/event-emitter';
+import { doBFS, doDFS } from './utils/traverse';
+export class Graph extends EventEmitter {
     nodeMap = new Map();
@@ -6,2 +8,3 @@ edgeMap = new Map();
     outEdgesMap = new Map();
+    bothEdgesMap = new Map();
     treeIndices = new Map();
@@ -42,2 +45,3 @@ changes = [];
     constructor(options) {
+        super();
         if (!options)
@@ -89,6 +93,8 @@ return;
         this.changes = [];
-        this.onChanged({
+        const event = {
             graph: this,
             changes,
-        });
+        };
+        this.emit('changed', event);
+        this.onChanged(event);
     }
@@ -235,5 +241,3 @@ /**
     checkNodeExistence(id) {
-        if (!this.hasNode(id)) {
-            throw new Error('Node not found for id: ' + id);
-        }
+        this.getNode(id);
     }
@@ -252,3 +256,2 @@ /**
     areNeighbors(firstNodeId, secondNodeId) {
-        this.checkNodeExistence(firstNodeId);
         return this.getNeighbors(secondNodeId).some((neighbor) => neighbor.id === firstNodeId);
@@ -261,4 +264,7 @@ }
     getNode(id) {
-        this.checkNodeExistence(id);
-        return this.nodeMap.get(id);
+        const node = this.nodeMap.get(id);
+        if (!node) {
+            throw new Error('Node not found for id: ' + id);
+        }
+        return node;
     }
@@ -273,12 +279,14 @@ /**
         this.checkNodeExistence(id);
-        const inEdges = this.inEdgesMap.get(id);
-        const outEdges = this.outEdgesMap.get(id);
         if (direction === 'in') {
+            const inEdges = this.inEdgesMap.get(id);
             return Array.from(inEdges);
         }
         else if (direction === 'out') {
+            const outEdges = this.outEdgesMap.get(id);
             return Array.from(outEdges);
         }
-        const bothEdges = new Set([...inEdges, ...outEdges]);
-        return Array.from(bothEdges);
+        else {
+            const bothEdges = this.bothEdgesMap.get(id);
+            return Array.from(bothEdges);
+        }
     }
@@ -297,4 +305,4 @@ /**
         const outEdges = this.getRelatedEdges(id, 'out');
-        const targets = outEdges.map((edge) => edge.target);
-        return Array.from(new Set(targets)).map((id) => this.getNode(id));
+        const targets = outEdges.map((edge) => this.getNode(edge.target));
+        return Array.from(new Set(targets));
     }
@@ -306,4 +314,4 @@ /**
         const inEdges = this.getRelatedEdges(id, 'in');
-        const sources = inEdges.map((edge) => edge.source);
-        return Array.from(new Set(sources)).map((id) => this.getNode(id));
+        const sources = inEdges.map((edge) => this.getNode(edge.source));
+        return Array.from(new Set(sources));
     }
@@ -327,2 +335,3 @@ /**
         this.outEdgesMap.set(node.id, new Set());
+        this.bothEdgesMap.set(node.id, new Set());
         this.treeIndices.forEach((tree) => {
@@ -353,6 +362,4 @@ tree.childrenMap.set(node.id, new Set());
         const node = this.getNode(id);
-        const inEdges = this.inEdgesMap.get(id);
-        const outEdges = this.outEdgesMap.get(id);
-        inEdges?.forEach((edge) => this.doRemoveEdge(edge.id));
-        outEdges?.forEach((edge) => this.doRemoveEdge(edge.id));
+        const bothEdges = this.bothEdgesMap.get(id);
+        bothEdges?.forEach((edge) => this.doRemoveEdge(edge.id));
         this.nodeMap.delete(id);
@@ -483,4 +490,8 @@ this.treeIndices.forEach((tree) => {
         const outEdges = this.outEdgesMap.get(edge.source);
+        const bothEdgesOfSource = this.bothEdgesMap.get(edge.source);
+        const bothEdgesOfTarget = this.bothEdgesMap.get(edge.target);
         inEdges.add(edge);
         outEdges.add(edge);
+        bothEdgesOfSource.add(edge);
+        bothEdgesOfTarget.add(edge);
         this.changes.push({ type: 'EdgeAdded', value: edge });
@@ -518,4 +529,8 @@ }
         const inEdges = this.inEdgesMap.get(edge.target);
+        const bothEdgesOfSource = this.bothEdgesMap.get(edge.source);
+        const bothEdgesOfTarget = this.bothEdgesMap.get(edge.target);
         outEdges.delete(edge);
         inEdges.delete(edge);
+        bothEdgesOfSource.delete(edge);
+        bothEdgesOfTarget.delete(edge);
         this.edgeMap.delete(id);
@@ -550,3 +565,5 @@ this.changes.push({ type: 'EdgeRemoved', value: edge });
         this.outEdgesMap.get(oldSource).delete(edge);
+        this.bothEdgesMap.get(oldSource).delete(edge);
         this.outEdgesMap.get(newSource).add(edge);
+        this.bothEdgesMap.get(newSource).add(edge);
         edge.source = source;
@@ -573,3 +590,5 @@ this.batch(() => {
         this.inEdgesMap.get(oldTarget).delete(edge);
+        this.bothEdgesMap.get(oldTarget).delete(edge);
         this.inEdgesMap.get(newTarget).add(edge);
+        this.bothEdgesMap.get(newTarget).add(edge);
         edge.target = target;
@@ -643,6 +662,9 @@ this.batch(() => {
     checkTreeExistence(treeKey) {
-        if (!this.treeIndices.has(treeKey)) {
+        if (!this.hasTreeStructure(treeKey)) {
             throw new Error('Tree structure not found for treeKey: ' + treeKey);
         }
     }
+    hasTreeStructure(treeKey) {
+        return this.treeIndices.has(treeKey);
+    }
     /**
@@ -823,2 +845,15 @@ * Attach a new tree structure representing the hierarchy of all nodes in the graph.
     /**
+     * Returns an array of all the ancestor nodes, staring from the parent to the root.
+     */
+    getAncestors(id, treeKey) {
+        const ancestors = [];
+        let current = this.getNode(id);
+        let parent;
+        while (parent = this.getParent(current.id, treeKey)) {
+            ancestors.push(parent);
+            current = parent;
+        }
+        return ancestors;
+    }
+    /**
      * Set node parent. If this operation causes a circle, it fails with an error.
@@ -858,2 +893,10 @@ * @param id - ID of the child node.
     }
+    dfsTree(id, fn, treeKey) {
+        const navigator = (nodeId) => this.getChildren(nodeId, treeKey);
+        return doDFS(this.getNode(id), new Set(), fn, navigator);
+    }
+    bfsTree(id, fn, treeKey) {
+        const navigator = (nodeId) => this.getChildren(nodeId, treeKey);
+        return doBFS([this.getNode(id)], new Set(), fn, navigator);
+    }
     // ================= Graph =================
@@ -872,30 +915,18 @@ /**
     }
-    doBFS(queue, visited, fn) {
-        while (queue.length) {
-            const node = queue.shift();
-            fn(node);
-            visited.add(node.id);
-            this.getSuccessors(node.id).forEach((n) => {
-                if (!visited.has(n.id)) {
-                    visited.add(n.id);
-                    queue.push(n);
-                }
-            });
-        }
+    bfs(id, fn, direction = 'out') {
+        const navigator = {
+            in: this.getPredecessors.bind(this),
+            out: this.getSuccessors.bind(this),
+            both: this.getNeighbors.bind(this),
+        }[direction];
+        return doBFS([this.getNode(id)], new Set(), fn, navigator);
     }
-    bfs(id, fn) {
-        this.doBFS([this.getNode(id)], new Set(), fn);
+    dfs(id, fn, direction = 'out') {
+        const navigator = {
+            in: this.getPredecessors.bind(this),
+            out: this.getSuccessors.bind(this),
+            both: this.getNeighbors.bind(this),
+        }[direction];
+        return doDFS(this.getNode(id), new Set(), fn, navigator);
     }
-    doDFS(node, visited, fn) {
-        fn(node);
-        visited.add(node.id);
-        this.getSuccessors(node.id).forEach((n) => {
-            if (!visited.has(n.id)) {
-                this.doDFS(n, visited, fn);
-            }
-        });
-    }
-    dfs(id, fn) {
-        this.doDFS(this.getNode(id), new Set(), fn);
-    }
     clone() {
@@ -902,0 +933,0 @@ // Make a shallow copy of nodes and edges.

esm/index.d.ts

 export * from './types';
 export * from './graph';
+export * from './graphView';

esm/index.js

 export * from './types';
 export * from './graph';
+export * from './graphView';
 //# sourceMappingURL=index.js.map

esm/types.d.ts

@@ -160,1 +160,22 @@ import type { Graph } from './graph';
 };
+/** Options to create a GraphView */
+export interface GraphViewOptions<N extends PlainObject, E extends PlainObject> {
+    /** The original Graph */
+    graph: Graph<N, E>;
+    nodeFilter?: (node: Node<N>) => boolean;
+    edgeFilter?: (edge: Edge<E>, source: Node<N>, target: Node<N>) => boolean;
+    /**
+     * Cache mode of the GraphView. Defaults to 'none'.
+     *
+     * - `none`: Use no cache. Filters are applied when reading data. Fast to create but a bit
+     * slow to read data.
+     *
+     * - `auto`: Automatically cache data when view created or graph changed. Fast to read
+     * data but takes time to build up cache. You should call `stopAutoCache()` to avoid
+     * unnecessary updates if the GraphView is no longer active.
+     *
+     * - `manual` Manage cache manually. `clearCache()` `refreshCache()` `updateCache()`
+     * might be useful.
+     */
+    cache?: 'none' | 'auto' | 'manual';
+}

lib/graph.d.ts

@@ -0,3 +1,4 @@
+import EventEmitter from '@antv/event-emitter';
 import { Node, Edge, GraphChange, GraphChangedEvent, GraphOptions, ID, TreeData, PlainObject } from './types';
-export declare class Graph<N extends PlainObject, E extends PlainObject> {
+export declare class Graph<N extends PlainObject, E extends PlainObject> extends EventEmitter {
     private nodeMap;
@@ -7,2 +8,3 @@ private edgeMap;
     private outEdgesMap;
+    private bothEdgesMap;
     private treeIndices;
@@ -292,2 +294,3 @@ private changes;
     private checkTreeExistence;
+    hasTreeStructure(treeKey: string | undefined): boolean;
     /**
@@ -409,2 +412,6 @@ * Attach a new tree structure representing the hierarchy of all nodes in the graph.
     /**
+     * Returns an array of all the ancestor nodes, staring from the parent to the root.
+     */
+    getAncestors(id: ID, treeKey?: string): Node<N>[];
+    /**
      * Set node parent. If this operation causes a circle, it fails with an error.
@@ -417,2 +424,4 @@ * @param id - ID of the child node.
     setParent(id: ID, parent: ID, treeKey?: string): void;
+    dfsTree(id: ID, fn: (node: Node<N>) => boolean | void, treeKey?: string): boolean;
+    bfsTree(id: ID, fn: (node: Node<N>) => boolean | void, treeKey?: string): boolean;
     /**
@@ -426,8 +435,6 @@ * Get all nodes in the graph as an array.
     getAllEdges(): Edge<E>[];
-    private doBFS;
-    bfs(id: ID, fn: (node: Node<N>) => void): void;
-    private doDFS;
-    dfs(id: ID, fn: (node: Node<N>) => void): void;
+    bfs(id: ID, fn: (node: Node<N>) => boolean | void, direction?: 'in' | 'out' | 'both'): boolean;
+    dfs(id: ID, fn: (node: Node<N>) => boolean | void, direction?: 'in' | 'out' | 'both'): boolean;
     clone(): Graph<N, E>;
     toJSON(): string;
 }

lib/graph.js

 "use strict";
+var __importDefault = (this && this.__importDefault) || function (mod) {
+    return (mod && mod.__esModule) ? mod : { "default": mod };
+};
 Object.defineProperty(exports, "__esModule", { value: true });
 exports.Graph = void 0;
-class Graph {
+const event_emitter_1 = __importDefault(require("@antv/event-emitter"));
+const traverse_1 = require("./utils/traverse");
+class Graph extends event_emitter_1.default {
     nodeMap = new Map();
@@ -9,2 +14,3 @@ edgeMap = new Map();
     outEdgesMap = new Map();
+    bothEdgesMap = new Map();
     treeIndices = new Map();
@@ -45,2 +51,3 @@ changes = [];
     constructor(options) {
+        super();
         if (!options)
@@ -92,6 +99,8 @@ return;
         this.changes = [];
-        this.onChanged({
+        const event = {
             graph: this,
             changes,
-        });
+        };
+        this.emit('changed', event);
+        this.onChanged(event);
     }
@@ -238,5 +247,3 @@ /**
     checkNodeExistence(id) {
-        if (!this.hasNode(id)) {
-            throw new Error('Node not found for id: ' + id);
-        }
+        this.getNode(id);
     }
@@ -255,3 +262,2 @@ /**
     areNeighbors(firstNodeId, secondNodeId) {
-        this.checkNodeExistence(firstNodeId);
         return this.getNeighbors(secondNodeId).some((neighbor) => neighbor.id === firstNodeId);
@@ -264,4 +270,7 @@ }
     getNode(id) {
-        this.checkNodeExistence(id);
-        return this.nodeMap.get(id);
+        const node = this.nodeMap.get(id);
+        if (!node) {
+            throw new Error('Node not found for id: ' + id);
+        }
+        return node;
     }
@@ -276,12 +285,14 @@ /**
         this.checkNodeExistence(id);
-        const inEdges = this.inEdgesMap.get(id);
-        const outEdges = this.outEdgesMap.get(id);
         if (direction === 'in') {
+            const inEdges = this.inEdgesMap.get(id);
             return Array.from(inEdges);
         }
         else if (direction === 'out') {
+            const outEdges = this.outEdgesMap.get(id);
             return Array.from(outEdges);
         }
-        const bothEdges = new Set([...inEdges, ...outEdges]);
-        return Array.from(bothEdges);
+        else {
+            const bothEdges = this.bothEdgesMap.get(id);
+            return Array.from(bothEdges);
+        }
     }
@@ -300,4 +311,4 @@ /**
         const outEdges = this.getRelatedEdges(id, 'out');
-        const targets = outEdges.map((edge) => edge.target);
-        return Array.from(new Set(targets)).map((id) => this.getNode(id));
+        const targets = outEdges.map((edge) => this.getNode(edge.target));
+        return Array.from(new Set(targets));
     }
@@ -309,4 +320,4 @@ /**
         const inEdges = this.getRelatedEdges(id, 'in');
-        const sources = inEdges.map((edge) => edge.source);
-        return Array.from(new Set(sources)).map((id) => this.getNode(id));
+        const sources = inEdges.map((edge) => this.getNode(edge.source));
+        return Array.from(new Set(sources));
     }
@@ -330,2 +341,3 @@ /**
         this.outEdgesMap.set(node.id, new Set());
+        this.bothEdgesMap.set(node.id, new Set());
         this.treeIndices.forEach((tree) => {
@@ -356,6 +368,4 @@ tree.childrenMap.set(node.id, new Set());
         const node = this.getNode(id);
-        const inEdges = this.inEdgesMap.get(id);
-        const outEdges = this.outEdgesMap.get(id);
-        inEdges?.forEach((edge) => this.doRemoveEdge(edge.id));
-        outEdges?.forEach((edge) => this.doRemoveEdge(edge.id));
+        const bothEdges = this.bothEdgesMap.get(id);
+        bothEdges?.forEach((edge) => this.doRemoveEdge(edge.id));
         this.nodeMap.delete(id);
@@ -486,4 +496,8 @@ this.treeIndices.forEach((tree) => {
         const outEdges = this.outEdgesMap.get(edge.source);
+        const bothEdgesOfSource = this.bothEdgesMap.get(edge.source);
+        const bothEdgesOfTarget = this.bothEdgesMap.get(edge.target);
         inEdges.add(edge);
         outEdges.add(edge);
+        bothEdgesOfSource.add(edge);
+        bothEdgesOfTarget.add(edge);
         this.changes.push({ type: 'EdgeAdded', value: edge });
@@ -521,4 +535,8 @@ }
         const inEdges = this.inEdgesMap.get(edge.target);
+        const bothEdgesOfSource = this.bothEdgesMap.get(edge.source);
+        const bothEdgesOfTarget = this.bothEdgesMap.get(edge.target);
         outEdges.delete(edge);
         inEdges.delete(edge);
+        bothEdgesOfSource.delete(edge);
+        bothEdgesOfTarget.delete(edge);
         this.edgeMap.delete(id);
@@ -553,3 +571,5 @@ this.changes.push({ type: 'EdgeRemoved', value: edge });
         this.outEdgesMap.get(oldSource).delete(edge);
+        this.bothEdgesMap.get(oldSource).delete(edge);
         this.outEdgesMap.get(newSource).add(edge);
+        this.bothEdgesMap.get(newSource).add(edge);
         edge.source = source;
@@ -576,3 +596,5 @@ this.batch(() => {
         this.inEdgesMap.get(oldTarget).delete(edge);
+        this.bothEdgesMap.get(oldTarget).delete(edge);
         this.inEdgesMap.get(newTarget).add(edge);
+        this.bothEdgesMap.get(newTarget).add(edge);
         edge.target = target;
@@ -646,6 +668,9 @@ this.batch(() => {
     checkTreeExistence(treeKey) {
-        if (!this.treeIndices.has(treeKey)) {
+        if (!this.hasTreeStructure(treeKey)) {
             throw new Error('Tree structure not found for treeKey: ' + treeKey);
         }
     }
+    hasTreeStructure(treeKey) {
+        return this.treeIndices.has(treeKey);
+    }
     /**
@@ -826,2 +851,15 @@ * Attach a new tree structure representing the hierarchy of all nodes in the graph.
     /**
+     * Returns an array of all the ancestor nodes, staring from the parent to the root.
+     */
+    getAncestors(id, treeKey) {
+        const ancestors = [];
+        let current = this.getNode(id);
+        let parent;
+        while (parent = this.getParent(current.id, treeKey)) {
+            ancestors.push(parent);
+            current = parent;
+        }
+        return ancestors;
+    }
+    /**
      * Set node parent. If this operation causes a circle, it fails with an error.
@@ -861,2 +899,10 @@ * @param id - ID of the child node.
     }
+    dfsTree(id, fn, treeKey) {
+        const navigator = (nodeId) => this.getChildren(nodeId, treeKey);
+        return (0, traverse_1.doDFS)(this.getNode(id), new Set(), fn, navigator);
+    }
+    bfsTree(id, fn, treeKey) {
+        const navigator = (nodeId) => this.getChildren(nodeId, treeKey);
+        return (0, traverse_1.doBFS)([this.getNode(id)], new Set(), fn, navigator);
+    }
     // ================= Graph =================
@@ -875,30 +921,18 @@ /**
     }
-    doBFS(queue, visited, fn) {
-        while (queue.length) {
-            const node = queue.shift();
-            fn(node);
-            visited.add(node.id);
-            this.getSuccessors(node.id).forEach((n) => {
-                if (!visited.has(n.id)) {
-                    visited.add(n.id);
-                    queue.push(n);
-                }
-            });
-        }
+    bfs(id, fn, direction = 'out') {
+        const navigator = {
+            in: this.getPredecessors.bind(this),
+            out: this.getSuccessors.bind(this),
+            both: this.getNeighbors.bind(this),
+        }[direction];
+        return (0, traverse_1.doBFS)([this.getNode(id)], new Set(), fn, navigator);
     }
-    bfs(id, fn) {
-        this.doBFS([this.getNode(id)], new Set(), fn);
+    dfs(id, fn, direction = 'out') {
+        const navigator = {
+            in: this.getPredecessors.bind(this),
+            out: this.getSuccessors.bind(this),
+            both: this.getNeighbors.bind(this),
+        }[direction];
+        return (0, traverse_1.doDFS)(this.getNode(id), new Set(), fn, navigator);
     }
-    doDFS(node, visited, fn) {
-        fn(node);
-        visited.add(node.id);
-        this.getSuccessors(node.id).forEach((n) => {
-            if (!visited.has(n.id)) {
-                this.doDFS(n, visited, fn);
-            }
-        });
-    }
-    dfs(id, fn) {
-        this.doDFS(this.getNode(id), new Set(), fn);
-    }
     clone() {
@@ -905,0 +939,0 @@ // Make a shallow copy of nodes and edges.

lib/index.d.ts

 export * from './types';
 export * from './graph';
+export * from './graphView';

lib/index.js

@@ -19,2 +19,3 @@ "use strict";
 __exportStar(require("./graph"), exports);
+__exportStar(require("./graphView"), exports);
 //# sourceMappingURL=index.js.map

lib/types.d.ts

@@ -160,1 +160,22 @@ import type { Graph } from './graph';
 };
+/** Options to create a GraphView */
+export interface GraphViewOptions<N extends PlainObject, E extends PlainObject> {
+    /** The original Graph */
+    graph: Graph<N, E>;
+    nodeFilter?: (node: Node<N>) => boolean;
+    edgeFilter?: (edge: Edge<E>, source: Node<N>, target: Node<N>) => boolean;
+    /**
+     * Cache mode of the GraphView. Defaults to 'none'.
+     *
+     * - `none`: Use no cache. Filters are applied when reading data. Fast to create but a bit
+     * slow to read data.
+     *
+     * - `auto`: Automatically cache data when view created or graph changed. Fast to read
+     * data but takes time to build up cache. You should call `stopAutoCache()` to avoid
+     * unnecessary updates if the GraphView is no longer active.
+     *
+     * - `manual` Manage cache manually. `clearCache()` `refreshCache()` `updateCache()`
+     * might be useful.
+     */
+    cache?: 'none' | 'auto' | 'manual';
+}

package.json

 {
   "name": "@antv/graphlib",
-  "version": "2.0.0-alpha.2",
+  "version": "2.0.0-alpha.3",
+  "sideEffects": false,
   "scripts": {
@@ -22,3 +23,5 @@ "clean": "rimraf lib esm dist",
   "unpkg": "dist/index.umd.min.js",
-  "dependencies": {},
+  "dependencies": {
+    "@antv/event-emitter": "^0.1.3"
+  },
   "devDependencies": {
@@ -25,0 +28,0 @@ "@commitlint/cli": "^11.0.0",

src/graph.ts

@@ -0,1 +1,2 @@
+import EventEmitter from '@antv/event-emitter';
 import {
@@ -14,4 +15,8 @@ Node,
 } from './types';
+import { doBFS, doDFS } from './utils/traverse';
 
-export class Graph<N extends PlainObject, E extends PlainObject> {
+export class Graph<
+  N extends PlainObject,
+  E extends PlainObject,
+> extends EventEmitter {
   private nodeMap: Map<ID, Node<N>> = new Map();
@@ -21,2 +26,3 @@ private edgeMap: Map<ID, Edge<E>> = new Map();
   private outEdgesMap: Map<ID, Set<Edge<E>>> = new Map();
+  private bothEdgesMap: Map<ID, Set<Edge<E>>> = new Map();
   private treeIndices: TreeIndices<Node<N>> = new Map();
@@ -60,2 +66,3 @@
   constructor(options?: GraphOptions<N, E>) {
+    super();
     if (!options) return;
@@ -104,6 +111,8 @@ if (options.nodes) this.addNodes(options.nodes);
     this.changes = [];
-    this.onChanged({
+    const event = {
       graph: this,
       changes,
-    });
+    };
+    this.emit('changed', event);
+    this.onChanged(event);
   }
@@ -252,5 +261,3 @@
   private checkNodeExistence(id: ID): void {
-    if (!this.hasNode(id)) {
-      throw new Error('Node not found for id: ' + id);
-    }
+    this.getNode(id);
   }
@@ -271,3 +278,2 @@
   public areNeighbors(firstNodeId: ID, secondNodeId: ID): boolean {
-    this.checkNodeExistence(firstNodeId);
     return this.getNeighbors(secondNodeId).some(
@@ -283,4 +289,7 @@ (neighbor) => neighbor.id === firstNodeId,
   public getNode(id: ID): Node<N> {
-    this.checkNodeExistence(id);
-    return this.nodeMap.get(id)!;
+    const node = this.nodeMap.get(id);
+    if (!node) {
+      throw new Error('Node not found for id: ' + id);
+    }
+    return node;
   }
@@ -297,13 +306,12 @@
 
-    const inEdges = this.inEdgesMap.get(id)!;
-    const outEdges = this.outEdgesMap.get(id)!;
-
     if (direction === 'in') {
+      const inEdges = this.inEdgesMap.get(id)!;
       return Array.from(inEdges);
     } else if (direction === 'out') {
+      const outEdges = this.outEdgesMap.get(id)!;
       return Array.from(outEdges);
+    } else {
+      const bothEdges = this.bothEdgesMap.get(id)!;
+      return Array.from(bothEdges);
     }
-
-    const bothEdges = new Set([...inEdges, ...outEdges]);
-    return Array.from(bothEdges);
   }
@@ -324,4 +332,4 @@
     const outEdges = this.getRelatedEdges(id, 'out');
-    const targets = outEdges.map((edge) => edge.target);
-    return Array.from(new Set(targets)).map((id) => this.getNode(id));
+    const targets = outEdges.map((edge) => this.getNode(edge.target));
+    return Array.from(new Set(targets));
   }
@@ -334,4 +342,4 @@
     const inEdges = this.getRelatedEdges(id, 'in');
-    const sources = inEdges.map((edge) => edge.source);
-    return Array.from(new Set(sources)).map((id) => this.getNode(id));
+    const sources = inEdges.map((edge) => this.getNode(edge.source));
+    return Array.from(new Set(sources));
   }
@@ -357,2 +365,3 @@
     this.outEdgesMap.set(node.id, new Set());
+    this.bothEdgesMap.set(node.id, new Set());
     this.treeIndices.forEach((tree) => {
@@ -386,6 +395,4 @@ tree.childrenMap.set(node.id, new Set());
     const node = this.getNode(id);
-    const inEdges = this.inEdgesMap.get(id);
-    const outEdges = this.outEdgesMap.get(id);
-    inEdges?.forEach((edge) => this.doRemoveEdge(edge.id));
-    outEdges?.forEach((edge) => this.doRemoveEdge(edge.id));
+    const bothEdges = this.bothEdgesMap.get(id);
+    bothEdges?.forEach((edge) => this.doRemoveEdge(edge.id));
     this.nodeMap.delete(id);
@@ -569,4 +576,8 @@ this.treeIndices.forEach((tree) => {
     const outEdges = this.outEdgesMap.get(edge.source)!;
+    const bothEdgesOfSource = this.bothEdgesMap.get(edge.source)!;
+    const bothEdgesOfTarget = this.bothEdgesMap.get(edge.target)!;
     inEdges.add(edge);
     outEdges.add(edge);
+    bothEdgesOfSource.add(edge);
+    bothEdgesOfTarget.add(edge);
 
@@ -608,4 +619,8 @@ this.changes.push({ type: 'EdgeAdded', value: edge });
     const inEdges = this.inEdgesMap.get(edge.target)!;
+    const bothEdgesOfSource = this.bothEdgesMap.get(edge.source)!;
+    const bothEdgesOfTarget = this.bothEdgesMap.get(edge.target)!;
     outEdges.delete(edge);
     inEdges.delete(edge);
+    bothEdgesOfSource.delete(edge);
+    bothEdgesOfTarget.delete(edge);
     this.edgeMap.delete(id);
@@ -643,3 +658,5 @@ this.changes.push({ type: 'EdgeRemoved', value: edge });
     this.outEdgesMap.get(oldSource)!.delete(edge);
+    this.bothEdgesMap.get(oldSource)!.delete(edge);
     this.outEdgesMap.get(newSource)!.add(edge);
+    this.bothEdgesMap.get(newSource)!.add(edge);
     edge.source = source;
@@ -667,3 +684,5 @@ this.batch(() => {
     this.inEdgesMap.get(oldTarget)!.delete(edge);
+    this.bothEdgesMap.get(oldTarget)!.delete(edge);
     this.inEdgesMap.get(newTarget)!.add(edge);
+    this.bothEdgesMap.get(newTarget)!.add(edge);
     edge.target = target;
@@ -779,3 +798,3 @@ this.batch(() => {
   private checkTreeExistence(treeKey: string | undefined): void {
-    if (!this.treeIndices.has(treeKey)) {
+    if (!this.hasTreeStructure(treeKey)) {
       throw new Error('Tree structure not found for treeKey: ' + treeKey);
@@ -785,2 +804,6 @@ }
 
+  public hasTreeStructure(treeKey: string | undefined): boolean {
+    return this.treeIndices.has(treeKey);
+  }
+
   /**
@@ -971,2 +994,16 @@ * Attach a new tree structure representing the hierarchy of all nodes in the graph.
   /**
+   * Returns an array of all the ancestor nodes, staring from the parent to the root.
+   */
+  public getAncestors(id: ID, treeKey?: string): Node<N>[] {
+    const ancestors: Node<N>[] = [];
+    let current = this.getNode(id);
+    let parent: Node<N> | null;
+    while (parent = this.getParent(current.id, treeKey)) {
+      ancestors.push(parent);
+      current = parent;
+    }
+    return ancestors;
+  }
+
+  /**
    * Set node parent. If this operation causes a circle, it fails with an error.
@@ -1011,2 +1048,12 @@ * @param id - ID of the child node.
 
+  dfsTree(id: ID, fn: (node: Node<N>) => boolean | void, treeKey?: string) {
+    const navigator = (nodeId: ID) => this.getChildren(nodeId, treeKey);
+    return doDFS(this.getNode(id), new Set(), fn, navigator);
+  }
+
+  bfsTree(id: ID, fn: (node: Node<N>) => boolean | void, treeKey?: string) {
+    const navigator = (nodeId: ID) => this.getChildren(nodeId, treeKey);
+    return doBFS([this.getNode(id)], new Set(), fn, navigator);
+  }
+
   // ================= Graph =================
@@ -1027,38 +1074,28 @@ /**
 
-  private doBFS(
-    queue: Node<N>[],
-    visited: Set<ID>,
-    fn: (node: Node<N>) => void,
-  ) {
-    while (queue.length) {
-      const node = queue.shift()!;
-      fn(node);
-      visited.add(node.id);
-      this.getSuccessors(node.id).forEach((n) => {
-        if (!visited.has(n.id)) {
-          visited.add(n.id);
-          queue.push(n);
-        }
-      });
-    }
+  public bfs(
+    id: ID,
+    fn: (node: Node<N>) => boolean | void,
+    direction: 'in' | 'out' | 'both' = 'out',
+  ): boolean {
+    const navigator = {
+      in: this.getPredecessors.bind(this),
+      out: this.getSuccessors.bind(this),
+      both: this.getNeighbors.bind(this),
+    }[direction];
+    return doBFS([this.getNode(id)], new Set(), fn, navigator);
   }
 
-  public bfs(id: ID, fn: (node: Node<N>) => void): void {
-    this.doBFS([this.getNode(id)], new Set(), fn);
+  public dfs(
+    id: ID,
+    fn: (node: Node<N>) => boolean | void,
+    direction: 'in' | 'out' | 'both' = 'out',
+  ): boolean {
+    const navigator = {
+      in: this.getPredecessors.bind(this),
+      out: this.getSuccessors.bind(this),
+      both: this.getNeighbors.bind(this),
+    }[direction];
+    return doDFS(this.getNode(id), new Set(), fn, navigator);
   }
 
-  private doDFS(node: Node<N>, visited: Set<ID>, fn: (node: Node<N>) => void) {
-    fn(node);
-    visited.add(node.id);
-    this.getSuccessors(node.id).forEach((n) => {
-      if (!visited.has(n.id)) {
-        this.doDFS(n, visited, fn);
-      }
-    });
-  }
-
-  public dfs(id: ID, fn: (node: Node<N>) => void): void {
-    this.doDFS(this.getNode(id), new Set(), fn);
-  }
-
   public clone(): Graph<N, E> {
@@ -1065,0 +1102,0 @@ // Make a shallow copy of nodes and edges.

src/index.ts

 export * from './types';
 export * from './graph';
+export * from './graphView';

src/types.ts

@@ -205,1 +205,26 @@ import type { Graph } from './graph';
 };
+
+/** Options to create a GraphView */
+export interface GraphViewOptions<
+  N extends PlainObject,
+  E extends PlainObject,
+> {
+  /** The original Graph */
+  graph: Graph<N, E>;
+  nodeFilter?: (node: Node<N>) => boolean;
+  edgeFilter?: (edge: Edge<E>, source: Node<N>, target: Node<N>) => boolean;
+  /**
+   * Cache mode of the GraphView. Defaults to 'none'.
+   *
+   * - `none`: Use no cache. Filters are applied when reading data. Fast to create but a bit
+   * slow to read data.
+   *
+   * - `auto`: Automatically cache data when view created or graph changed. Fast to read
+   * data but takes time to build up cache. You should call `stopAutoCache()` to avoid
+   * unnecessary updates if the GraphView is no longer active.
+   *
+   * - `manual` Manage cache manually. `clearCache()` `refreshCache()` `updateCache()`
+   * might be useful.
+   */
+  cache?: 'none' | 'auto' | 'manual';
+}

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

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

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

Improved metrics

Total package byte prevSize

1460862

increased by30.61%

Number of package files

102

increased by25.93%

Lines of code

8924

increased by25%

Number of medium supply chain risk alerts

0

decreased by-100%

Worsened metrics

Dependency count

1

increased byInfinity%

Dependency changes

• + Added@antv/event-emitter@^0.1.3

• + Added@antv/event-emitter@0.1.3(transitive)