Graphology Shortest Path

Shortest path functions for graphology.

Installation

``
npm install graphology-shortest-path
`

Usage

- Unweighted
- bidirectional
- singleSource
- singleSourceLength
- undirectedSingleSourceLength
- Dijkstra
- bidirectional
- singleSource
- A-star
- bidirectional
- Utilities
- edgePathFromNodePath

Unweighted

$3

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

`js
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.

$3

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

`js
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.

$3

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

`js
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.

$3

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.

`js
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.

`js
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.

`js
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.

`js
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

$3

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

`js
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.