Package Exports

graphology-shortest-path
graphology-shortest-path/dijkstra
graphology-shortest-path/dijkstra.js
graphology-shortest-path/index.js
graphology-shortest-path/indexed-brandes
graphology-shortest-path/indexed-brandes.js
graphology-shortest-path/unweighted
graphology-shortest-path/unweighted.js

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (graphology-shortest-path) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

Graphology Shortest Path

Shortest path functions for graphology.

Installation

npm install graphology-shortest-path

Unweighted

bidirectional

Returns the shortest path in the graph between source & target or null if such a path does not exist.

import {bidirectional} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import {bidirectional} from 'graphology-shortest-path/unweighted';

// Returning the shortest path between source & target
const path = bidirectional(graph, source, target);

Arguments

graph Graph: a graphology instance.
source any: source node.
target any: target node.

singleSource

Return a map of every shortest path between the given source & all the nodes of the graph.

import {singleSource} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import {singleSource} from 'graphology-shortest-path/unweighted';

// Returning every shortest path between source & every node of the graph
const paths = singleSource(graph, source);

Arguments

graph Graph: a graphology instance.
source any: source node.

singleSourceLength

Return a map of every shortest path length between the given source & all the nodes of the graph.

import {singleSourceLength} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import {singleSourceLength} from 'graphology-shortest-path/unweighted';

// Returning every shortest path between source & every node of the graph
const paths = singleSourceLength(graph, source);

Arguments

graph Graph: a graphology instance.
source any: source node.

undirectedSingleSourceLength

Return a map of every shortest path length between the given source & all the nodes of the graph. This is basically the same as singleSourceLength except that it will consider any given graph as undirected when traversing.

import {undirectedSingleSourceLength} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import {undirectedSingleSourceLength} from 'graphology-shortest-path/unweighted';

// Returning every shortest path between source & every node of the graph
const paths = undirectedSingleSourceLength(graph, source);

Arguments

graph Graph: a graphology instance.
source any: source node.

Dijkstra

bidirectional

Returns the shortest path in the weighted graph between source & target or null if such a path does not exist.

import {dijkstra} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import dijkstra from 'graphology-shortest-path/dijkstra';

// Returning the shortest path between source & target
const path = dijkstra.bidirectional(graph, source, target);

// If you store edges' weight in custom attribute
const path = dijkstra.bidirectional(graph, source, target, 'customWeight');

// Using a custom weight getter function
const path = dijkstra.bidirectional(
  graph,
  source,
  target,
  (_, attr) => attr.importance
);

Arguments

graph Graph: a graphology instance.
source any: source node.
target any: target node.
getEdgeWeight ?string|function [weight]: name of the weight attribute or getter function.

singleSource

Return a map of every shortest path between the given source & all the nodes of the weighted graph.

import {dijkstra} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import dijkstra from 'graphology-shortest-path/dijkstra';

// Returning every shortest path between source & every node of the graph
const paths = dijkstra.singleSource(graph, source);

// If you store edges' weight in custom attribute
const paths = dijkstra.singleSource(graph, source, 'customWeight');

// Using a custom weight getter function
const path = dijkstra.singleSource(graph, source, (_, attr) => attr.importance);

Arguments

graph Graph: a graphology instance.
source any: source node.
getEdgeWeight ?string|function [weight]: name of the weight attribute or getter function.

A-star

bidirectional

Returns the shortest path in the weighted graph between source & target or null if such a path does not exist.

import {astar} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import astar from 'graphology-shortest-path/astar';

// Returning the shortest path between source & target
const path = astar.bidirectional(
  graph,
  source,
  target,
  (_, attr) => attr.importance
  (node, finalTarget) => euclideanDistance(points[node], points[finalTarget])
);

Arguments

graph Graph: a graphology instance.
source any: source node.
target any: target node.
getEdgeWeight ?string|function [weight]: name of the weight attribute or getter function.
heuristic ?function: heuristic function to compute distance between current node and final target.

Utilities

edgePathFromNodePath

Helper function that can convert a node path to an edge path.

import {edgePathFromNodePath} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import {edgePathFromNodePath} from 'graphology-shortest-path/utils';

const edgePath = edgePathFromNodePath(graph, nodePath);

Arguments

graph Graph: a graphology instance.
nodePath Array: node path to convert.