Package Exports

graphology-shortest-path
graphology-shortest-path/dijkstra
graphology-shortest-path/unweighted

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

shortestPath

Returns the shortest path in the graph between source & target or null if such a path does not exist (same as 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).

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

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.

brandes

Apply Ulrik Brandes' method to collect single source shortest paths from the given node. This is mostly used to compute betweenness centrality.

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

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 paths = dijkstra.bidirectional(graph, source, target, 'customWeight');

Arguments

graph Graph: a graphology instance.
source any: source node.
target any: target node.
weightAttribute ?string [weight]: name of the weight attribute.

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');

Arguments

graph Graph: a graphology instance.
source any: source node.
weightAttribute ?string [weight]: name of the weight attribute.

brandes

Apply Ulrik Brandes' method to collect single source shortest paths from the given node. This is mostly used to compute betweenness centrality.

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

// 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');

Arguments

graph Graph: a graphology instance.
source any: source node.
weightAttribute ?string [weight]: name of the weight attribute.