npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

graph-fns

v0.4.0

Published

A utility library for working with graphs.

Downloads

12

Readme

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

| Term | Description | | --- | --- | | graph / network | A system of vertices connected in pairs by edges. (Wikipedia) | | vertex / node | The fundamental unit of which graphs are formed. (Wikipedia) | | edge / link / branch / arc | A connection between two vertices in a graph. (Wikipedia) | | order | The number of vertices in a graph. | | size | The number of edges in a graph. | | weighted graph | A graph with a numeric weight associated with each edge. (Wolfram MathWorld) | | directed graph | A graph where the edges have direction. (Wikipedia) | | undirected graph | A graph where the edges do not have a direction. (Math Insight) | | path | A sequence of edges that connect a set of vertices where each vertex is distinct. (Wikipedia) | | directed path | A path where all edges are orientated in the same direction. | | undirected path | A path where the edges can be orientated in any direction. | | loop / buckle | An edge which starts and ends at the same vertex. (Wikipedia) | | cycle | A path that starts and ends at the same vertex. (Wikipedia) |

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:

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:

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:

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:

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:

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:

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:

getEdge

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

Get the weight of the given edge.

Also see:

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:

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:

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:

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:

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:

removeVertex

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

Removes a vertex from a graph.

Also see:

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:

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:

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:

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"] }