graph-definition

Graph definition

This package provides the Graph class which allows hustle-free creation of a generic graph.

Installation

npm install graph-definition
npm install --save-dev typescript

Interface

// this doesn't really exist
interface Graph {
  nodes: {
    [key: string]: {
      value: any;
    };
  };
  edges: Array<{
    from: string;
    to: string;
    weight?: number;
    dir?: 1 | -1 | 0;
  }>;
}

Usage

import Graph from "graph-definition";

Example of non-directed graph (map of routes between cities):

const map = new Graph({
  Kyiv: { population: 2.884e6 }, // arbitrary node payload
  Berlin: { population: 3.575e6 },
  NewYork: { population: 8.623e6 },
}, [
  // distance between Kyiv and Berlin
  { from: "Kyiv", to: "Berlin", weight: 1337.2 },

  // distance between Berlin and New York
  { from: "Berlin", to: "NewYork", weight: 6381 },

  // distance between Kyiv and New York
  { from: "Kyiv", to: "NewYork", weight: 7507 },
]);

Example of a directed graph (rock-paper-scissors game):

const relations = new Graph({
  Rock: null, // use `null` for empty payload; `Graph` only cares about keys
  Paper: null,
  Scissors: null,
}, [
  // Rock loses to Paper
  { from: "Rock", to: "Paper", weight: 1, dir: 1 },

  // Paper loses to Scissors
  { from: "Paper", to: "Scissors", weight: 1, dir: 1 },

  // Rock beats Scissors
  { from: "Rock", to: "Scissors", weight: 1, dir: -1 },
]);

Example of a vertex of degree 0:

const graph = new Graph({
  HalfLife3: null,
  Players: null,
  ReleaseDate: null,
}, [
  { from: "Players", to: "HalfLife3" },
]);

graph.getNodeDegree("ReleaseDate");
// 0

Example of a neural network (not very practical though, just a proof of concept):

class Neuron {
  constructor(public activation: number = Math.random()) {}
}

// 2-3-1 neural network
const network = new Graph({
  // input layer
  l0_n0: new Neuron(), // first neuron
  l0_n1: new Neuron(), // second neuron

  // hidden layer
  l1_n0: new Neuron(), // first neuron
  l1_n1: new Neuron(), // etc.
  l1_n2: new Neuron(),

  // output layer
  l2_n0: new Neuron(),
}, [
  // connections between input and hidden layers
  { from: "l0_n0", to: "l1_n0", weight: .9685, dir: 1 },
  { from: "l0_n1", to: "l1_n0", weight: .1583, dir: 1 },
  { from: "l0_n0", to: "l1_n1", weight: .0538, dir: 1 },
  { from: "l0_n1", to: "l1_n1", weight: .6713, dir: 1 },
  { from: "l0_n0", to: "l1_n2", weight: .6046, dir: 1 },
  { from: "l0_n1", to: "l1_n2", weight: .7004, dir: 1 },

  // connections between hidden and output layers
  { from: "l1_n0", to: "l2_n0", weight: .4191, dir: 1 },
  { from: "l1_n1", to: "l2_n0", weight: .0811, dir: 1 },
  { from: "l1_n2", to: "l2_n0", weight: .1991, dir: 1 },
]);