graphology-shortest-path - npm Package Compare versions

Comparing version 1.5.2 to 2.0.0

dijkstra.d.ts

@@ -1,2 +0,3 @@
-import Graph from 'graphology-types';
+import Graph, {Attributes} from 'graphology-types';
+import {MinimalEdgeMapper} from 'graphology-utils/getters';
 
@@ -11,18 +12,34 @@ type SingleSourceDijkstraResult = {[key: string]: string[]};
 
-interface IDijkstra {
-  bidirectional(
-    graph: Graph,
-    source: string,
-    target: string,
-    weightAttribute: string
-  ): BidirectionalDijstraResult;
-  singleSource(
-    graph: Graph,
-    source: string,
-    weightAttribute: string
-  ): SingleSourceDijkstraResult;
-  brandes(graph: Graph, source: string, weightAttribute: string): BrandesResult;
-}
+export function bidirectional<
+  NodeAttributes extends Attributes = Attributes,
+  EdgeAttributes extends Attributes = Attributes
+>(
+  graph: Graph<NodeAttributes, EdgeAttributes>,
+  source: unknown,
+  target: unknown,
+  getEdgeWeight?:
+    | keyof EdgeAttributes
+    | MinimalEdgeMapper<number, EdgeAttributes>
+): BidirectionalDijstraResult;
 
-declare const dijkstra: IDijkstra;
-export default dijkstra;
+export function singleSource<
+  NodeAttributes extends Attributes = Attributes,
+  EdgeAttributes extends Attributes = Attributes
+>(
+  graph: Graph<NodeAttributes, EdgeAttributes>,
+  source: unknown,
+  getEdgeWeight?:
+    | keyof EdgeAttributes
+    | MinimalEdgeMapper<number, EdgeAttributes>
+): SingleSourceDijkstraResult;
+
+export function brandes<
+  NodeAttributes extends Attributes = Attributes,
+  EdgeAttributes extends Attributes = Attributes
+>(
+  graph: Graph<NodeAttributes, EdgeAttributes>,
+  source: unknown,
+  getEdgeWeight?:
+    | keyof EdgeAttributes
+    | MinimalEdgeMapper<number, EdgeAttributes>
+): BrandesResult;

dijkstra.js

@@ -7,4 +7,6 @@ /**
  */
-var isGraph = require('graphology-utils/is-graph'),
-  Heap = require('mnemonist/heap');
+var isGraph = require('graphology-utils/is-graph');
+var createEdgeWeightGetter =
+  require('graphology-utils/getters').createEdgeWeightGetter;
+var Heap = require('mnemonist/heap');
 
@@ -14,5 +16,3 @@ /**
  */
-var DEFAULTS = {
-  weightAttribute: 'weight'
-};
+var DEFAULT_WEIGHT_ATTRIBUTE = 'weight';
 
@@ -53,9 +53,9 @@ function DIJKSTRA_HEAP_COMPARATOR(a, b) {
  *
- * @param  {Graph}  graph           - The graphology instance.
- * @param  {string} source          - Source node.
- * @param  {string} target          - Target node.
- * @param  {string} weightAttribute - Name of the weight attribute.
- * @param  {array}                  - The found path if any and its cost.
+ * @param  {Graph}  graph         - The graphology instance.
+ * @param  {string} source        - Source node.
+ * @param  {string} target        - Target node.
+ * @param  {string} getEdgeWeight - Name of the weight attribute or getter function.
+ * @param  {array}                - The found path if any and its cost.
  */
-function abstractBidirectionalDijkstra(graph, source, target, weightAttribute) {
+function abstractBidirectionalDijkstra(graph, source, target, getEdgeWeight) {
   source = '' + source;
@@ -84,12 +84,6 @@ target = '' + target;
 
-  weightAttribute = weightAttribute || DEFAULTS.weightAttribute;
+  getEdgeWeight = createEdgeWeightGetter(
+    getEdgeWeight || DEFAULT_WEIGHT_ATTRIBUTE
+  ).fromMinimalEntry;
 
-  var getWeight = function (edge) {
-    var weight = graph.getEdgeAttribute(edge, weightAttribute);
-
-    if (typeof weight !== 'number' || isNaN(weight)) return 1;
-
-    return weight;
-  };
-
   if (source === target) return [0, [source]];
@@ -149,3 +143,3 @@
       u = graph.opposite(v, e);
-      cost = distances[dir][v] + getWeight(e);
+      cost = distances[dir][v] + getEdgeWeight(e, graph.getEdgeAttributes(e));
 
@@ -185,9 +179,9 @@ if (u in distances[dir] && cost < distances[dir][u]) {
  *
- * @param  {Graph}  graph           - The graphology instance.
- * @param  {array}  sources         - A list of sources.
- * @param  {string} weightAttribute - Name of the weight attribute.
- * @param  {number} cutoff          - Maximum depth of the search.
- * @param  {string} target          - Optional target to reach.
- * @param  {object} paths           - Optional paths object to maintain.
- * @return {object}                 - Returns the paths.
+ * @param  {Graph}  graph         - The graphology instance.
+ * @param  {array}  sources       - A list of sources.
+ * @param  {string} getEdgeWeight - Name of the weight attribute or getter function.
+ * @param  {number} cutoff        - Maximum depth of the search.
+ * @param  {string} target        - Optional target to reach.
+ * @param  {object} paths         - Optional paths object to maintain.
+ * @return {object}               - Returns the paths.
  */
@@ -197,3 +191,3 @@ function abstractDijkstraMultisource(
   sources,
-  weightAttribute,
+  getEdgeWeight,
   cutoff,
@@ -215,13 +209,6 @@ target,
 
-  weightAttribute = weightAttribute || DEFAULTS.weightAttribute;
+  getEdgeWeight = createEdgeWeightGetter(
+    getEdgeWeight || DEFAULT_WEIGHT_ATTRIBUTE
+  ).fromMinimalEntry;
 
-  // Building necessary functions
-  var getWeight = function (edge) {
-    var weight = graph.getEdgeAttribute(edge, weightAttribute);
-
-    if (typeof weight !== 'number' || isNaN(weight)) return 1;
-
-    return weight;
-  };
-
   var distances = {},
@@ -268,3 +255,3 @@ seen = {},
       u = graph.opposite(v, e);
-      cost = getWeight(e) + distances[v];
+      cost = getEdgeWeight(e, graph.getEdgeAttributes(e)) + distances[v];
 
@@ -293,11 +280,11 @@ if (cutoff && cost > cutoff) continue;
  *
- * @param  {Graph}  graph           - The graphology instance.
- * @param  {string} source          - Source node.
- * @param  {string} weightAttribute - Name of the weight attribute.
- * @return {object}                 - An object of found paths.
+ * @param  {Graph}  graph         - The graphology instance.
+ * @param  {string} source        - Source node.
+ * @param  {string} getEdgeWeight - Name of the weight attribute or getter function.
+ * @return {object}               - An object of found paths.
  */
-function singleSourceDijkstra(graph, source, weightAttribute) {
+function singleSourceDijkstra(graph, source, getEdgeWeight) {
   var paths = {};
 
-  abstractDijkstraMultisource(graph, [source], weightAttribute, 0, null, paths);
+  abstractDijkstraMultisource(graph, [source], getEdgeWeight, 0, null, paths);
 
@@ -307,9 +294,4 @@ return paths;
 
-function bidirectionalDijkstra(graph, source, target, weightAttribute) {
-  return abstractBidirectionalDijkstra(
-    graph,
-    source,
-    target,
-    weightAttribute
-  )[1];
+function bidirectionalDijkstra(graph, source, target, getEdgeWeight) {
+  return abstractBidirectionalDijkstra(graph, source, target, getEdgeWeight)[1];
 }
@@ -325,11 +307,14 @@
  *
- * @param  {Graph}  graph           - Target graph.
- * @param  {any}    source          - Source node.
- * @param  {string} weightAttribute - Name of the weight attribute.
- * @return {array}                  - [Stack, Paths, Sigma]
+ * @param  {Graph}  graph         - Target graph.
+ * @param  {any}    source        - Source node.
+ * @param  {string} getEdgeWeight - Name of the weight attribute or getter function.
+ * @return {array}                - [Stack, Paths, Sigma]
  */
-function brandes(graph, source, weightAttribute) {
+function brandes(graph, source, getEdgeWeight) {
   source = '' + source;
-  weightAttribute = weightAttribute || DEFAULTS.weightAttribute;
 
+  getEdgeWeight = createEdgeWeightGetter(
+    getEdgeWeight || DEFAULT_WEIGHT_ATTRIBUTE
+  ).fromMinimalEntry;
+
   var S = [],
@@ -386,3 +371,3 @@ P = {},
       w = graph.opposite(v, e);
-      cost = dist + (graph.getEdgeAttribute(e, weightAttribute) || 1);
+      cost = dist + getEdgeWeight(e, graph.getEdgeAttributes(e));
 
@@ -407,6 +392,4 @@ if (!(w in D) && (!(w in seen) || cost < seen[w])) {
  */
-module.exports = {
-  bidirectional: bidirectionalDijkstra,
-  singleSource: singleSourceDijkstra,
-  brandes: brandes
-};
+exports.bidirectional = bidirectionalDijkstra;
+exports.singleSource = singleSourceDijkstra;
+exports.brandes = brandes;

index.d.ts

@@ -1,2 +0,11 @@
-export {default as dijkstra} from './dijkstra';
-export {default as unweighted} from './unweighted';
+export * as dijkstra from './dijkstra';
+export * as unweighted from './unweighted';
+
+export {
+  singleSource,
+  singleSourceLength,
+  bidirectional,
+  brandes
+} from './unweighted';
+
+export {edgePathFromNodePath} from './utils';

index.js

@@ -7,8 +7,14 @@ /**
  */
-var dijkstra = require('./dijkstra.js');
 var unweighted = require('./unweighted.js');
+var utils = require('./utils.js');
 
-unweighted.dijkstra = dijkstra;
-unweighted.unweighted = unweighted;
+exports.unweighted = unweighted;
+exports.dijkstra = require('./dijkstra.js');
 
-module.exports = unweighted;
+exports.bidirectional = unweighted.bidirectional;
+exports.singleSource = unweighted.singleSource;
+exports.singleSourceLength = unweighted.singleSourceLength;
+exports.undirectedSingleSourceLength = unweighted.undirectedSingleSourceLength;
+exports.brandes = unweighted.brandes;
+
+exports.edgePathFromNodePath = utils.edgePathFromNodePath;

indexed-brandes.d.ts

@@ -1,7 +0,8 @@
-import Graph from 'graphology-types';
+import Graph, {Attributes} from 'graphology-types';
+import {MinimalEdgeMapper} from 'graphology-utils/getters';
 import FixedStack from 'mnemonist/fixed-stack';
 import {
-  OutboundNeighborhoodIndex,
-  WeightedOutboundNeighborhoodIndex
-} from 'graphology-indices/neighborhood/outbound';
+  NeighborhoodIndex,
+  WeightedNeighborhoodIndex
+} from 'graphology-indices/neighborhood';
 
@@ -18,8 +19,16 @@ type IndexedBrandesResult = [
   (graph: Graph): IndexedBrandesFunction;
-  index: OutboundNeighborhoodIndex;
+  index: NeighborhoodIndex;
 }
 
-interface ICreateDijkstraIndexedBrandes {
-  (graph: Graph, weightAttribute?: string): IndexedBrandesFunction;
-  index: WeightedOutboundNeighborhoodIndex;
+interface ICreateDijkstraIndexedBrandes<
+  NodeAttributes extends Attributes = Attributes,
+  EdgeAttributes extends Attributes = Attributes
+> {
+  (
+    graph: Graph<NodeAttributes, EdgeAttributes>,
+    getEdgeWeight?:
+      | keyof EdgeAttributes
+      | MinimalEdgeMapper<number, EdgeAttributes>
+  ): IndexedBrandesFunction;
+  index: WeightedNeighborhoodIndex;
 }
@@ -26,0 +35,0 @@

indexed-brandes.js

@@ -14,4 +14,4 @@ /**
 
-var NeighborhoodIndex = neighborhoodIndices.NeighborhoodIndex,
-  WeightedNeighborhoodIndex = neighborhoodIndices.WeightedNeighborhoodIndex;
+var NeighborhoodIndex = neighborhoodIndices.NeighborhoodIndex;
+var WeightedNeighborhoodIndex = neighborhoodIndices.WeightedNeighborhoodIndex;
 
@@ -114,4 +114,4 @@ /**
  *
- * @param  {Graph}    graph           - The graphology instance.
- * @param  {string}   weightAttribute - Name of the weight attribute.
+ * @param  {Graph}    graph         - The graphology instance.
+ * @param  {string}   getEdgeWeight - Name of the weight attribute or getter function.
  * @return {function}
@@ -121,8 +121,9 @@ */
   graph,
-  weightAttribute
+  getEdgeWeight
 ) {
-  if (arguments.length < 2) weightAttribute = 'weight';
+  var neighborhoodIndex = new WeightedNeighborhoodIndex(
+    graph,
+    getEdgeWeight || 'weight'
+  );
 
-  var neighborhoodIndex = new WeightedNeighborhoodIndex(graph, weightAttribute);
-
   var neighborhood = neighborhoodIndex.neighborhood,
@@ -129,0 +130,0 @@ weights = neighborhoodIndex.weights,

package.json

 {
   "name": "graphology-shortest-path",
-  "version": "1.5.2",
+  "version": "2.0.0",
   "description": "Shortest path functions for graphology.",
@@ -12,3 +12,4 @@ "main": "index.js",
     "indexed-brandes.js",
-    "unweighted.js"
+    "unweighted.js",
+    "utils.js"
   ],
@@ -44,6 +45,6 @@ "scripts": {
     "@yomguithereal/helpers": "^1.1.1",
-    "graphology-indices": "^0.16.0",
-    "graphology-utils": "^2.1.2",
-    "mnemonist": "^0.38.1"
+    "graphology-indices": "^0.16.3",
+    "graphology-utils": "^2.4.3",
+    "mnemonist": "^0.39.0"
   }
 }

README.md

@@ -14,3 +14,2 @@ # Graphology Shortest Path
 - [Unweighted](#unweighted)
-  - [shortestPath](#shortestpath)
   - [bidirectional](#bidirectional)
@@ -20,34 +19,10 @@ - [singleSource](#singlesource)
   - [undirectedSingleSourceLength](#undirectedsinglesourcelength)
-  - [brandes](#brandes)
 - [Dijkstra](#dijkstra)
   - [bidirectional](#dijkstra-bidirectional)
   - [singleSource](#dijkstra-singlesource)
-  - [brandes](#dijkstra-brandes)
+- [Utilities](#utilities)
+  - [edgePathFromNodePath](#edgepathfromnodepath)
 
 ## Unweighted
 
-### shortestPath
-
-Returns the shortest path in the graph between source & target or `null` if such a path does not exist (same as [bidirectional](#bidirectional)).
-
-If you only pass the source & omit the target, will return a map of every shortest path between the source & all the nodes of the graph (same as [singleSource](#singlesource)).
-
-```js
-import shortestPath from 'graphology-shortest-path';
-// Alternatively, if you want to load only the relevant code
-import shortestPath from 'graphology-shortest-path/unweighted';
-
-// Returning the shortest path between source & target
-const path = shortestPath(graph, source, target);
-
-// Returning every shortest path between source & every node of the graph
-const paths = shortestPath(graph, source);
-```
-
-_Arguments_
-
-- **graph** _Graph_: a `graphology` instance.
-- **source** _any_: source node.
-- **target** _?any_: optionally, target node.
-
 ### bidirectional
@@ -126,20 +101,2 @@
 
-### brandes
-
-Apply Ulrik Brandes' method to collect single source shortest paths from the given node. This is mostly used to compute betweenness centrality.
-
-```js
-import {brandes} from 'graphology-shortest-path';
-// Alternatively, if you want to load only the relevant code
-import {brandes} from 'graphology-shortest-path/unweighted';
-
-// Returning S, P & sigma
-const [S, P, sigma] = brandes(graph, source);
-```
-
-_Arguments_
-
-- **graph** _Graph_: a `graphology` instance.
-- **source** _any_: source node.
-
 ## Dijkstra
@@ -160,3 +117,11 @@
 // If you store edges' weight in custom attribute
-const paths = dijkstra.bidirectional(graph, source, target, 'customWeight');
+const path = dijkstra.bidirectional(graph, source, target, 'customWeight');
+
+// Using a custom weight getter function
+const path = dijkstra.bidirectional(
+  graph,
+  source,
+  target,
+  (_, attr) => attr.importance
+);
 ```
@@ -169,3 +134,3 @@
 - **target** _any_: target node.
-- **weightAttribute** _?string_ [`weight`]: name of the weight attribute.
+- **getEdgeWeight** _?string\|function_ [`weight`]: name of the weight attribute or getter function.
 
@@ -186,2 +151,5 @@ <h3 id="dijkstra-singlesource">singleSource</h3>
 const paths = dijkstra.singleSource(graph, source, 'customWeight');
+
+// Using a custom weight getter function
+const path = dijkstra.singleSource(graph, source, (_, attr) => attr.importance);
 ```
@@ -193,18 +161,16 @@
 - **source** _any_: source node.
-- **weightAttribute** _?string_ [`weight`]: name of the weight attribute.
+- **getEdgeWeight** _?string\|function_ [`weight`]: name of the weight attribute or getter function.
 
-<h3 id="dijkstra-brandes">brandes</h3>
+## Utilities
 
-Apply Ulrik Brandes' method to collect single source shortest paths from the given node. This is mostly used to compute betweenness centrality.
+### edgePathFromNodePath
 
+Helper function that can convert a node path to an edge path.
+
 ```js
-import {dijkstra} from 'graphology-shortest-path';
+import {edgePathFromNodePath} from 'graphology-shortest-path';
 // Alternatively, if you want to load only the relevant code
-import dijkstra from 'graphology-shortest-path/dijkstra';
+import {edgePathFromNodePath} from 'graphology-shortest-path/utils';
 
-// Returning S, P & sigma
-const [S, P, sigma] = dijkstra.brandes(graph, source);
-
-// If you store edges' weight in custom attribute
-const [S, P, sigma] = dijkstra.brandes(graph, source, 'customWeight');
+const edgePath = edgePathFromNodePath(graph, nodePath);
 ```
@@ -215,3 +181,2 @@
 - **graph** _Graph_: a `graphology` instance.
-- **source** _any_: source node.
-- **weightAttribute** _?string_ [`weight`]: name of the weight attribute.
+- **edgePath** _Array_: edge path to convert.

unweighted.d.ts

@@ -13,18 +13,18 @@ import Graph from 'graphology-types';
 
-interface IUnweightedShortestPath {
-  (graph: Graph, source: unknown): ShortestPathMapping;
-  (graph: Graph, source: unknown, target: unknown): ShortestPath | null;
+export function bidirectional(
+  graph: Graph,
+  source: unknown,
+  target: unknown
+): ShortestPath | null;
 
-  bidirectional(
-    graph: Graph,
-    source: unknown,
-    target: unknown
-  ): ShortestPath | null;
-  singleSource(graph: Graph, source: unknown): ShortestPathMapping;
-  singleSourceLength(graph: Graph, source: unknown): ShortestPathLengthMapping;
-  brandes(graph: Graph, source: unknown): BrandesResult;
-}
+export function singleSource(
+  graph: Graph,
+  source: unknown
+): ShortestPathMapping;
 
-declare const shortestPath: IUnweightedShortestPath;
+export function singleSourceLength(
+  graph: Graph,
+  source: unknown
+): ShortestPathLengthMapping;
 
-export default shortestPath;
+export function brandes(graph: Graph, source: unknown): BrandesResult;

unweighted.js

@@ -8,5 +8,5 @@ /**
  */
-var isGraph = require('graphology-utils/is-graph'),
-  Queue = require('mnemonist/queue'),
-  extend = require('@yomguithereal/helpers/extend');
+var isGraph = require('graphology-utils/is-graph');
+var Queue = require('mnemonist/queue');
+var extend = require('@yomguithereal/helpers/extend');
 
@@ -275,17 +275,2 @@ /**
 /**
- * Main polymorphic function taking either only a source or a
- * source/target combo.
- *
- * @param  {Graph}  graph      - Target graph.
- * @param  {any}    source     - Source node.
- * @param  {any}    [target]   - Target node.
- * @return {array|object|null} - The map of found paths.
- */
-function shortestPath(graph, source, target) {
-  if (arguments.length < 3) return singleSource(graph, source);
-
-  return bidirectional(graph, source, target);
-}
-
-/**
  * Function using Ulrik Brandes' method to map single source shortest paths
@@ -363,8 +348,6 @@ * from selected node.
  */
-shortestPath.bidirectional = bidirectional;
-shortestPath.singleSource = singleSource;
-shortestPath.singleSourceLength = singleSourceLength;
-shortestPath.undirectedSingleSourceLength = undirectedSingleSourceLength;
-shortestPath.brandes = brandes;
-
-module.exports = shortestPath;
+exports.bidirectional = bidirectional;
+exports.singleSource = singleSource;
+exports.singleSourceLength = singleSourceLength;
+exports.undirectedSingleSourceLength = undirectedSingleSourceLength;
+exports.brandes = brandes;

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

Improved metrics

Total package byte prevSize

34119

increased by0.59%

Number of package files

13

increased by18.18%

Lines of code

903

increased by6.49%

Worsened metrics

Number of lines in readme file

175

decreased by-16.67%

Dependency changes

• - Removedmnemonist@0.38.5(transitive)

• Updatedgraphology-indices@^0.16.3

• Updatedgraphology-utils@^2.4.3

• Updatedmnemonist@^0.39.0