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

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.