Skip to content
Shortest path functions for graphology.
JavaScript
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
test Fixing cases when an erroneous path is returned Nov 27, 2018
.gitignore Initial commit Feb 17, 2017
.travis.yml Fixing travis Nov 26, 2018
LICENSE.txt Initial commit Feb 17, 2017
README.md Adding brandes method to dijkstra Mar 9, 2018
dijkstra.js Slight optimization Nov 27, 2018
index.js Starting Dijkstra Mar 9, 2018
package-lock.json Bump 1.0.4 Nov 27, 2018
package.json Bump 1.0.4 Nov 27, 2018
unweighted.js Fixing cases when an erroneous path is returned Nov 27, 2018

README.md

Build Status

Graphology Shortest Path

Shortest path functions for graphology.

Installation

npm install graphology-shortest-path

Usage

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.
You can’t perform that action at this time.