graph-fns v0.4.0

Features

• Pure functions and immutable data patterns.
• Works in Node.js and browser runtimes.
• Flow and TypeScript declarations included.
• CommonJS, UMD and ESM modules provided.
• Zero dependencies.
• D3.js interoperability.

Demo

https://h2788.csb.app/

Installation

Yarn:

yarn add graph-fns

npm:

npm install graph-fns

Usage

import { create, addEdge, isCyclic, topologicalSort, degree, addVertex } from "graph-fns";

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

graph = addEdge(graph, ["A", "C"]);
//=> Graph { "A" -> "C", "B" }

graph = addEdge(graph, ["B", "A"]);
//=> Graph { "A" -> "C", "B" -> "A" }

isCyclic(graph);
//=> false

topologicalSort(graph);
//=> ["B", "A", "C"]

degree(graph, "A");
//=> 2

graph = addVertex(graph, "D");
//=> Graph { "A" -> "C", "B" -> "A", "D" }

graph = addEdge(graph, ["C", "D"]);
//=> Graph { "A" -> "C", "B" -> "A", "C" -> "D" }

descendants(graph, "A");
//=> Set { "C", "D" }

graph = addEdge(graph, ["D", "B"]);
//=> Graph { "A" -> "C", "B" -> "A", "C" -> "D", "D" -> "B" }

isCyclic(graph);
//=> true

Terminology

Types

D3Graph

declare type D3Graph = {
  nodes: Array<{
    id: string;
  }>;
  links: Array<{
    source: string;
    target: string;
  }>;
};

A representation a graph convenient for using with D3.js force-directed graphs.

Edge

declare type Edge = [string, string];

Graph

declare type Graph = {
  [u: string]: {
    [v: string]: number;
  };
};

This is the main data structure used by graph-fns to represent a graph. It is an adjacency matrix where each number in the matrix describes the edge from vertex u to vertex v. By default, a value of 1 is used to indicate there is a edge between the two vertices, but any value other than 0 can be used to signify the presence of an edge (typically used to describe a weighted graph).

Functions

addEdge

declare const addEdge: (graph: Graph, [u, v]: Edge) => Graph;

Adds a new edge to the graph from vertex u to vertex v.

Note: addEdge(graph, edge) is equivalent to setEdge(graph, edge, 1).

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

graph = addEdge(graph, ["A", "B"]);
//=> Graph { "A" -> "B", "C" }

Also see:

• removeEdge
• getEdge
• setEdge

addVertex

declare const addVertex: (graph: Graph, vertex: string) => Graph;

Adds a new vertex to the graph. The new vertex will not have any edges connecting it to existing vertices in the graph.

Note: If the vertex already exists the graph will be returned unmodified.

Also see:

• removeVertex

ancestors

declare const ancestors: (graph: Graph, vertex: string) => Set<string>;

Given a DAG, returns all ancestors of the given vertex (i.e. vertices from which there is a directed path to the given vertex).

Note: If the given graph contains cycles (checked with isCyclic), an error will be thrown.

Also see:

• descendants
• parents

children

declare const children: (graph: Graph, vertex: string) => Set<string>;

Returns all the vertices that are children of the given vertex (i.e. there is an edge starting at the given vertex going to the child vertex).

Note: If there is an edge that both starts and ends at the given vertex, it will be considered a child of itself and included in the result.

Also see:

• parents
• descendants

clone

declare const clone: (graph: Graph) => Graph;

Creates a copy of the graph.

create

declare const create: (size?: number, id?: (i: number) => string) => Graph;

Creates a new graph. The new graph can be seeded with an optional number of vertices, but it will not contain any edges.

The size argument defines how many vertices with which to seed the graph. Additional vertices can be added using addVertex, but it is more efficient to create them upfront when possible.

The id function can be provided to specify the identity of each vertex. The i argument passed is a unique monotonically increasing integer for each vertex being created and by default it will simply be converted to a string ((i) => i.toString(10)) resulting in the sequence "0", "1", "2" etc.

To create a graph using existing ID's you can use a pattern like this:

const users = [
  { id: "412", name: "Jane" },
  { id: "34", name: "Kate" },
  { id: "526", name: "Mike" },
  { id: "155", name: "Tony" },
];

const graph = create(users.length, (i) => users[i].id);

degree

declare const degree: (graph: Graph, vertex: string, weighted?: boolean) => number;

Returns the degree for the given vertex.

By default weighted is false, if set to true the result will be the sum of the edge weights (which could be zero or a negative value).

Also see:

• indegree
• outdegree

descendants

declare const descendants: (graph: Graph, vertex: string) => Set<string>;

Given a DAG, returns all descendants of the given vertex (i.e. vertices to which there is a directed path from the given vertex).

Note: If the given graph contains cycles (checked with isCyclic), an error will be thrown.

Also see:

• ancestors
• children

edges

declare const edges: (graph: Graph) => Set<Edge>;

Returns all the edges in the graph (i.e. any edge with a value other than 0).

fromD3

declare const fromD3: (graph: D3Graph) => Graph;

Converts a graph from a D3Graph representation into a Graph representation.

When the D3Graph contains multiple links between two nodes the resulting graph will have inflated edge weights to reflect that.

const graph = fromD3({
  nodes: [{ id: "A" }, { id: "B" }, { id: "C" }],
  links: [
    { source: "A", target: "B" },
    { source: "A", target: "C" },
    { source: "A", target: "C" },
  ],
});
//=> Graph { "A" -> "B", "A" -> "C" }

getEdge(["A", "B"]);
//=> 1
getEdge(["A", "C"]);
//=> 2

Note: Any extraneous data associated with nodes or links in the D3Graph representation will be ignored.

Also see:

• toD3

getEdge

declare const getEdge: (graph: Graph, [u, v]: Edge) => number;

Get the weight of the given edge.

Also see:

• addEdge
• removeEdge
• setEdge

indegree

declare const indegree: (graph: Graph, vertex: string, weighted?: boolean) => number;

Returns the indegree for the given vertex.

By default weighted is false, if set to true the result will be the sum of the edge weights (which could be zero or a negative value).

Also see:

• degree
• outdegree

isCyclic

declare const isCyclic: (graph: Graph) => boolean;

Returns true if the graph provided contains any cycles (including "loops" — when an edge that starts and ends at the same vertex), otherwise returns false.

isUndirected

declare const isUndirected: (graph: Graph) => boolean;

Returns true if the graph can be considered an undirected graph — every edge in the graph (from vertex A to B) has a mutual edge (from vertex B to A) with an equal weight. Loops are considered bidirectional and are allow in a undirected graph.

let graph = create(2, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B" }

isUndirected(graph);
//=> true

graph = addEdge(graph, ["A", "B"]);
//=> Graph { "A" -> "B" }

isUndirected(graph);
//=> false

graph = addEdge(graph, ["B", "A"]);
//=> Graph { "A" <-> "B" }

isUndirected(graph);
//=> true

makeUndirected

declare const makeUndirected: (graph: Graph, merge?: (a: number, b: number) => number) => Graph;

Converts a directed graph to an undirected graph by either adding edges to make them mutual or balancing the weights of mutual edges that aren't already equal.

The merge function is used to determine the weight of edges in cases where mutual edges with differing weights already exist. If not provide the default method is to use the highest of the two edge weights ((a, b) => Math.max(a, b)).

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

graph = addEdge(graph, ["A", "B"]);
//=> Graph { "A" -> "B", "C" }

graph = makeUndirected(graph);
//=> Graph { "A" <-> "B", "C" }

order

declare const order: (graph: Graph) => number;

Returns the number of vertices in the graph.

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

order(graph);
//=> 3

Also see:

• size

outdegree

declare const outdegree: (graph: Graph, vertex: string, weighted?: boolean) => number;

Returns the outdegree for the given vertex.

By default weighted is false, if set to true the result will be the sum of the edge weights (which could be zero or a negative value).

Also see:

• degree
• indegree

parents

declare const parents: (graph: Graph, vertex: string) => Set<string>;

Returns all the vertices that are parents of the given vertex (i.e. there is an edge starting at the parent vertex going to the given vertex).

Note: If there is an edge that both starts and ends at the given vertex, it will be considered a parent of itself and included in the result.

Also see:

• ancestors
• children

removeEdge

declare const removeEdge: (graph: Graph, edge: Edge) => Graph;

Removes an edge from a graph.

Note: removeEdge(graph, edge) is equivalent to setEdge(graph, edge, 0).

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

graph = addEdge(graph, ["A", "B"]);
//=> Graph { "A" -> "B", "C" }

graph = removeEdge(graph, ["A", "B"]);
//=> Graph { "A", "B", "C" }

Also see:

• addEdge
• getEdge
• setEdge

removeVertex

declare const removeVertex: (graph: Graph, vertex: string) => Graph;

Removes a vertex from a graph.

Also see:

• addVertex

setEdge

declare const setEdge: (graph: Graph, [u, v]: Edge, weight: number) => Graph;

Set the weight of the given edge.

Note: setEdge(graph, edge, 1) is equivalent to addEdge(graph, edge) and setEdge(graph, edge, 0) is equivalent to removeEdge(graph, edge).

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

graph = setEdge(graph, ["A", "B"], 1);
//=> Graph { "A" -> "B", "C" }

graph = setEdge(graph, ["A", "B"], 0);
//=> Graph { "A", "B", "C" }

Also see:

• addEdge
• getEdge
• removeEdge

size

declare const size: (graph: Graph) => number;

Returns the number of edges in the graph.

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

graph = addEdge(graph, ["A", "B"]);
//=> Graph { "A" -> "B", "C" }

graph = addEdge(graph, ["B", "C"]);
//=> Graph { "A" -> "B", "B" -> "C" }

size(graph);
//=> 2

Also see:

• order

toD3

declare const toD3: (graph: Graph) => D3Graph;

Converts a graph from a Graph representation into a D3Graph representation.

Edges with a weight of 2 or greater will result in multiple links being generated in the D3Graph.

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

graph = setEdge(graph, ["A", "B"], 1);
//=> Graph { "A" -> "B", "C" }

graph = setEdge(graph, ["A", "C"], 2);
//=> Graph { "A" -> "B", "A" -> "C" }

toD3(graph);
//=> {
//     nodes: [{ id: "A" }, { id: "B" }, { id: "C" }],
//     links: [
//       { source: "A", target: "B" },
//       { source: "A", target: "C" },
//       { source: "A", target: "C" },
//     ],
//   }

Also see:

• fromD3

topologicalSort

declare const topologicalSort: (graph: Graph) => Array<string>;

Given a DAG, returns an array of the graph's vertices sorted using a topological sort.

Note: If the given graph contains cycles (checked with isCyclic), an error will be thrown.

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

graph = addEdge(graph, ["A", "C"]);
//=> Graph { "A" -> "C", "B" }

graph = addEdge(graph, ["C", "B"]);
//=> Graph { "A" -> "C", "C" -> "B" }

topologicalSort(graph);
//=> ["A", "C", "B"]

transpose

declare const transpose: (graph: Graph) => Graph;

Flips the orientation of all edges in a directed graph.

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

graph = addEdge(graph, ["A", "B"]);
//=> Graph { "A" -> "B", "C" }

graph = addEdge(graph, ["B", "C"]);
//=> Graph { "A" -> "B", "B" -> "C" }

transpose(graph);
//=> Graph { "B" -> "A", "C" -> "B" }

vertices

declare const vertices: (graph: Graph) => Set<string>;

Returns the vertices in the graph.

vertexPairs

declare const vertexPairs: (graph: Graph) => Set<[string, string]>;

Returns a list of all pairs of vertices in the graph irrespective of the edges present in the graph.

let graph = create(3, (i) => String.fromCharCode(65 + i));
//=> Graph { "A", "B", "C" }

vertexPairs(graph);
//=> Set { ["A", "A"], ["A", "B"], ["A", "C"], ["B", "B"], ["B", "C"], ["C", "C"] }