# dijkstra-pathfinder

> Pathfinder algorithm written in typescript. Uses all the power of Dijkstra algorithm.

Latest version **1.0.2** (published 2020-04-29) · MIT license · 0 weekly downloads

## Install

```sh
npm install dijkstra-pathfinder
pnpm add dijkstra-pathfinder
yarn add dijkstra-pathfinder
bun add dijkstra-pathfinder
```

## Health

**Score 25/100 (F)** — status: abandoned.

Positive: has types; no vulnerabilities; high quality score.

Warnings: low downloads; no esm support.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 1.0.2 |
| Published | 2020-04-29 |
| First published | 2020-04-26 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | bundled |
| Module format | CommonJS |
| Dependencies | 0 |
| Unpacked size | 19.7 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| Author | Julien Maulny |
| Maintainers | alcalyn |
| Keywords | dijkstra, pathfinder, graph |

## Links

- npm: https://www.npmjs.com/package/dijkstra-pathfinder
- Repository: https://gitlab.com/Alcalyn/dijkstra-pathfinder
- Issues: https://gitlab.com/Alcalyn/dijkstra-pathfinder/-/issues
- npm.io page: https://npm.io/package/dijkstra-pathfinder

## Alternatives

- [base64url](https://npm.io/package/base64url.md) — 6.1M weekly downloads
- [get-installed-path](https://npm.io/package/get-installed-path.md) — 502.9K weekly downloads
- [@uppy/url](https://npm.io/package/@uppy/url.md) — 185.8K weekly downloads
- [@d3fc/d3fc-shape](https://npm.io/package/@d3fc/d3fc-shape.md) — 16.2K weekly downloads
- [localizer](https://npm.io/package/localizer.md) — 226 weekly downloads

## Recent versions

- 1.0.2 (latest) — 2020-04-29
- 1.0.1 — 2020-04-26
- 1.0.0 — 2020-04-26

## README

# Dijkstra Pathfinder

Pathfinder algorithm written in typescript. Uses all the power of Dijkstra algorithm.

## Install

``` bash
npm install dijkstra-pathfinder --save

# or

yarn add dijkstra-pathfinder
```

## Usage

### Basic graph

Create a graph with bidirectional arcs with `graph.addArc(A, B)`.

![Graph picture basic example](img/basic.svg)

<details>
    <summary>Dot graph</summary>

``` dot
graph {
  rankdir=LR
  A -- E -- D
  A -- B -- C -- D
}
```
</details>

``` ts
const { Graph, Node, Dijkstra } = require('dijkstra-pathfinder');

const graph = new Graph();

const A = new Node();
const B = new Node();
const C = new Node();
const D = new Node();
const E = new Node();

graph.addArc(A, B);
graph.addArc(B, C);
graph.addArc(C, D);
graph.addArc(A, E);
graph.addArc(E, D);

// Instanciate a Dijkstra instance with A as starting node.
const dijkstra = new Dijkstra(graph, A);

// Calculate all best paths from A.
dijkstra.calculate();

// Path from A to D
dijkstra.getPathTo(D); // Node[] = [A, E, D]

// Path from A to C
const pathToC = dijkstra.getPathTo(C); // Node[] = [A, B, C]
```

### Graph with distances between nodes

Specify arc distance with `graph.addArc(A, B, 3)`.
If not set, distance is set to `1`.

![Graph picture distances example](img/distances.svg)

<details>
    <summary>Dot graph</summary>

``` dot
graph {
  rankdir=LR
  A -- E [label=3]
  E -- D [label=5]
  A -- B [label=2]
  B -- C -- D [label=1]
}
```
</details>

``` ts
const { Graph, Node, Dijkstra } = require('dijkstra-pathfinder');

const graph = new Graph();

const A = new Node();
const B = new Node();
const C = new Node();
const D = new Node();
const E = new Node();

graph.addArc(A, B, 2);
graph.addArc(B, C, 1);
graph.addArc(C, D, 1);
graph.addArc(A, E, 3);
graph.addArc(E, D, 2);

// Instanciate a Dijkstra instance with A as starting node.
const dijkstra = new Dijkstra(graph, A);

// Calculate all best paths from A.
dijkstra.calculate();

// Path from A to D
const pathToD = dijkstra.getPathTo(D); // Node[] = [A, B, C, D]

// Distance from A to D
pathToD[pathToD.length - 1].bestPath.distance; // number = 4

// Path from A to C
const pathToC = dijkstra.getPathTo(C);

// Distance from A to C
pathToC[pathToC.length - 1].bestPath.distance; // number = 3
```

### Oriented arcs

Use oriented arcs with `graph.addOrientedArc(B, A)`.

![Graph picture oriented example](img/oriented.svg)

<details>
    <summary>Dot graph</summary>

``` dot
digraph {
  rankdir=LR
  {rank = min; A}
  A -> E -> D
  B -> C -> D
  B -> A
}
```
</details>

``` ts
const { Graph, Node, Dijkstra } = require('dijkstra-pathfinder');

const graph = new Graph();

const A = new Node();
const B = new Node();
const C = new Node();
const D = new Node();
const E = new Node();

graph.addOrientedArc(B, A);
graph.addArc(B, C);
graph.addArc(C, D);
graph.addOrientedArc(A, E);
graph.addOrientedArc(E, D);

const dijkstra = new Dijkstra(graph, A);

dijkstra.calculate();

// Path from A to D
const pathToD = dijkstra.getPathTo(D); // Node[] = [A, E, D]

// Path from A to C
const pathToC = dijkstra.getPathTo(C); // Node[] = [A, E, D, C]
```

Note that:

``` ts
graph.addArc(A, B);
```

is equivalent to:

``` ts
graph.addOrientedArc(A, B);
graph.addOrientedArc(B, A);
```

### Add your payload

Add payload to your nodes to give them a business value:

![Graph picture payload example](img/payload.svg)

<details>
    <summary>Dot graph</summary>

``` dot
graph {
  rankdir=LR

  A [label="A (1;1)"]
  B [label="B (4;5)"]
  FarFarAway [label="🏰"]

  A -- B [label=5]
  B -- Paris -- London -- B
  London -- FarFarAway [label=40]
}
```
</details>

``` ts
const { Graph, Node, Dijkstra } = require('dijkstra-pathfinder');

const graph = new Graph();

const A = new Node('A (1;1)');
const B = new Node('B (4;5)');
const Paris = new Node('Paris');
const London = new Node('London');
const FarFarAway = new Node('🏰');

graph.addArc(A, B, 5);
graph.addArc(B, Paris);
graph.addArc(Paris, London);
graph.addArc(B, London);
graph.addArc(London, FarFarAway, 40);

const dijkstra = new Dijkstra(graph, A);

dijkstra.calculate();

// Path from A to 🏰
const pathToD = dijkstra.getPathTo(graph.findNodeByPayload('🏰'));

pathToD[0]; // Node = A
pathToD[0].payload; // string = "A (1;1)"

pathToD[1].payload; // string = "B (4;5)"
pathToD[2].payload; // string = "London"
pathToD[3].payload; // string = "🏰"

pathToD[pathToD.length - 1].bestPath.distance; // number = 46
```

### Clone graph

Clone a graph instance:

![Graph picture clone example](img/clone.svg)

<details>
    <summary>Dot graph</summary>

``` dot
graph {
  rankdir=LR
  A -- B -- C

  subgraph cluster {
    label=graph2
    edge[style=dashed]
    A -- C
  }
}
```
</details>

``` ts
const { Graph, Node, Dijkstra } = require('dijkstra-pathfinder');

const graph = new Graph();

const A = new Node('A');
const B = new Node('B');
const C = new Node('C');

graph.addArc(A, B);
graph.addArc(B, C);

const graph2 = graph.clone();

// Let's add a shortcut in cloned graph.
graph2.addArc(graph2.findNodeByPayload('A'), graph2.findNodeByPayload('C'));

// Instanciate a Dijkstra instance with A as starting node.
const dijkstra = new Dijkstra(graph, A);
dijkstra.calculate();

// Path from A to C
const path = dijkstra.getPathTo(C);
/*
  Node[] = [
    {payload: 'A'},
    {payload: 'B'},
    {payload: 'C'},
  ]
*/

// Instanciate another Dijkstra instance on graph2.
const dijkstra2 = new Dijkstra(graph2, graph2.findNodeByPayload('A'));
dijkstra2.calculate();

// Path from A to C
const path2 = dijkstra2.getPathTo(graph2.findNodeByPayload('C'));
/*
  Node[] = [
    {payload: 'A'},
    {payload: 'C'},
  ]
*/
```


*Graphs are generated with Dot language and this generator: <https://edotor.net>.*


## Develop

Clone this repo, then:

``` bash
# Install dependencies with
yarn

# Run tests with
yarn test

# Build files with
yarn build
```

## License

This library is under [MIT License](LICENSE).

---
_Source: https://npm.io/package/dijkstra-pathfinder · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._