You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Mattia Belletti 4c71c5871d include before_script in specific tasks 3 months ago
.vscode Initial rough import and conversion. 3 months ago
src Documentation. 3 months ago
.babelrc Compilation system. 3 months ago
.gitignore Documentation. 3 months ago
.gitlab-ci.yml include before_script in specific tasks 3 months ago
README.md Documentation. 3 months ago
package.json Initial gitlab ci. 3 months ago
tsconfig-dist.json Compilation system. 3 months ago
tsconfig-es.json Compilation system. 3 months ago
tsconfig.json Compilation system. 3 months ago
typedoc.json Remove readme from typedoc. 3 months ago
webpack.config.base.js Compilation system. 3 months ago
webpack.config.development.js Compilation system. 3 months ago
webpack.config.js Compilation system. 3 months ago
webpack.config.production.js Compilation system. 3 months ago
yarn.lock Documentation. 3 months ago

README.md

Kahn's Topological Sort Algorithm

Kahn's algorithm is a possible way of ordering the nodes of a DAG (directed acyclic graph) in a way that preserves the partial order of the DAG itself.

This package contains a JavaScript implementation of the algorithm (with support for TypeScript typing).

Installation

To use this package in your JavaScript project, you first have to set the correct registry:

$ npm config set @redglow:registry https://npm.foxthesystem.space

Then you can add it to your project:

  • npm: npm install @redglow/kahn-topological-sort --save-dev
  • yarn: yarn add @redglow/kahn-topological-sort --dev

Usage

The first thing to do is to import the main function of the package, topologicalSort (all the examples will be in TypeScript):

import { topologicalSort } from "@redglow/kahn-topological-sort";

This function is generic and works on objects of any kind for nodes. Because of this, it needs some functions to retrieve the data it needs from the nodes:

  • comparer is a comparerer function used to break the tie when multiple nodes can be chosen by the algorithm; given two nodes, returns -1 if the first is smaller than the second, 1 if the first is bigger than the second, and 0 if it is indifferent,
  • getKey returns the key of a node (a unique identifier expressed as a string),
  • getParents returns the list of parents of a node, and
  • getChildren returns the list of children of a node.

E.g.:

interface INode {
  id: string;
  children: string[];
  parents: string[];
}

const nodes: INode[] = [
  {
    id: "A",
    children: ["B", "C"],
    parents: []
  },
  {
    id: "B",
    children: ["D"],
    parents: ["A"]
  },
  {
    id: "C",
    children: ["D"],
    parents: ["A"]
  },
  {
    id: "D",
    children: [],
    parents: ["B", "C"]
  }
];
const comparer = (node1: INode, node2: INode) => node1.id.localeCompare(node2.id);
const getKey = (node: INode) => node.id;
const getParents = (node: INode) => node.parents;
const getChildren = (node: INode) => node.children;

const sortedNodes = topologicalSort(nodes, getKey, getParents, getChildren);
// sortedNodes will be the list of nodes with ids A, B, C, D

The functions getChildren and getParents can be derived one from the other. Because of this, there are two helper functions. createGetChildren produce the function getChildren from getParents:

import { createGetChildren } from "@redglow/kahn-topological-sort";

const getChildren = createGetChildren(nodes, getKey, getParents);

Whereas createGetParents does the opposite:

import { createGetParents } from "@redglow/kahn-topological-sort";

const getParents = createGetParents(nodes, getKey, getChildren);

API

The full API is documented here.