Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
graph-data-structure
Advanced tools
graph-data-structure - npm Package Compare versions
Comparing version 4.0.0 to 4.1.0
@@ -67,5 +67,5 @@ type EdgeWeight = number; | ||
| /** | ||
| * Get the properties of the given edge or undefined if none are set. | ||
| * Get the properties of the given edge or undefined if the edge doesn't exist . | ||
| */ | ||
| getEdgeProperties(source: Node, target: Node): LinkProps; | ||
| getEdgeProperties(source: Node, target: Node): LinkProps | undefined; | ||
| /** | ||
@@ -130,4 +130,5 @@ * Adds an edge from the `source` node to `target` node. | ||
| shouldFollow?: (args: { | ||
| source: NoInfer<Node>; | ||
| target: NoInfer<Node>; | ||
| source: Node; | ||
| target: Node; | ||
| props: LinkProps; | ||
| graph: Graph<Node, LinkProps>; | ||
@@ -181,4 +182,5 @@ }) => boolean; | ||
| shouldFollow?: (args: { | ||
| source: NoInfer<Node>; | ||
| target: NoInfer<Node>; | ||
| source: Node; | ||
| target: Node; | ||
| props: LinkProps; | ||
| graph: Graph<Node, LinkProps>; | ||
@@ -185,0 +187,0 @@ }) => boolean; |
@@ -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).graphDataStructure={})}(this,(function(e){"use strict";function t(e,t){if(!1===e||null==e)throw console.warn("Test invariant failed:",t),new Error(t)}class o{nodes=new Set;edges=new Map;edgeWeights=new Map;edgeProperties=new Map;addNode(e){return this.nodes.has(e)||this.nodes.add(e),this.edges.has(e)||this.edges.set(e,new Set),this}removeNode(e){this.edges.delete(e),this.nodes.delete(e);for(const t of this.edges.values())t.delete(e);return this}adjacent(e){return this.edges.get(e)}setEdgeWeight(e,o,r){this.edgeWeights.has(e)||this.edgeWeights.set(e,new Map);const n=this.edgeWeights.get(e);return t(n),n.set(o,r),this}getEdgeWeight(e,t){return this.edgeWeights.get(e)?.get(t)??1}setEdgeProperties(e,o,r){this.edgeProperties.has(e)||this.edgeProperties.set(e,new Map);const n=this.edgeProperties.get(e);return t(n),n.set(o,r),this}getEdgeProperties(e,t){return this.edgeProperties.get(e)?.get(t)}addEdge(e,o,...r){let n,s;const d=r[0];"number"==typeof d&&(n=d),"object"==typeof d&&(n=d.weight,d&&(s=Object.prototype.hasOwnProperty.call(d,"props")?d.props:void 0)),this.addNode(e),this.addNode(o);const i=this.adjacent(e);return t(i),i.add(o),void 0!==n&&this.setEdgeWeight(e,o,n),void 0!==s&&this.setEdgeProperties(e,o,s),this}removeEdge(e,t){return this.edges.get(e)?.delete(t),this.edgeProperties.get(e)?.delete(t),this}hasEdge(e,t){return this.edges.get(e)?.has(t)??!1}}class r extends Error{constructor(e){super(e),Object.setPrototypeOf(this,r.prototype)}}function n(e,t,o,s,d,i){const{errorOnCycle:h=!1,shouldFollow:g}=i;if(s.has(d)&&h)throw new r("Cycle found");o.has(d)||(o.add(d),s.add(d),e.adjacent(d)?.forEach((r=>{(void 0===g||g({source:d,target:r,graph:e}))&&n(e,t,o,s,r,i)})),s.delete(d),t.push(d))}function s(e,t={}){const{sourceNodes:o=Array.from(e.nodes),includeSourceNodes:r=!0}=t,s=new Set,d=new Set,i=[];if(r){for(let r=0;r<o.length;r++){const h=o[r];h&&n(e,i,s,d,h,t)}return i}for(let e=0;e<o.length;e++){const t=o[e];t&&s.add(t)}for(let r=0;r<o.length;r++){const h=o[r];h&&e.adjacent(h)?.forEach((o=>n(e,i,s,d,o,t)))}return i}function d(e){let t,o=1/0;const{d:r,q:n}=e;return n.forEach((e=>{const n=r.get(e)??1/0;n<o&&(o=n,t=e)})),void 0===t?(n.clear(),null):(n.delete(t),t)}function i(e,o,r,n){const{d:s,p:d}=o,i=e.getEdgeWeight(r,n),h=s.get(r),g=s.get(n);t(h,"Missing source distance"),t(g,"Missing target distance"),g>h+i&&(s.set(n,h+i),d.set(n,r))}function h(e,t,o,r){const n=e.nodes,{q:s}=t;for(!function(e,{d:t},o,r){if(e.forEach((e=>{t.set(e,1/0)})),t.get(o)!==1/0)throw new Error("Source node is not in the graph");if(t.get(r)!==1/0)throw new Error("Destination node is not in the graph");t.set(o,0)}(n,t,o,r),function(e,{q:t}){e.forEach((e=>{t.add(e)}))}(n,t);0!==s.size;){const o=d(t);if(null===o)return;e.adjacent(o)?.forEach((r=>{i(e,t,o,r)}))}}function g(e,t,o){const r={d:new Map,p:new Map,q:new Set};return h(e,r,t,o),function(e,t,o,r){const{p:n}=t,s=[];let d=0,i=r;for(;n.has(i);){const t=n.get(i);s.push(i),d+=e.getEdgeWeight(t,i),i=t}if(i!==o)throw new Error("No path found");return s.push(i),s.reverse(),{nodes:s,weight:d}}(e,r,t,o)}function c(e,t,o,r,n,s){return!!r.has(n)||(r.add(n),t.push(n),n==s?(o.push(n),!1):Array.from(e.adjacent(n)??[]).every((n=>c(e,t,o,r,n,s))))}function a(e,t,o,r,n){r.has(n)||(r.add(n),t.indexOf(n)>=0?o.push(n):0==o.length&&e.adjacent(n)?.forEach((n=>{a(e,t,o,r,n)})))}e.CycleError=r,e.Graph=o,e.cloneGraph=function(e){const t=new o;for(let[o,r]of e.edges.entries())r.forEach((r=>{t.addEdge.apply(t,[o,r]);const n=e.edgeWeights.get(o)?.get(r);n&&t.setEdgeWeight(o,r,n);const s=e.getEdgeProperties(o,r);s&&t.setEdgeProperties(o,r,s)}));return t},e.depthFirstSearch=s,e.deserializeGraph=function(...e){const[t,r]=e,n=new o,s=new Map;return t.nodes.forEach((e=>{n.addNode(e),r&&s.set(r(e),e)})),t.links.forEach((e=>{if(!r)return void n.addEdge.apply(n,[e.source,e.target,e.weight,e.props]);const t=s.get(r(e.source))??e.source,o=s.get(r(e.target))??e.target;n.addEdge.apply(n,[t,o,e.weight,e.props])})),n},e.findNodes=function(e,t){const o=[];return e.nodes.forEach((e=>{t(e)&&o.push(e)})),o},e.getFirstNode=function(e,t){for(const o of e.nodes)if(t(o))return o;throw new Error("Node not found.")},e.getNode=function(e,t){const o=[];for(const r of e.nodes)t(r)&&o.push(r);if(0===o.length)throw new Error("Node not found.");if(o.length>1)throw new Error("More than one node found.");return o[0]},e.hasCycle=function(e,t){try{return s(e,{...t,includeSourceNodes:!0,errorOnCycle:!0}),!1}catch(e){if(e instanceof r)return!0;throw e}},e.indegree=function(e,t){let o=0;for(const r of e.edges.values())for(let e of r)e===t&&o++;return o},e.lowestCommonAncestors=function(e,t,o){const r=[],n=[];return c(e,r,n,new Set,t,o)&&a(e,r,n,new Set,o),n},e.outdegree=function(e,t){return e.edges.get(t)?.size??0},e.serializeGraph=function(e,t={}){const{includeDefaultWeight:o=!1}=t,r={nodes:Array.from(e.nodes),links:[]};return r.nodes.forEach((t=>{const n=t;e.adjacent(n)?.forEach((t=>{const s=e.getEdgeWeight(n,t),d=e.getEdgeProperties(n,t),i={source:n,target:t};(1!=s||o)&&(i.weight=s),d&&(i.props=d),r.links.push(i)}))})),r},e.shortestPath=g,e.shortestPaths=function(e,t,o){let r=g(e,t,o);const n=[r],s=r.weight,d=[];for(;r.weight;){const i=r.nodes[0],h=r.nodes[1];e.hasEdge(i,h)&&(d.push({u:i,v:h,weight:e.getEdgeWeight(i,h),props:e.getEdgeProperties(i,h)}),e.removeEdge(i,h)),e.hasEdge(h,i)&&(d.push({u:h,v:i,weight:e.getEdgeWeight(h,i),props:e.getEdgeProperties(i,h)}),e.removeEdge(h,i));try{if(r=g(e,t,o),!r.weight||s<r.weight)break;n.push(r)}catch(e){break}}for(const{u:t,v:o,weight:r,props:n}of d)e.addEdge(t,o,r,n);return n},e.topologicalSort=function(e,t={}){return s(e,{...t,errorOnCycle:!0}).reverse()}})); | ||
| !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).graphDataStructure={})}(this,(function(e){"use strict";function t(e,t){if(!1===e||null==e)throw console.warn("Test invariant failed:",t),new Error(t)}class o{nodes=new Set;edges=new Map;edgeWeights=new Map;edgeProperties=new Map;addNode(e){return this.nodes.has(e)||this.nodes.add(e),this.edges.has(e)||this.edges.set(e,new Set),this}removeNode(e){this.edges.delete(e),this.nodes.delete(e);for(const t of this.edges.values())t.delete(e);return this}adjacent(e){return this.edges.get(e)}setEdgeWeight(e,o,r){this.edgeWeights.has(e)||this.edgeWeights.set(e,new Map);const n=this.edgeWeights.get(e);return t(n),n.set(o,r),this}getEdgeWeight(e,t){return this.edgeWeights.get(e)?.get(t)??1}setEdgeProperties(e,o,r){this.edgeProperties.has(e)||this.edgeProperties.set(e,new Map);const n=this.edgeProperties.get(e);return t(n),n.set(o,r),this}getEdgeProperties(e,t){return this.edgeProperties.get(e)?.get(t)}addEdge(e,o,...r){let n,s;const d=r[0];"number"==typeof d&&(n=d),"object"==typeof d&&(n=d.weight,d&&(s=Object.prototype.hasOwnProperty.call(d,"props")?d.props:void 0)),this.addNode(e),this.addNode(o);const i=this.adjacent(e);return t(i),i.add(o),void 0!==n&&this.setEdgeWeight(e,o,n),void 0!==s&&this.setEdgeProperties(e,o,s),this}removeEdge(e,t){return this.edges.get(e)?.delete(t),this.edgeProperties.get(e)?.delete(t),this}hasEdge(e,t){return this.edges.get(e)?.has(t)??!1}}class r extends Error{constructor(e){super(e),Object.setPrototypeOf(this,r.prototype)}}function n(e,t,o,s,d,i){const{errorOnCycle:g=!1,shouldFollow:h}=i;if(s.has(d)&&g)throw new r("Cycle found");o.has(d)||(o.add(d),s.add(d),e.adjacent(d)?.forEach((r=>{(void 0===h||h({source:d,target:r,graph:e,props:e.getEdgeProperties(d,r)}))&&n(e,t,o,s,r,i)})),s.delete(d),t.push(d))}function s(e,t={}){const{sourceNodes:o=Array.from(e.nodes),includeSourceNodes:r=!0}=t,s=new Set,d=new Set,i=[];if(r){for(let r=0;r<o.length;r++){const g=o[r];g&&n(e,i,s,d,g,t)}return i}for(let e=0;e<o.length;e++){const t=o[e];t&&s.add(t)}for(let r=0;r<o.length;r++){const g=o[r];g&&e.adjacent(g)?.forEach((o=>n(e,i,s,d,o,t)))}return i}function d(e){let t,o=1/0;const{d:r,q:n}=e;return n.forEach((e=>{const n=r.get(e)??1/0;n<o&&(o=n,t=e)})),void 0===t?(n.clear(),null):(n.delete(t),t)}function i(e,o,r,n){const{d:s,p:d}=o,i=e.getEdgeWeight(r,n),g=s.get(r),h=s.get(n);t(g,"Missing source distance"),t(h,"Missing target distance"),h>g+i&&(s.set(n,g+i),d.set(n,r))}function g(e,t,o,r){const n=e.nodes,{q:s}=t;for(!function(e,{d:t},o,r){if(e.forEach((e=>{t.set(e,1/0)})),t.get(o)!==1/0)throw new Error("Source node is not in the graph");if(t.get(r)!==1/0)throw new Error("Destination node is not in the graph");t.set(o,0)}(n,t,o,r),function(e,{q:t}){e.forEach((e=>{t.add(e)}))}(n,t);0!==s.size;){const o=d(t);if(null===o)return;e.adjacent(o)?.forEach((r=>{i(e,t,o,r)}))}}function h(e,t,o){const r={d:new Map,p:new Map,q:new Set};return g(e,r,t,o),function(e,t,o,r){const{p:n}=t,s=[];let d=0,i=r;for(;n.has(i);){const t=n.get(i);s.push(i),d+=e.getEdgeWeight(t,i),i=t}if(i!==o)throw new Error("No path found");return s.push(i),s.reverse(),{nodes:s,weight:d}}(e,r,t,o)}function c(e,t,o,r,n,s){return!!r.has(n)||(r.add(n),t.push(n),n==s?(o.push(n),!1):Array.from(e.adjacent(n)??[]).every((n=>c(e,t,o,r,n,s))))}function a(e,t,o,r,n){r.has(n)||(r.add(n),t.indexOf(n)>=0?o.push(n):0==o.length&&e.adjacent(n)?.forEach((n=>{a(e,t,o,r,n)})))}e.CycleError=r,e.Graph=o,e.cloneGraph=function(e){const t=new o;for(let[o,r]of e.edges.entries())r.forEach((r=>{t.addEdge.apply(t,[o,r]);const n=e.edgeWeights.get(o)?.get(r);n&&t.setEdgeWeight(o,r,n);const s=e.getEdgeProperties(o,r);s&&t.setEdgeProperties(o,r,s)}));return t},e.depthFirstSearch=s,e.deserializeGraph=function(...e){const[t,r]=e,n=new o,s=new Map;return t.nodes.forEach((e=>{n.addNode(e),r&&s.set(r(e),e)})),t.links.forEach((e=>{if(!r)return void n.addEdge.apply(n,[e.source,e.target,e.weight,e.props]);const t=s.get(r(e.source))??e.source,o=s.get(r(e.target))??e.target;n.addEdge.apply(n,[t,o,e.weight,e.props])})),n},e.findNodes=function(e,t){const o=[];return e.nodes.forEach((e=>{t(e)&&o.push(e)})),o},e.getFirstNode=function(e,t){for(const o of e.nodes)if(t(o))return o;throw new Error("Node not found.")},e.getNode=function(e,t){const o=[];for(const r of e.nodes)t(r)&&o.push(r);if(0===o.length)throw new Error("Node not found.");if(o.length>1)throw new Error("More than one node found.");return o[0]},e.hasCycle=function(e,t){try{return s(e,{...t,includeSourceNodes:!0,errorOnCycle:!0}),!1}catch(e){if(e instanceof r)return!0;throw e}},e.indegree=function(e,t){let o=0;for(const r of e.edges.values())for(let e of r)e===t&&o++;return o},e.lowestCommonAncestors=function(e,t,o){const r=[],n=[];return c(e,r,n,new Set,t,o)&&a(e,r,n,new Set,o),n},e.outdegree=function(e,t){return e.edges.get(t)?.size??0},e.serializeGraph=function(e,t={}){const{includeDefaultWeight:o=!1}=t,r={nodes:Array.from(e.nodes),links:[]};return r.nodes.forEach((t=>{const n=t;e.adjacent(n)?.forEach((t=>{const s=e.getEdgeWeight(n,t),d=e.getEdgeProperties(n,t),i={source:n,target:t};(1!=s||o)&&(i.weight=s),d&&(i.props=d),r.links.push(i)}))})),r},e.shortestPath=h,e.shortestPaths=function(e,t,o){let r=h(e,t,o);const n=[r],s=r.weight,d=[];for(;r.weight;){const i=r.nodes[0],g=r.nodes[1];e.hasEdge(i,g)&&(d.push({u:i,v:g,weight:e.getEdgeWeight(i,g),props:e.getEdgeProperties(i,g)}),e.removeEdge(i,g)),e.hasEdge(g,i)&&(d.push({u:g,v:i,weight:e.getEdgeWeight(g,i),props:e.getEdgeProperties(g,i)}),e.removeEdge(g,i));try{if(r=h(e,t,o),!r.weight||s<r.weight)break;n.push(r)}catch(e){break}}for(const{u:t,v:o,weight:r,props:n}of d)e.addEdge(t,o,r,n);return n},e.topologicalSort=function(e,t={}){return s(e,{...t,errorOnCycle:!0}).reverse()}})); |
| { | ||
| "name": "graph-data-structure", | ||
| "version": "4.0.0", | ||
| "version": "4.1.0", | ||
| "description": "A graph data structure with topological sort.", | ||
@@ -49,12 +49,12 @@ "author": "Curran Kelleher", | ||
| "devDependencies": { | ||
| "@rollup/plugin-node-resolve": "15.2.3", | ||
| "@rollup/plugin-node-resolve": "15.3.0", | ||
| "@rollup/plugin-terser": "0.4.4", | ||
| "@types/node": "22.5.4", | ||
| "@types/node": "22.7.9", | ||
| "microbundle": "0.15.1", | ||
| "prettier": "3.3.3", | ||
| "release-it": "17.6.0", | ||
| "rollup": "4.21.3", | ||
| "release-it": "17.10.0", | ||
| "rollup": "4.24.0", | ||
| "rollup-plugin-ts": "3.4.5", | ||
| "typescript": "5.6.2", | ||
| "vitest": "2.0.5" | ||
| "typescript": "5.6.3", | ||
| "vitest": "2.1.3" | ||
| }, | ||
@@ -61,0 +61,0 @@ "files": [ |
118
README.md
@@ -5,3 +5,3 @@ # graph-data-structure | ||
| This library provides a minimalist implementation of a directed graph data structure. Nodes are represented by unique strings. Internally, an [adjacency list](https://en.wikipedia.org/wiki/Adjacency_list) is used to represent nodes and edges. | ||
| This library provides a minimalist implementation of a directed graph data structure. Nodes are represented by unique strings or any other object. Internally, an [adjacency list](https://en.wikipedia.org/wiki/Adjacency_list) is used to represent nodes and edges. | ||
@@ -27,3 +27,3 @@ The primary use case for this library is in implementing [dataflow programming](https://en.wikipedia.org/wiki/Dataflow_programming) or [reactive programming](https://en.wikipedia.org/wiki/Reactive_programming). The key algorithm necessary for these is topological sorting, to get an ordering of nodes such that for each edge (**u** -> **v**), **u** comes before **v** in the sorted order. The topological sorting algorithm exposed here has modifications useful for computing the order in which functions in a data flow graph should be executed, namely specifying source nodes for propagation and specifying to exclude the source nodes themselves from the result. | ||
| ```javascript | ||
| const { Graph } = require('graph-data-structure'); | ||
| import { Graph, serializeGraph, deserializeGraph, topologicalSort, shortestPath } from 'graph-data-structure'; | ||
| ``` | ||
@@ -35,6 +35,6 @@ | ||
| To create a graph instance, invoke **[Graph](#graph)** as a constructor function. | ||
| Start by creating a new **[Graph](#graph)** object. | ||
| ```javascript | ||
| var graph = Graph(); | ||
| var graph = new Graph(); | ||
| ``` | ||
@@ -58,6 +58,6 @@ | ||
| [Topological sorting](https://en.wikipedia.org/wiki/Topological_sorting) can be done by invoking **[topologicalSort](#topological-sort)** like this. | ||
| [Topological sorting](https://en.wikipedia.org/wiki/Topological_sorting) can be done by invoking the standalone function **[topologicalSort](#topological-sort)** like this. | ||
| ```javascript | ||
| graph.topologicalSort(); // Returns ["a", "b", "c"] | ||
| topologicalSort(graph); // Returns ["a", "b", "c"] | ||
| ``` | ||
@@ -74,4 +74,4 @@ | ||
| ```javascript | ||
| var graph = Graph() | ||
| .addEdge('socks', 'shoes') | ||
| const graph = new Graph(); | ||
| graph.addEdge('socks', 'shoes') | ||
| .addEdge('shirt', 'belt') | ||
@@ -86,3 +86,3 @@ .addEdge('shirt', 'tie') | ||
| // prints [ "underpants", "pants", "shirt", "tie", "belt", "jacket", "socks", "shoes" ] | ||
| console.log(graph.topologicalSort()); | ||
| console.log(topologicalSort(graph)); | ||
| ``` | ||
@@ -107,3 +107,3 @@ | ||
| The optional argument _serialized_ is a serialized graph that may have been generated by **[serialize](#serialize)**. If _serialized_ is present, it is deserialized by invoking **[deserialize](#deserialize)**. | ||
| The optional argument _serialized_ is a serialized graph that may have been generated by **[serializeGraph](#serializeGraph)**. If _serialized_ is present, it is deserialized by invoking **[deserializeGraph(mySerializedObject)](#deserializeGraph)**. | ||
@@ -114,8 +114,10 @@ ### Adding and Removing Nodes | ||
| Adds a node to the graph. Returns _graph_ to support method chaining. The argument _node_ is a string identifier that uniquely identifies the node within this graph instance. If a node with the same identifier was already added to the graph, this function does nothing. | ||
| Adds a node to the graph. Returns _graph_ to support method chaining. If the given _node_ was already added to the graph, this function does nothing. | ||
| <a name="remove-node" href="#remove-node">#</a> <i>graph</i>.<b>removeNode</b>(<i>node</i>) | ||
| Removes the specified node. Returns _graph_ to support method chaining. The argument _node_ is a string identifier for the node to remove. This function also removes all edges connected to the specified node, both incoming and outgoing. | ||
| Removes the specified node. Returns _graph_ to support method chaining. The argument _node_ is a string or object identifier for the node to remove. This function also removes all edges connected to the specified node, both incoming and outgoing. | ||
| **Note:** You have to remove them using the exact same reference as when they were created. One can use getNode() to retrieve such reference. | ||
| ### Adding and Removing Edges | ||
@@ -125,3 +127,3 @@ | ||
| Adds an edge from node _u_ to node _v_. Returns _graph_ to support method chaining. The arguments _u_ and _v_ are string identifiers for nodes. This function also adds _u_ and _v_ as nodes if they were not already added. | ||
| Adds an edge from node _u_ to node _v_. Returns _graph_ to support method chaining. The arguments _u_ and _v_ are node references (either objects or strings). This function also adds _u_ and _v_ as nodes if they were not already added. | ||
@@ -132,3 +134,3 @@ The last argument _weight_ (optional) specifies the weight of this edge. | ||
| Removes the edge from node _u_ to node _v_. Returns _graph_ to support method chaining. The arguments _u_ and _v_ are string identifiers for nodes. This function does not remove the nodes _u_ and _v_. Does nothing if the edge does not exist. | ||
| Removes the edge from node _u_ to node _v_. Returns _graph_ to support method chaining. The arguments _u_ and _v_ are node references. This function does not remove the nodes _u_ and _v_. Does nothing if the edge does not exist. | ||
@@ -145,3 +147,3 @@ <a name="has-edge" href="#has-edge">#</a> <i>graph</i>.<b>hasEdge</b>(<i>u</i>, <i>v</i>) | ||
| <a name="get-edge-weight" href="#get-edge-weight">#</a> <i>graph</i>.<b>getEdgeWeight</b>(<i>u</i>, <i>v</i>, <i>weight</i>) | ||
| <a name="get-edge-weight" href="#get-edge-weight">#</a> <i>graph</i>.<b>getEdgeWeight</b>(<i>u</i>, <i>v</i>) | ||
@@ -152,30 +154,16 @@ Gets the _weight_ of the edge from node _u_ to node _v_. If no weight was previously set on this edge, then the value 1 is returned. | ||
| <a name="nodes" href="#nodes">#</a> <i>graph</i>.<b>nodes</b>() | ||
| List all nodes in the graph. Returns an array of node identifier strings. | ||
| <a name="adjacent" href="#adjacent">#</a> <i>graph</i>.<b>adjacent</b>(<i>node</i>) | ||
| Gets the adjacent node list for the specified node. The argument _node_ is a string identifier for a node. Returns an array of node identifier strings. | ||
| Gets the adjacent node list for the specified node. The argument _node_ is a node reference (object or string). Returns a `Set` of adjacent node references or `undefined` if the node is not found. | ||
| The "adjacent node list" is the Array of nodes for which there is an incoming edge from the given node. In other words, for all edges (**u** -> **v**) where **u** is the specified node, all values for **v** are in the adjacent node list. | ||
| <a name="indegree" href="#indegree">#</a> <i>graph</i>.<b>indegree</b>(<i>node</i>) | ||
| Computes the [indegree](https://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree) (number of incoming edges) for the specified _node_. | ||
| <a name="outdegree" href="#outdegree">#</a> <i>graph</i>.<b>outdegree</b>(<i>node</i>) | ||
| Computes the [outdegree](https://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree) (number of outgoing edges) for the specified _node_. | ||
| ### Serialization | ||
| <a name="serialize" href="#serialize">#</a> <i>graph</i>.<b>serialize</b>() | ||
| <a name="serializeGraph" href="#serializeGraph">#</a> <b>serializeGraph</b>(<i>graph</i>) | ||
| Serializes the graph. Returns an object with the following properties. | ||
| - `nodes` An array of objects, each with an `id` property whose value is a node identifier string. | ||
| - `nodes` An array of objects, each representing a node reference. | ||
| - `links` An array of objects representing edges, each with the following properties. | ||
| - `source` The node identifier string of the source node (**u**). | ||
| - `target` The node identifier string of the target node (**v**). | ||
| - `source` The node reference of the source node (**u**). | ||
| - `target` The node reference of the target node (**v**). | ||
| - `weight` The weight of the edge between the source and target nodes. | ||
@@ -186,63 +174,32 @@ | ||
| ```javascript | ||
| var graph = Graph(); | ||
| var graph = new Graph(); | ||
| graph.addEdge('a', 'b'); | ||
| graph.addEdge('b', 'c'); | ||
| var serialized = graph.serialize(); | ||
| var serialized = serializeGraph(graph); | ||
| ``` | ||
| The following will be the value of `serialized`. | ||
| <a name="deserializeGraph" href="#deserializeGraph">#</a> <b>deserializeGraph</b>(<i>serialized</i>) | ||
| ```json | ||
| { | ||
| "nodes": [{ "id": "a" }, { "id": "b" }, { "id": "c" }], | ||
| "links": [ | ||
| { "source": "a", "target": "b", "weight": 1 }, | ||
| { "source": "b", "target": "c", "weight": 1 } | ||
| ] | ||
| } | ||
| ``` | ||
| Deserializes the given serialized graph. Returns a new _graph_. The argument _serialized_ is a graph representation with the structure described in **[serializeGraph](#serializeGraph)**. | ||
| This representation conforms to the convention of graph representation when working with D3.js force layouts. See also [d3.simulation.nodes](https://github.com/d3/d3-force#simulation_nodes) and [d3.forceLinks](https://github.com/d3/d3-force#links). | ||
| <a name="deserialize" href="#deserialize">#</a> <i>graph</i>.<b>deserialize</b>(<i>serialized</i>) | ||
| Deserializes the given serialized graph. Returns _graph_ to support method chaining. The argument _serialized_ is a graph representation with the structure described in **[serialize](#serialize)**. This function iterates over the serialized graph and adds the nodes and links it represents by invoking **[addNode](#add-node)** and **[addEdge](#add-edge)**. The output from **[serialize](#serialize)** can be used as the input to **deserialize**. | ||
| ### Graph Algorithms | ||
| <a name="dfs" href="#dfs">#</a> <i>graph</i>.<b>depthFirstSearch</b>([<i>sourceNodes</i>][, <i>includesourcenodes</i>][, <i>errorOnCycle</i>]) | ||
| <a name="topological-sort" href="#topological-sort">#</a> <b>topologicalSort</b>(<i>graph</i>) | ||
| Performs [Depth-first Search](https://en.wikipedia.org/wiki/Depth-first_search). Returns an array of node identifier strings. The returned array includes nodes visited by the algorithm in the order in which they were visited. Implementation inspired by pseudocode from Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604. | ||
| Performs [Topological Sort]( | ||
| Arguments: | ||
| https://en.wikipedia.org/wiki/Topological_sorting). Returns an array of node identifier strings. The returned array includes nodes in topologically sorted order. This means that for each visited edge (**u** -> **v**), **u** comes before **v** in the topologically sorted order. | ||
| - _sourceNodes_ (optional) - An array of node identifier strings. This specifies the subset of nodes to use as the sources of the depth-first search. If _sourceNodes_ is not specified, all **[nodes](#nodes)** in the graph are used as source nodes. | ||
| - _includeSourceNodes_ (optional) - A boolean specifying whether or not to include the source nodes in the returned array. If _includeSourceNodes_ is not specified, it is treated as `true` (all source nodes are included in the returned array). | ||
| - _errorOnCycle_ (optional) - A boolean indicating that a `CycleError` should be thrown whenever a cycle is first encountered. Defaults to `false`. | ||
| Note: this function raises a `CycleError` when the input is not a DAG. | ||
| <a name="has-cycle" href="#has-cycle">#</a> <i>graph</i>.<b>hasCycle</b>() | ||
| <a name="shortest-path" href="#shortest-path">#</a> <b>shortestPath</b>(<i>graph</i>, <i>sourceNode</i>, <i>destinationNode</i>) | ||
| Checks if the graph has any cycles. Returns `true` if it does and `false` otherwise. | ||
| Performs [Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). Returns an object with two properties: `nodes`, an array of node references representing the path, and `weight`, the total weight of the path. | ||
| <a name="lca" href="#lca">#</a> <i>graph</i>.<b>lowestCommonAncestors</b>([<i>node1</i>][, <i>node2</i>]) | ||
| ```javascript | ||
| var result = shortestPath(graph, 'a', 'c'); | ||
| console.log(result.nodes); // Prints the array of nodes in the shortest path | ||
| console.log(result.weight); // Prints the total weight of the path | ||
| ``` | ||
| Performs search of [Lowest common ancestors](https://en.wikipedia.org/wiki/Lowest_common_ancestor). Returns an array of node identifier strings. | ||
| Arguments: | ||
| - _node1_ (required) - First node. | ||
| - _node2_ (required) - Second node. | ||
| <a name="topological-sort" href="#topological-sort">#</a> <i>graph</i>.<b>topologicalSort</b>([<i>sourceNodes</i>][, <i>includesourcenodes</i>]) | ||
| Performs [Topological Sort](https://en.wikipedia.org/wiki/Topological_sorting). Returns an array of node identifier strings. The returned array includes nodes in topologically sorted order. This means that for each visited edge (**u** -> **v**), **u** comes before **v** in the topologically sorted order. Amazingly, this comes from simply reversing the result from depth first search. Inspired by by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613. | ||
| See **[depthFirstSearch](#dfs)** for documentation of the arguments _sourceNodes_ and _includeSourceNodes_. | ||
| Note: this function raises a `CycleError` when the input is not a DAG. | ||
| <a name="shortest-path" href="#shortest-path">#</a> <i>graph</i>.<b>shortestPath</b>(<i>sourceNode</i>, <i>destinationNode</i>) | ||
| Performs [Dijkstras Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). Returns an array of node identifier strings. The returned array includes the nodes of the shortest path from source to destination node. The returned array also contains a `weight` property, which is the total weight over all edges in the path. Inspired by by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 658. | ||
| <p align="center"> | ||
@@ -253,1 +210,2 @@ <a href="https://datavis.tech/"> | ||
| </p> | ||
| ``` |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis 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
LicenseThis 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 riskPackage 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
- Lines of code
- increased by0.64%
314
- Number of medium supply chain risk alerts
- decreased by-100%
0
Worsened metrics
- Total package byte prevSize
- decreased by-5.32%
55485
- Number of lines in readme file
- decreased by-17.5%
198
No dependency changes