@api-modeling/graphlib - npm Package Compare versions

Comparing version 3.0.0 to 3.0.1

package.json

 {
   "name": "@api-modeling/graphlib",
-  "version": "3.0.0",
+  "version": "3.0.1",
   "description": "A directed and undirected multi-graph library",
@@ -5,0 +5,0 @@ "author": "Chris Pettitt <[e-mail]>",

src/alg/components.d.ts

 import { Graph } from "../graph";
 import { NodeIdentifier } from "../types";
 
+/**
+ * Finds all connected components in a graph and returns an array of these components.
+ * Each component is itself an array that contains the ids of nodes in the component.
+ * Complexity: O(|V|).
+ * 
+ * @argument graph - graph to find components in.
+ * @returns array of nodes list representing components
+ */
 export default function components(g: Graph): NodeIdentifier[][];

src/alg/components.js

@@ -5,4 +5,8 @@ /** @typedef {import('../graph').Graph} Graph */
 /**
- * @param {Graph} g 
- * @returns {NodeIdentifier[][]}
+ * Finds all connected components in a graph and returns an array of these components.
+ * Each component is itself an array that contains the ids of nodes in the component.
+ * Complexity: O(|V|).
+ * 
+ * @param {Graph} g graph to find components in.
+ * @returns {NodeIdentifier[][]} array of nodes list representing components
  */
@@ -9,0 +13,0 @@ export default function components(g) {

src/alg/dijkstra-all.d.ts

 import { Graph } from "../graph.js";
-import { Edge, FloydWarshallItem, NodeIdentifier } from "../types.js";
+import { Edge, NodePath, NodeIdentifier } from "../types.js";
 
-export default function dijkstraAll(g: Graph, weightFunc?: (edge: Edge) => number, edgeFunc?: (v: NodeIdentifier) => Edge[]): Record<NodeIdentifier, Record<NodeIdentifier, FloydWarshallItem>>;
+/**
+ * This function finds the shortest path from each node to every other reachable node in
+ * the graph. It is similar to alg.dijkstra, but instead of returning a single-source
+ * array, it returns a mapping of source -> alg.dijksta(g, source, weightFn, edgeFn).
+ * Complexity: O(|V| * (|E| + |V|) * log |V|).
+ *
+ * @argument graph graph where to search paths.
+ * @argument weightFn function which takes edge e and returns the weight of it. If no weightFn
+ * is supplied then each edge is assumed to have a weight of 1. This function throws an
+ * Error if any of the traversed edges have a negative edge weight.
+ * @argument edgeFn function which takes a node v and returns the ids of all edges incident to it
+ * for the purposes of shortest path traversal. By default this function uses the graph.outEdges.
+ * @returns shortest paths map.
+ */
+export default function dijkstraAll(g: Graph, weightFunc?: (edge: Edge) => number, edgeFunc?: (v: NodeIdentifier) => Edge[]): Record<NodeIdentifier, Record<NodeIdentifier, NodePath>>;

src/alg/dijkstra-all.js

@@ -6,12 +6,17 @@ import dijkstra from "./dijkstra.js";
 /** @typedef {import('../types').Edge} Edge */
-/** @typedef {import('../types').FloydWarshallItem} FloydWarshallItem */
+/** @typedef {import('../types').NodePath} NodePath */
 
 /**
+ * This function finds the shortest path from each node to every other reachable node in
+ * the graph. It is similar to alg.dijkstra, but instead of returning a single-source
+ * array, it returns a mapping of source -> alg.dijksta(g, source, weightFn, edgeFn).
+ * Complexity: O(|V| * (|E| + |V|) * log |V|).
+ * 
  * @param {Graph} g 
  * @param {(edge: Edge) => number=} weightFunc 
  * @param {(v: NodeIdentifier) => Edge[]=} edgeFunc 
- * @returns {Record<NodeIdentifier, Record<NodeIdentifier, FloydWarshallItem>>}
+ * @returns {Record<NodeIdentifier, Record<NodeIdentifier, NodePath>>}
  */
 export default function dijkstraAll(g, weightFunc, edgeFunc) {
-  /** @type Record<NodeIdentifier, Record<NodeIdentifier, FloydWarshallItem>> */
+  /** @type Record<NodeIdentifier, Record<NodeIdentifier, NodePath>> */
   const result = {};
@@ -18,0 +23,0 @@ const ids = g.nodes();

src/alg/dijkstra.d.ts

 import { Graph } from "../graph";
-import { Edge, FloydWarshallItem, NodeIdentifier } from "../types";
+import { Edge, NodePath, NodeIdentifier } from "../types";
 
-export default function dijkstra(g: Graph, source: NodeIdentifier, weightFn?: ((edge: Edge) => number), edgeFn?: ((v: NodeIdentifier) => Edge[])): Record<NodeIdentifier, FloydWarshallItem>;
+/**
+ * This function is an implementation of Dijkstra's algorithm which finds the shortest
+ * path from source to all other nodes in graph. This function returns a map of
+ * v -> { distance, predecessor }. The distance property holds the sum of the weights
+ * from source to v along the shortest path or Number.POSITIVE_INFINITY if there is no path
+ * from source. The predecessor property can be used to walk the individual elements of the
+ * path from source to v in reverse order.
+ * Complexity: O((|E| + |V|) * log |V|).
+ *
+ * @argument graph - graph where to search pathes.
+ * @argument source - node to start pathes from.
+ * @argument weightFn - function which takes edge e and returns the weight of it. If no weightFn
+ * is supplied then each edge is assumed to have a weight of 1. This function throws an
+ * Error if any of the traversed edges have a negative edge weight.
+ * @argument edgeFn - function which takes a node v and returns the ids of all edges incident to it
+ * for the purposes of shortest path traversal. By default this function uses the graph.outEdges.
+ * @returns shortest pathes map that starts from node source
+ */
+export default function dijkstra(g: Graph, source: NodeIdentifier, weightFn?: ((edge: Edge) => number), edgeFn?: ((v: NodeIdentifier) => Edge[])): Record<NodeIdentifier, NodePath>;

src/alg/dijkstra.js

@@ -6,3 +6,3 @@ import { PriorityQueue } from '../data/PriorityQueue.js';
 /** @typedef {import('../types').NodeIdentifier} NodeIdentifier */
-/** @typedef {import('../types').FloydWarshallItem} FloydWarshallItem */
+/** @typedef {import('../types').NodePath} NodePath */
 
@@ -17,10 +17,10 @@ const DEFAULT_WEIGHT_FUNC = () => 1;
  * @param {(v: NodeIdentifier) => Edge[]} edgeFn 
- * @returns {Record<NodeIdentifier, FloydWarshallItem>}
+ * @returns {Record<NodeIdentifier, NodePath>}
  */
 function runDijkstra(g, source, weightFn, edgeFn) {
-  /** @type {Record<NodeIdentifier, FloydWarshallItem>} */
+  /** @type {Record<NodeIdentifier, NodePath>} */
   const results = {};
   const pq = new PriorityQueue();
   let v; 
-  /** @type FloydWarshallItem */
+  /** @type NodePath */
   let vEntry;
@@ -69,7 +69,18 @@
 /**
- * @param {Graph} g
- * @param {NodeIdentifier} source 
- * @param {((edge: Edge) => number)=} weightFn 
- * @param {((v: NodeIdentifier) => Edge[])=} edgeFn 
- * @returns {Record<NodeIdentifier, FloydWarshallItem>}
+ * This function is an implementation of Dijkstra's algorithm which finds the shortest
+ * path from source to all other nodes in graph. This function returns a map of
+ * v -> { distance, predecessor }. The distance property holds the sum of the weights
+ * from source to v along the shortest path or Number.POSITIVE_INFINITY if there is no path
+ * from source. The predecessor property can be used to walk the individual elements of the
+ * path from source to v in reverse order.
+ * Complexity: O((|E| + |V|) * log |V|).
+ * 
+ * @param {Graph} g - graph where to search paths.
+ * @param {NodeIdentifier} source node to start paths from.
+ * @param {((edge: Edge) => number)=} weightFn function which takes edge e and returns the weight of it. If no weightFn
+ * is supplied then each edge is assumed to have a weight of 1. This function throws an
+ * Error if any of the traversed edges have a negative edge weight.
+ * @param {((v: NodeIdentifier) => Edge[])=} edgeFn function which takes a node v and returns the ids of all edges incident to it
+ * for the purposes of shortest path traversal. By default this function uses the graph.outEdges.
+ * @returns {Record<NodeIdentifier, NodePath>} shortest paths map that starts from node source
  */
@@ -76,0 +87,0 @@ export default function dijkstra(g, source, weightFn, edgeFn) {

src/alg/find-cycles.d.ts

 import { Graph } from "../graph";
 import { NodeIdentifier } from "../types";
 
+/**
+ * Given a Graph, graph, this function returns all nodes that are part of a cycle. As there
+ * may be more than one cycle in a graph this function return an array of these cycles,
+ * where each cycle is itself represented by an array of ids for each node involved in
+ * that cycle. Method alg.isAcyclic is more efficient if you only need to determine whether a graph has a
+ * cycle or not.
+ * Complexity: O(|V| + |E|).
+ * 
+ * @argument graph - graph where to search cycles.
+ * @returns cycles list.
+ */
 export default function findCycles(g: Graph): NodeIdentifier[][];

src/alg/find-cycles.js

@@ -7,4 +7,11 @@ import tarjan from "./tarjan.js";
 /**
- * @param {Graph} g 
- * @returns {NodeIdentifier[][]}
+ * Given a Graph, graph, this function returns all nodes that are part of a cycle. As there
+ * may be more than one cycle in a graph this function return an array of these cycles,
+ * where each cycle is itself represented by an array of ids for each node involved in
+ * that cycle. Method alg.isAcyclic is more efficient if you only need to determine whether a graph has a
+ * cycle or not.
+ * Complexity: O(|V| + |E|).
+ * 
+ * @param {Graph} g graph where to search cycles.
+ * @returns {NodeIdentifier[][]} cycles list.
  */
@@ -11,0 +18,0 @@ export default function findCycles(g) {

src/alg/floyd-warshall.d.ts

 import { Graph } from "../graph";
 import { Edge, FloydWarshallResult, NodeIdentifier } from "../types";
 
+/**
+ * This function is an implementation of the Floyd-Warshall algorithm, which finds the
+ * shortest path from each node to every other reachable node in the graph. It is similar
+ * to alg.dijkstraAll, but it handles negative edge weights and is more efficient for some types
+ * of graphs. This function returns a map of source -> { target -> { distance, predecessor }.
+ * The distance property holds the sum of the weights from source to target along the shortest
+ * path of Number.POSITIVE_INFINITY if there is no path from source. The predecessor property
+ * can be used to walk the individual elements of the path from source to target in reverse
+ * order.
+ * Complexity: O(|V|^3).
+ *
+ * @argument graph - graph where to search pathes.
+ * @argument weightFn - function which takes edge e and returns the weight of it. If no weightFn
+ * is supplied then each edge is assumed to have a weight of 1. This function throws an
+ * Error if any of the traversed edges have a negative edge weight.
+ * @argument edgeFn - function which takes a node v and returns the ids of all edges incident to it
+ * for the purposes of shortest path traversal. By default this function uses the graph.outEdges.
+ * @returns shortest pathes map.
+ */
 export default function floydWarshall(g: Graph, weightFn?: (edge: Edge) => number, edgeFn?: (v: NodeIdentifier) => Edge[]): FloydWarshallResult;

src/alg/floyd-warshall.js

@@ -6,3 +6,2 @@ const DEFAULT_WEIGHT_FUNC = () => 1;
 /** @typedef {import('../types').Edge} Edge */
-/** @typedef {import('../types').FloydWarshallItem} FloydWarshallItem */
 /** @typedef {import('../types').FloydWarshallResult} FloydWarshallResult */
@@ -56,2 +55,12 @@
 /**
+ * This function is an implementation of the Floyd-Warshall algorithm, which finds the
+ * shortest path from each node to every other reachable node in the graph. It is similar
+ * to alg.dijkstraAll, but it handles negative edge weights and is more efficient for some types
+ * of graphs. This function returns a map of source -> { target -> { distance, predecessor }.
+ * The distance property holds the sum of the weights from source to target along the shortest
+ * path of Number.POSITIVE_INFINITY if there is no path from source. The predecessor property
+ * can be used to walk the individual elements of the path from source to target in reverse
+ * order.
+ * Complexity: O(|V|^3).
+ * 
  * @param {Graph} g 
@@ -58,0 +67,0 @@ * @param {(edge: Edge) => number=} weightFn

src/alg/is-acyclic.d.ts

 import { Graph } from "../graph";
 
+/**
+ * Given a Graph, graph, this function returns true if the graph has no cycles and returns false if it
+ * does. This algorithm returns as soon as it detects the first cycle. You can use alg.findCycles
+ * to get the actual list of cycles in the graph.
+ * 
+ * @argument graph graph to detect whether it acyclic ot not.
+ * @returns whether graph contain cycles or not.
+ */
 export default function isAcyclic(g: Graph): boolean;

src/alg/is-acyclic.js

@@ -6,2 +6,6 @@ import topSort, { CycleException } from "./topsort.js";
 /**
+ * Given a Graph, graph, this function returns true if the graph has no cycles and returns false if it
+ * does. This algorithm returns as soon as it detects the first cycle. You can use alg.findCycles
+ * to get the actual list of cycles in the graph.
+ * 
  * @param {Graph} g 
@@ -8,0 +12,0 @@ * @returns {boolean}

src/alg/postorder.d.ts

 import { Graph } from "../graph";
 import { NodeIdentifier } from "../types";
 
+/**
+ * Performs post-order depth first traversal on the input graph. If the graph is
+ * undirected then this algorithm will navigate using neighbors. If the graph
+ * is directed then this algorithm will navigate using successors.
+ * 
+ * @argument graph - depth first traversal target.
+ * @argument vs - nodes list to traverse.
+ * @returns the nodes in the order they were visited as a list of their names.
+ */
 export default function postOrder(g: Graph, vs: NodeIdentifier|NodeIdentifier[]): NodeIdentifier[];

src/alg/preorder.d.ts

 import { Graph } from "../graph";
 import { NodeIdentifier } from "../types";
 
+/**
+ * Performs pre-order depth first traversal on the input graph. If the graph is
+ * undirected then this algorithm will navigate using neighbors. If the graph
+ * is directed then this algorithm will navigate using successors.
+ * 
+ * @argument graph - depth first traversal target.
+ * @argument vs - nodes list to traverse.
+ * @returns the nodes in the order they were visited as a list of their names.
+ */
 export default function preOrder(g: Graph, vs: NodeIdentifier|NodeIdentifier[]): NodeIdentifier[];

src/alg/prim.d.ts

 import { Graph } from "../graph";
 import { Edge } from "../types";
 
+/**
+ * Prim's algorithm takes a connected undirected graph and generates a minimum spanning tree. This
+ * function returns the minimum spanning tree as an undirected graph. This algorithm is derived
+ * from the description in "Introduction to Algorithms", Third Edition, Cormen, et al., Pg 634.
+ * Complexity: O(|E| * log |V|);
+ *
+ * @argument graph graph to generate a minimum spanning tree of.
+ * @argument weightFn function which takes edge e and returns the weight of it. 
+ * It throws an Error if the graph is not connected.
+ * @returns minimum spanning tree of graph.
+ */
 export default function prim(g: Graph, weightFunc: (edge: Edge) => number): Graph;

src/alg/prim.js

@@ -7,3 +7,8 @@ import { Graph } from "../graph.js";
 /**
- * @param {Graph} g
+ * Prim's algorithm takes a connected undirected graph and generates a minimum spanning tree. This
+ * function returns the minimum spanning tree as an undirected graph. This algorithm is derived
+ * from the description in "Introduction to Algorithms", Third Edition, Cormen, et al., Pg 634.
+ * Complexity: O(|E| * log |V|);
+ * 
+ * @param {Graph} g graph to generate a minimum spanning tree of.
  * @param {(edge: Edge) => number} weightFunc 
@@ -10,0 +15,0 @@ * @returns {Graph}

src/alg/tarjan.d.ts

 import { Graph } from "../graph";
 import { NodeIdentifier } from "../types";
 
+/**
+ * This function is an implementation of Tarjan's algorithm which finds all strongly connected
+ * components in the directed graph g. Each strongly connected component is composed of nodes that
+ * can reach all other nodes in the component via directed edges. A strongly connected component
+ * can consist of a single node if that node cannot both reach and be reached by any other
+ * specific node in the graph. Components of more than one node are guaranteed to have at least
+ * one cycle.
+ * Complexity: O(|V| + |E|).
+ *
+ * @argument graph - graph to find all strongly connected components of.
+ * @return an array of components. Each component is itself an array that contains
+ * the ids of all nodes in the component.
+ */
 export default function tarjan(g: Graph): NodeIdentifier[][];

src/alg/topsort.d.ts

@@ -6,2 +6,10 @@ import { Graph } from "../graph";
 
+/**
+ * Given a Graph graph this function applies topological sorting to it.
+ * If the graph has a cycle it is impossible to generate such a list and CycleException is thrown.
+ * Complexity: O(|V| + |E|).
+ * 
+ * @argument graph - graph to apply topological sorting to.
+ * @returns an array of nodes such that for each edge u -> v, u appears before v in the array.
+ */
 export default function topSort(g: Graph): NodeIdentifier[];

src/graph.d.ts

@@ -1,12 +0,16 @@
-import { CountedEdges, Edge, GraphInit, Label, NodeChildren, NodeIdentifier, NodeParents } from "./types";
+import { CountedEdges, Edge, GraphInit, NodeChildren, NodeIdentifier, NodeParents } from "./types";
 
-export declare class Graph {
+/**
+ * The graph library.
+ * The `N` interface represents a node dictionary and the `E` interface represents an edge dictionary.
+ */
+export declare class Graph<N, E> {
   _isDirected: boolean;
   _isMultigraph: boolean;
   _isCompound: boolean;
-  _label: string;
+  _label: any;
   /**
    * v -> label
    */
-  _nodes: Record<NodeIdentifier, Label>;
+  _nodes: Record<NodeIdentifier, N>;
   _parent: NodeParents;
@@ -19,3 +23,3 @@
      */
-  _in: Record<NodeIdentifier, Record<NodeIdentifier, Edge>>;
+  _in: Record<NodeIdentifier, Record<NodeIdentifier, Edge<E>>>;
 
@@ -30,3 +34,3 @@ /**
    */
-  _out: Record<NodeIdentifier, Record<NodeIdentifier, Edge>>;
+  _out: Record<NodeIdentifier, Record<NodeIdentifier, Edge<E>>>;
 
@@ -41,3 +45,3 @@ /**
    */
-  _edgeObjects: Record<NodeIdentifier, Edge>;
+  _edgeObjects: Record<NodeIdentifier, Edge<E>>;
 
@@ -47,3 +51,3 @@ /**
    */
-  _edgeLabels: Record<NodeIdentifier, Label>;
+  _edgeLabels: Record<NodeIdentifier, E>;
 
@@ -95,3 +99,3 @@ /* Number of nodes in the graph. Should only be changed by the implementation. */
    */
-  setGraph(label: string): Graph;
+  setGraph(label: any): Graph<N,E>;
 
@@ -101,3 +105,3 @@ /**
    */
-  graph(): string|undefined;
+  graph(): any|undefined;
 
@@ -107,3 +111,3 @@ /**
    */
-  _defaultNodeLabelFn(node?: NodeIdentifier): string|undefined;
+  _defaultNodeLabelFn(node?: NodeIdentifier): any|undefined;
 
@@ -113,3 +117,3 @@ /**
    */
-  _defaultEdgeLabelFn(v: NodeIdentifier, w: NodeIdentifier, name?: string): string|undefined;
+  _defaultEdgeLabelFn(v: NodeIdentifier, w: NodeIdentifier, name?: string): any|undefined;
 
@@ -121,3 +125,3 @@ /**
    */
-  setDefaultNodeLabel(newDefault: string|(() => string)): Graph;
+  setDefaultNodeLabel(newDefault: string|((node?: NodeIdentifier) => any)): Graph<N,E>;
 
@@ -146,3 +150,3 @@ /**
    */
-  setNodes(vs: NodeIdentifier[], value?: Label): Graph;
+  setNodes(vs: NodeIdentifier[], value?: N): Graph<N,E>;
 
@@ -158,3 +162,3 @@ /**
    */
-  setNode(v: NodeIdentifier, label?: Label): Graph;
+  setNode(v: NodeIdentifier, label?: N): Graph<N,E>;
 
@@ -164,3 +168,3 @@ /**
    */
-  node(v: NodeIdentifier): Label|undefined;
+  node(v: NodeIdentifier): N|undefined;
 
@@ -178,3 +182,3 @@ /**
    */
-  removeNode(v: NodeIdentifier): Graph;
+  removeNode(v: NodeIdentifier): Graph<N,E>;
 
@@ -188,3 +192,3 @@ /**
    */
-  setParent(v: NodeIdentifier, parent?: NodeIdentifier): Graph;
+  setParent(v: NodeIdentifier, parent?: NodeIdentifier): Graph<N,E>;
 
@@ -227,3 +231,3 @@ _removeFromParentsChildList(v: NodeIdentifier): void;
    */
-  filterNodes(filter: (id: NodeIdentifier) => boolean): Graph;
+  filterNodes(filter: (id: NodeIdentifier) => boolean): Graph<N,E>;
 
@@ -235,3 +239,3 @@ /**
    */
-  setDefaultEdgeLabel(newDefault: string|((v:NodeIdentifier, w:NodeIdentifier, name?: string) => string)): Graph;
+  setDefaultEdgeLabel(newDefault: string|((v:NodeIdentifier, w:NodeIdentifier, name?: string|number) => any)): Graph<N,E>;
 
@@ -246,5 +250,5 @@ /**
    */
-  edges(): Edge[];
+  edges(): Edge<E>[];
 
-  setPath(vs: NodeIdentifier[], value?: string): Graph;
+  setPath(vs: NodeIdentifier[], value?: string): Graph<N,E>;
 
@@ -267,3 +271,3 @@ /**
    */
-  setEdge(v: NodeIdentifier|Edge, w?: NodeIdentifier|Label, value?: number|string, name?: string): Graph;
+  setEdge(v: NodeIdentifier|Edge<E>, w?: NodeIdentifier|E, value?: E, name?: string|number): Graph<N,E>;
 
@@ -281,3 +285,3 @@ /**
    */
-  edge(v: Edge|NodeIdentifier, w?: NodeIdentifier|string, name?: string): Label|undefined;
+  edge(v: Edge<E>|NodeIdentifier, w?: NodeIdentifier|string, name?: string|number): E|undefined;
 
@@ -295,3 +299,3 @@ /**
    */
-  hasEdge(v: Edge|NodeIdentifier, w?: NodeIdentifier|string, name?: string): boolean;
+  hasEdge(v: Edge<E>|NodeIdentifier, w?: NodeIdentifier|string, name?: string): boolean;
 
@@ -309,3 +313,3 @@ /**
    */
-  removeEdge(v: Edge|NodeIdentifier, w?: NodeIdentifier|string, name?: string): Graph;
+  removeEdge(v: Edge<E>|NodeIdentifier, w?: NodeIdentifier|string, name?: string): Graph<N,E>;
 
@@ -321,3 +325,3 @@ /**
    */
-  inEdges(v: NodeIdentifier, u?: NodeIdentifier): Edge[]|undefined;
+  inEdges(v: NodeIdentifier, u?: NodeIdentifier): Edge<E>[]|undefined;
 
@@ -333,3 +337,3 @@ /**
    */
-  outEdges(v: NodeIdentifier, w?: NodeIdentifier): Edge[]|undefined;
+  outEdges(v: NodeIdentifier, w?: NodeIdentifier): Edge<E>[]|undefined;
 
@@ -344,3 +348,3 @@ /**
    */
-  nodeEdges(v: NodeIdentifier, w?: NodeIdentifier): Edge[]|undefined;
+  nodeEdges(v: NodeIdentifier, w?: NodeIdentifier): Edge<E>[]|undefined;
 }

src/graph.js

@@ -9,4 +9,2 @@ /* eslint-disable class-methods-use-this */
 /** @typedef {import('./types').GraphInit} GraphInit */
-/** @typedef {import('./types').NodeLabel} NodeLabel */
-/** @typedef {import('./types').Label} Label */
 /** @typedef {import('./types').NodeIdentifier} NodeIdentifier */
@@ -23,3 +21,3 @@ /** @typedef {import('./types').NodeChildren} NodeChildren */
  */
- function incrementOrInitEntry(map, k) {
+function incrementOrInitEntry(map, k) {
   if (map[k]) {
@@ -48,3 +46,3 @@ map[k]++;
  * @param {NodeIdentifier} w_ Required when the `v` is not an Edge. When the `v` is Edge then this is the same as `value`.
- * @param {string=} name
+ * @param {string|number=} name
  * @returns {string}
@@ -67,3 +65,3 @@ */
  * @param {NodeIdentifier} w_ Required when the `v` is not an Edge. When the `v` is Edge then this is the same as `value`.
- * @param {string=} name
+ * @param {string|number=} name
  * @returns {Edge}
@@ -116,2 +114,7 @@ */
 
+/**
+ * The graph library.
+ * 
+ * The `N` interface represents a node dictionary and the `E` interface represents an edge dictionary.
+ */
 export class Graph {
@@ -131,3 +134,3 @@ /**
      * Label for the graph itself
-     * @type {string}
+     * @type {any}
      */
@@ -138,3 +141,3 @@ this._label = undefined;
      * v -> label
-     * @type {Record<NodeIdentifier, Label>}
+     * @type {Record<NodeIdentifier, any>}
      */
@@ -186,3 +189,3 @@ this._nodes = {};
      * e -> label
-     * @type {Record<NodeIdentifier, Label>}
+     * @type {Record<NodeIdentifier, any>}
      */
@@ -239,3 +242,3 @@ this._edgeLabels = {};
    * Sets the label for the graph to `label`.
-   * @param {string} label 
+   * @param {any} label 
    * @returns {Graph}
@@ -249,3 +252,3 @@ */
   /**
-   * @returns {string|undefined} The currently assigned label for the graph. If no label has been assigned, returns undefined
+   * @returns {any|undefined} The currently assigned label for the graph. If no label has been assigned, returns undefined
    */
@@ -259,3 +262,3 @@ graph() {
    * @param {NodeIdentifier=} node 
-   * @returns {string}
+   * @returns {any}
    */
@@ -271,4 +274,4 @@ // eslint-disable-next-line no-unused-vars
    * @param {NodeIdentifier} w 
-   * @param {string=} name 
-   * @returns {string}
+   * @param {string|number=} name 
+   * @returns {any}
    */
@@ -287,4 +290,4 @@ // eslint-disable-next-line no-unused-vars
    * 
-   * @param {string|(() => string)} newDefault 
-   * @returns 
+   * @param {string|((node?: NodeIdentifier) => any)} newDefault 
+   * @returns {Graph}
    */
@@ -338,3 +341,3 @@ setDefaultNodeLabel(newDefault) {
    * @param {NodeIdentifier[]} vs 
-   * @param {Label=} value 
+   * @param {any=} value 
    * @returns {Graph}
@@ -360,3 +363,3 @@ */
    * @param {NodeIdentifier} v The node to set
-   * @param {Label=} label 
+   * @param {any=} label 
    * @returns {Graph} the graph, allowing this to be chained with other functions. Takes O(1) time.
@@ -388,3 +391,3 @@ */
    * @param {NodeIdentifier} v 
-   * @returns {Label|undefined} the label assigned to the node or undefined when not found. Takes O(1) time.
+   * @returns {any|undefined} the label assigned to the node or undefined when not found. Takes O(1) time.
    */
@@ -636,3 +639,3 @@ node(v) {
    * 
-   * @param {string|((v:NodeIdentifier, w:NodeIdentifier, name?: string) => string)} newDefault 
+   * @param {string|((v:NodeIdentifier, w:NodeIdentifier, name?: string) => any)} newDefault 
    * @returns {Graph}
@@ -690,5 +693,5 @@ */
    * @param {NodeIdentifier|Edge} v
-   * @param {NodeIdentifier|Label=} w Required when the `v` is not an Edge. When the `v` is Edge then this is the same as `value`.
-   * @param {number|string=} value
-   * @param {string=} name
+   * @param {NodeIdentifier|any=} w Required when the `v` is not an Edge. When the `v` is Edge then this is the same as `value`.
+   * @param {any=} value
+   * @param {string|number=} name
    * @returns {Graph} Returns the graph, allowing this to be chained with other functions. 
@@ -705,3 +708,3 @@ */
     let valueArg;
-    /** @type string */
+    /** @type string|number */
     let nameArg;
@@ -775,4 +778,4 @@ if (typeof v === 'object' && v !== null && "v" in v) {
    * @param {NodeIdentifier|string=} w Required when `v` is not an edge. When the `v` is an object then this is `name` param.
-   * @param {string=} name 
-   * @returns {Label|undefined} the label for the edge (v, w) if the graph has an edge between `v` and `w` with the optional name.
+   * @param {string|string=} name 
+   * @returns {any|undefined} the label for the edge (v, w) if the graph has an edge between `v` and `w` with the optional name.
    * Returns `undefined` if there is no such edge in the graph. 
@@ -779,0 +782,0 @@ */

src/json.d.ts

 import { Graph } from './graph';
 import { GraphJson } from './types';
 
+/**
+ * Creates a JSON representation of the graph that can be serialized to a string with
+ * JSON.stringify. The graph can later be restored using json.read.
+ * 
+ * @argument graph target to create JSON representation of.
+ * @returns JSON serializable graph representation
+ */
 export declare function write(g: Graph): GraphJson;
+
+/**
+ * Takes JSON as input and returns the graph representation.
+ *
+ * @example
+ * var g2 = graphlib.json.read(JSON.parse(str));
+ * g2.nodes();
+ * // ['a', 'b']
+ * g2.edges()
+ * // [ { v: 'a', w: 'b' } ]
+ * 
+ * @argument json - JSON serializable graph representation
+ * @returns graph constructed according to specified representation
+ */
 export declare function read(json: GraphJson): Graph;

src/types.d.ts

@@ -24,15 +24,8 @@ export declare interface GraphInit {
 
-export declare interface NodeLabel {
+export declare interface Node<T> {
   /**
-   * The label of the node.
-   */
-  label: string;
-}
-
-export declare interface Node {
-  /**
    * Node identifier
    */
   v: NodeIdentifier;
-  value?: Label;
+  value?: T;
   parent?: NodeIdentifier;
@@ -45,28 +38,27 @@ }
    */
-   v: NodeIdentifier;
-   /**
-    * The edges end node
-    */
-   w: NodeIdentifier;
-   /**
-    * The name of the edge.
-    */
-   name?: string;
+  v: NodeIdentifier;
+  /**
+   * The edges end node
+   */
+  w: NodeIdentifier;
+  /**
+   * The name of the edge.
+   */
+  name?: string;
 }
 
-export declare interface Edge extends EdgeBase {
+export declare interface Edge<T> extends EdgeBase {
   /**
    * The label of the edge.
    */
-  label?: Label;
+  label?: T;
 }
 
-export declare interface JsonEdge extends EdgeBase {
+export declare interface JsonEdge<T> extends EdgeBase {
   /**
    * The label of the edge.
    */
-  value?: Label;
+  value?: T;
 }
 
-export type Label = NodeLabel | string | number;
 export type NodeIdentifier = string | number;
@@ -78,6 +70,6 @@ export type NodeChildren = Record<NodeIdentifier, Record<NodeIdentifier, boolean>>;
 
-export declare interface GraphJson {
+export declare interface GraphJson<T> {
   options: GraphInit;
-  nodes: Node[];
-  edges: JsonEdge[];
+  nodes: Node<T>[];
+  edges: JsonEdge<T>[];
   value?: string;
@@ -91,3 +83,3 @@ }
 
-export declare interface FloydWarshallItem {
+export declare interface NodePath {
   distance: number;
@@ -97,2 +89,2 @@ predecessor?: NodeIdentifier;
 
-export type FloydWarshallResult = Record<NodeIdentifier, Record<NodeIdentifier, FloydWarshallItem>>;
+export type FloydWarshallResult = Record<NodeIdentifier, Record<NodeIdentifier, NodePath>>;

New alerts

Long strings

Supply chain risk

Contains long string literals, which may be a sign of obfuscated or packed code.

Found 1 instance in 1 package

Fixed alerts

Long strings

Supply chain risk

Contains long string literals, which may be a sign of obfuscated or packed code.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

86529

14.29%

Lines of code

2332

9.02%

No dependency changes