graphs-for-js - npm Package Compare versions

Comparing version 0.2.2 to 0.3.0

dist/index.d.ts

@@ -6,25 +6,34 @@ import { WeightedUndirectedGraph } from './src/WeightedUndirectedGraph';
 import * as GraphUtility from './src/GraphUtil';
-export declare const GraphBuilder: <V = unknown, E = unknown>() => {
-    withKeyFunction: <V_1, E_1>(fn: (v: V_1) => string) => {
+/**
+ * A builder tool for constructing graph data structures. Returns to callback functions,
+ * either to build to graph with a key function or without a key function.
+ * @constructor
+ */
+export declare const GraphBuilder: <V, E = unknown>() => {
+    withKeyFunction: (fn: (v: V) => string) => {
         directed: {
-            weighted: () => WeightedDirectedGraph<V_1, E_1>;
-            unweighted: () => DirectedGraph<V_1>;
+            weighted: () => WeightedDirectedGraph<V, E>;
+            unweighted: () => DirectedGraph<V, E>;
         };
         undirected: {
-            weighted: () => WeightedUndirectedGraph<V_1, E_1>;
-            unweighted: () => UndirectedGraph<V_1>;
+            weighted: () => WeightedUndirectedGraph<V, E>;
+            unweighted: () => UndirectedGraph<V, E>;
         };
     };
-    withoutKeyFunction: <V_3>() => {
+    withoutKeyFunction: () => {
         directed: {
-            weighted: () => WeightedDirectedGraph<V_3, E>;
-            unweighted: () => DirectedGraph<V_3>;
+            weighted: () => WeightedDirectedGraph<V, E>;
+            unweighted: () => DirectedGraph<V, E>;
         };
         undirected: {
-            weighted: () => WeightedUndirectedGraph<V_3, E>;
-            unweighted: () => UndirectedGraph<V_3>;
+            weighted: () => WeightedUndirectedGraph<V, E>;
+            unweighted: () => UndirectedGraph<V, E>;
         };
     };
 };
+/**
+ * A utility object which contains graph algorithm implementations and other graph tools,
+ * such as cloning and parsing a graph from JSON.
+ */
 export declare const GraphUtil: typeof GraphUtility;
 //# sourceMappingURL=index.d.ts.map

dist/index.js

@@ -40,2 +40,7 @@ "use strict";
 };
+/**
+ * A builder tool for constructing graph data structures. Returns to callback functions,
+ * either to build to graph with a key function or without a key function.
+ * @constructor
+ */
 exports.GraphBuilder = function () {
@@ -51,3 +56,7 @@ return {
 };
+/**
+ * A utility object which contains graph algorithm implementations and other graph tools,
+ * such as cloning and parsing a graph from JSON.
+ */
 exports.GraphUtil = GraphUtility;
 //# sourceMappingURL=index.js.map

dist/src/AbstractGraph.d.ts

 import { BasicEdge, GraphInterface } from './types/GraphInterface';
 import { Set } from 'typescript-collections';
 import { GraphType } from './types/GraphType';
-export declare abstract class AbstractNodeGraph<V> implements GraphInterface<V> {
+export declare abstract class AbstractNodeGraph<V, E = unknown> implements GraphInterface<V, E> {
     protected readonly graphNodes: Set<V>;
@@ -14,5 +14,5 @@ readonly toKeyFn: (v: V) => string;
     abstract remove(...nodes: V[]): number;
-    abstract edges(): BasicEdge<V>[];
-    abstract incomingEdgesOf(node: V): BasicEdge<V>[];
-    abstract outgoingEdgesOf(node: V): BasicEdge<V>[];
+    abstract edges(): BasicEdge<V, E>[];
+    abstract incomingEdgesOf(node: V): BasicEdge<V, E>[];
+    abstract outgoingEdgesOf(node: V): BasicEdge<V, E>[];
     abstract getGraphType(): GraphType;
@@ -19,0 +19,0 @@ abstract connect(source: V, target: V, value?: any): boolean;

dist/src/DirectedGraph.d.ts

@@ -5,3 +5,6 @@ import { BasicEdge, GraphInterface } from './types/GraphInterface';
 import { GraphType } from './types/GraphType';
-export declare class DirectedGraph<V> extends AbstractNodeGraph<V> implements GraphInterface<V> {
+/**
+ * An implementation of a directed graph without weights in its edges.
+ */
+export declare class DirectedGraph<V, E = unknown> extends AbstractNodeGraph<V, E> implements GraphInterface<V, E> {
     getGraphType(): GraphType;
@@ -16,8 +19,8 @@ protected readonly sourceToTarget: DefaultDictionary<V, Set<V>>;
     outDegreeOf(node: V): number;
-    edges(): BasicEdge<V>[];
+    edges(): BasicEdge<V, E>[];
     hasEdge(source: V, target: V): boolean;
-    incomingEdgesOf(target: V): BasicEdge<V>[];
-    outgoingEdgesOf(source: V): BasicEdge<V>[];
+    incomingEdgesOf(target: V): BasicEdge<V, E>[];
+    outgoingEdgesOf(source: V): BasicEdge<V, E>[];
     remove(...nodes: V[]): number;
 }
 //# sourceMappingURL=DirectedGraph.d.ts.map

dist/src/DirectedGraph.js

@@ -31,2 +31,5 @@ "use strict";
 var GraphType_1 = require("./types/GraphType");
+/**
+ * An implementation of a directed graph without weights in its edges.
+ */
 var DirectedGraph = /** @class */ (function (_super) {
@@ -33,0 +36,0 @@ __extends(DirectedGraph, _super);

dist/src/GraphUtil.d.ts

@@ -1,6 +0,24 @@
-export declare const hasCycle: <V>(graph: import("./types/GraphInterface").GraphInterface<V>) => boolean;
-export declare const findShortestPath: <V>(graph: import("./types/GraphInterface").GraphInterface<V>, start: V, end: V) => {
+export declare const hasCycle: <V>(graph: import("./types/GraphInterface").GraphInterface<V, unknown>) => boolean;
+export declare const findShortestPath: <V, E>(graph: import("./types/GraphInterface").GraphInterface<V, E>, start: V, end: V) => {
     path: V[];
     pathSize: number;
 };
+export declare const json: {
+    stringify: <V, E>(graph: import("./types/GraphInterface").GraphInterface<V, E>) => string;
+    parse: <V_1, E_1 = unknown>(jsonString: string, keyFunction?: ((v: V_1) => string) | undefined) => import("./types/GraphInterface").GraphInterface<V_1, E_1> | undefined;
+};
+export declare const castGraph: <V, E>(g: import("./types/GraphInterface").GraphInterface<V, E>) => {
+    type: import("./types/GraphType").GraphType.WeightedDirected;
+    graph: import("./WeightedDirectedGraph").WeightedDirectedGraph<V, E>;
+} | {
+    type: import("./types/GraphType").GraphType.NonWeightedDirected;
+    graph: import("./DirectedGraph").DirectedGraph<V, E>;
+} | {
+    type: import("./types/GraphType").GraphType.WeightedUndirected;
+    graph: import("./WeightedUndirectedGraph").WeightedUndirectedGraph<V, E>;
+} | {
+    type: import("./types/GraphType").GraphType.NonWeightedUndirected;
+    graph: import("./UndirectedGraph").UndirectedGraph<V, E>;
+};
+export declare const clone: <V, E>(g: import("./types/GraphInterface").GraphInterface<V, E>) => import("./types/GraphInterface").GraphInterface<V, E>;
 //# sourceMappingURL=GraphUtil.d.ts.map

dist/src/GraphUtil.js

@@ -22,7 +22,16 @@ "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
-exports.findShortestPath = exports.hasCycle = void 0;
+exports.clone = exports.castGraph = exports.json = exports.findShortestPath = exports.hasCycle = void 0;
 var HasCycle = __importStar(require("./util/HasCycle"));
 var FindShortestPath = __importStar(require("./util/FindShortestPath"));
+var j = __importStar(require("./util/json"));
+var caster = __importStar(require("./util/GetExplicitGraph"));
+var cloner = __importStar(require("./util/GraphClone"));
 exports.hasCycle = HasCycle.hasCycle;
 exports.findShortestPath = FindShortestPath.findShortestPath;
+exports.json = {
+    stringify: j.stringify,
+    parse: j.parse
+};
+exports.castGraph = caster.castExplicitly;
+exports.clone = cloner.clone;
 //# sourceMappingURL=GraphUtil.js.map

dist/src/types/GraphInterface.d.ts

 import { GraphType } from './GraphType';
-export interface BasicEdge<V> {
+export interface BasicEdge<V, E = unknown> {
     source: V;
     target: V;
     undirected: boolean;
+    value?: E;
 }
-export interface ValueEdge<V, E> extends BasicEdge<V> {
+export interface ValueEdge<V, E> extends BasicEdge<V, E> {
     value: E;
 }
-export interface GraphInterface<V> {
+export interface GraphInterface<V, E = unknown> {
+    /**
+     * The given Key Function used by the graph to determine the identity and uniqueness
+     * of a node in the graph. If none is given, then the default key function follows
+     * the following rules depending on the node type:
+     *
+     * Primitive Types:
+     * - This includes number, string, boolean, symbol, null, and undefined.
+     * - All primitives are converted to their string equivalents.
+     * - Caution: Floats are subject to float-precision issues.
+     *
+     * Objects:
+     * - A string representation of the object is used as the key, for which the string contains properties including
+     * keys and values.
+     * - For example, the object {a: 32, b: 23} is mapped as '{a:32,b:23}'
+     * - If an object value is circular, then it is mapped as the value of toString(), normally '[object Object]'
+     *
+     * @param v
+     */
     toKeyFn: (v: V) => string;
     /**
-     * Add nodes to the graph. Return the number of nodes added.
+     * Add nodes to the graph.
+     * Return the number of nodes added.
      * @param nodes
@@ -18,3 +38,4 @@ */
     /**
-     * Remove nodes from the graph. Return the number of nodes removed.
+     * Remove nodes from the graph.
+     * Return the number of nodes removed.
      * @param nodes
@@ -24,3 +45,3 @@ */
     /**
-     * Returns true if all of the nodes are in the graph.
+     * Returns true if all of the given nodes are in the graph.
      * @param nodes
@@ -30,3 +51,3 @@ */
     /**
-     * Return degree of a node.
+     * Return the degree of a node.
      * @param node
@@ -36,3 +57,3 @@ */
     /**
-     * Return in-degree of a node.
+     * Return the in-degree of a node.
      * @param node
@@ -47,3 +68,3 @@ */
     /**
-     * Return the set of all nodes in the graph.
+     * Return an array of all nodes in the graph.
      */
@@ -56,15 +77,19 @@ nodes: () => V[];
     /**
-     * Return a set of incoming edges to the node.
+     * Return an array of all incoming edges into the given node.
      * @param node
      */
-    incomingEdgesOf: (node: V) => BasicEdge<V>[];
+    incomingEdgesOf: (node: V) => BasicEdge<V, E>[];
     /**
-     * Return a set of outgoing edges from the node.
+     * Return an array of all outgoing edges from the given node.
      * @param node
      */
-    outgoingEdgesOf: (node: V) => BasicEdge<V>[];
+    outgoingEdgesOf: (node: V) => BasicEdge<V, E>[];
     /**
-     * Return the set of all edges in the graph.
+     * Return an array of all edges in the graph.
      */
-    edges: () => BasicEdge<V>[];
+    edges: () => BasicEdge<V, E>[];
+    /**
+     * Returns an identifier corresponding to the type of the graph, i.e. if it
+     * is an undirected graph or if its edges have weights.
+     */
     getGraphType: () => GraphType;
@@ -79,3 +104,4 @@ /**
     /**
-     * Return true if edge from source to target exists, otherwise false.
+     * Return true if an edge from source to the target exists in the graph,
+     * otherwise false.
      * @param source
@@ -86,3 +112,4 @@ * @param target
     /**
-     * Remove the edge from source to target. Return true if an edge is removed, otherwise false.
+     * Remove the edge from source to target.
+     * Return true if an edge is removed, otherwise false.
      * @param source
@@ -93,6 +120,7 @@ * @param target
 }
-export interface ValueGraph<V, E> extends GraphInterface<V> {
+export interface ValueGraph<V, E> extends GraphInterface<V, E> {
     /**
-     * Create an edge from the source node to the target node. Return true if a new
-     * edge is created, otherwise false.
+     * Create an edge from the source node to the target node with a given weight value.
+     * Return true if the edges in the graph changes, i.e. a new edge is created
+     * or an edge has its value changed. Return false otherwise.
      * @param source
@@ -104,3 +132,4 @@ * @param target
      * Return true if edge from source to target exists, otherwise false.
-     * If value is given, then the edge's value must also equal that value to return true.
+     * If value is given, then the value of the edge in the graph must also equal
+     * that value to return true.
      * @param source
@@ -114,3 +143,4 @@ * @param target
      *
-     * If value is given, then the edge's value must also equal to given value to be removed.
+     * If a value is given, then the value of the edge in the graph must also equal
+     * the given value to be removed.
      *
@@ -122,3 +152,3 @@ * @param source
     /**
-     * Return a set of incoming edges to the node.
+     * Return an array of all incoming edges into the given node.
      * @param node
@@ -128,3 +158,3 @@ */
     /**
-     * Return a set of outgoing edges from the node.
+     * Return an array of all outgoing edges from the given node.
      * @param node
@@ -134,7 +164,7 @@ */
     /**
-     * Return the set of all edges in the graph.
+     * Return an array of all edges in the graph.
      */
     edges: () => ValueEdge<V, E>[];
     /**
-     * Returns the value of an edge.
+     * Returns the value of an edge, if it exists.
      */
@@ -141,0 +171,0 @@ getEdgeValue: (source: V, target: V) => E | undefined;

dist/src/types/GraphType.d.ts

 export declare enum GraphType {
-    WeightedDirected = 0,
-    NonWeightedDirected = 1,
-    WeightedUndirected = 2,
-    NonWeightedUndirected = 3
+    WeightedDirected = "WeightedDirected",
+    NonWeightedDirected = "NonWeightedDirected",
+    WeightedUndirected = "WeightedUndirected",
+    NonWeightedUndirected = "NonWeightedUndirected"
 }
 //# sourceMappingURL=GraphType.d.ts.map

dist/src/types/GraphType.js

@@ -6,7 +6,7 @@ "use strict";
 (function (GraphType) {
-    GraphType[GraphType["WeightedDirected"] = 0] = "WeightedDirected";
-    GraphType[GraphType["NonWeightedDirected"] = 1] = "NonWeightedDirected";
-    GraphType[GraphType["WeightedUndirected"] = 2] = "WeightedUndirected";
-    GraphType[GraphType["NonWeightedUndirected"] = 3] = "NonWeightedUndirected";
+    GraphType["WeightedDirected"] = "WeightedDirected";
+    GraphType["NonWeightedDirected"] = "NonWeightedDirected";
+    GraphType["WeightedUndirected"] = "WeightedUndirected";
+    GraphType["NonWeightedUndirected"] = "NonWeightedUndirected";
 })(GraphType = exports.GraphType || (exports.GraphType = {}));
 //# sourceMappingURL=GraphType.js.map

dist/src/UndirectedGraph.d.ts

 import { DirectedGraph } from './DirectedGraph';
 import { BasicEdge } from './types/GraphInterface';
 import { GraphType } from './types/GraphType';
-export declare class UndirectedGraph<V> extends DirectedGraph<V> {
+/**
+ * An implementation of an undirected graph without weights in its edges.
+ */
+export declare class UndirectedGraph<V, E = unknown> extends DirectedGraph<V, E> {
     constructor(toKey?: (v: V) => string);
@@ -13,4 +16,4 @@ getGraphType(): GraphType;
      */
-    edges(): BasicEdge<V>[];
+    edges(): BasicEdge<V, E>[];
 }
 //# sourceMappingURL=UndirectedGraph.d.ts.map

dist/src/UndirectedGraph.js

@@ -20,2 +20,5 @@ "use strict";
 var GraphType_1 = require("./types/GraphType");
+/**
+ * An implementation of an undirected graph without weights in its edges.
+ */
 var UndirectedGraph = /** @class */ (function (_super) {
@@ -22,0 +25,0 @@ __extends(UndirectedGraph, _super);

dist/src/util/FindShortestPath.d.ts

 import { GraphInterface } from '../types/GraphInterface';
-export declare const findShortestPath: <V>(graph: GraphInterface<V>, start: V, end: V) => {
+/**
+ * Finds the shortest path from the given start node to the given end node.
+ *
+ * Returns an array representing the path found, where the first element is the
+ * start node, the last element is the end node, and all elements in between are the
+ * nodes in the path from the start to the end in order.
+ *
+ * Also returns the length of the path, i.e. the number of edges from start to end.
+ *
+ * Returns [] and -1 if no path is found.
+ */
+export declare const findShortestPath: <V, E>(graph: GraphInterface<V, E>, start: V, end: V) => {
     path: V[];
@@ -4,0 +15,0 @@ pathSize: number;

dist/src/util/FindShortestPath.js

@@ -16,2 +16,13 @@ "use strict";
 var typescript_collections_1 = require("typescript-collections");
+/**
+ * Finds the shortest path from the given start node to the given end node.
+ *
+ * Returns an array representing the path found, where the first element is the
+ * start node, the last element is the end node, and all elements in between are the
+ * nodes in the path from the start to the end in order.
+ *
+ * Also returns the length of the path, i.e. the number of edges from start to end.
+ *
+ * Returns [] and -1 if no path is found.
+ */
 exports.findShortestPath = function (graph, start, end) {
@@ -18,0 +29,0 @@ var e_1, _a;

dist/src/util/HasCycle.d.ts

 import { GraphInterface } from '../types/GraphInterface';
-export declare const hasCycle: <V>(graph: GraphInterface<V>) => boolean;
+/**
+ * Returns true if the given graph has a cycle and false otherwise,
+ * under the following definition of a cycle:
+ *
+ * There is a non-zero length path that starts and ends at a node `n`,
+ * and all edges in this path is unique.
+ *
+ */
+export declare const hasCycle: <V>(graph: GraphInterface<V, unknown>) => boolean;
 //# sourceMappingURL=HasCycle.d.ts.map

dist/src/util/HasCycle.js

@@ -127,2 +127,10 @@ "use strict";
 };
+/**
+ * Returns true if the given graph has a cycle and false otherwise,
+ * under the following definition of a cycle:
+ *
+ * There is a non-zero length path that starts and ends at a node `n`,
+ * and all edges in this path is unique.
+ *
+ */
 exports.hasCycle = function (graph) {
@@ -129,0 +137,0 @@ var graphType = graph.getGraphType();

dist/src/WeightedDirectedGraph.d.ts

@@ -8,3 +8,9 @@ import { ValueEdge, ValueGraph } from './types/GraphInterface';
 };
-export declare class WeightedDirectedGraph<V, E> extends AbstractNodeGraph<V> implements ValueGraph<V, E> {
+/**
+ * An implementation of a directed graph that has weights in its edges.
+ *
+ * @implements ValueGraph<V, E>
+ *
+ */
+export declare class WeightedDirectedGraph<V, E> extends AbstractNodeGraph<V, E> implements ValueGraph<V, E> {
     getGraphType(): GraphType;
@@ -11,0 +17,0 @@ protected readonly sourceToTarget: DefaultDictionary<V, Dictionary<V, EdgeValueWrapper<E>>>;

dist/src/WeightedDirectedGraph.js

@@ -31,2 +31,8 @@ "use strict";
 var GraphType_1 = require("./types/GraphType");
+/**
+ * An implementation of a directed graph that has weights in its edges.
+ *
+ * @implements ValueGraph<V, E>
+ *
+ */
 var WeightedDirectedGraph = /** @class */ (function (_super) {
@@ -49,8 +55,10 @@ __extends(WeightedDirectedGraph, _super);
         if (this.graphNodes.contains(source) && this.graphNodes.contains(target)) {
-            this.sourceToTarget.getValue(source).setValue(target, { value: value });
-            this.targetToSource.getValue(target).setValue(source, { value: value });
-            return true;
+            var currentValue = this.sourceToTarget.getValue(source).getValue(target);
+            if (currentValue === undefined || currentValue.value !== value) {
+                this.sourceToTarget.getValue(source).setValue(target, { value: value });
+                this.targetToSource.getValue(target).setValue(source, { value: value });
+                return true;
+            }
         }
-        else
-            return false;
+        return false;
     };
@@ -57,0 +65,0 @@ WeightedDirectedGraph.prototype.disconnect = function (source, target, value) {

dist/src/WeightedUndirectedGraph.d.ts

 import { WeightedDirectedGraph } from './WeightedDirectedGraph';
 import { GraphType } from './types/GraphType';
 import { ValueEdge } from './types/GraphInterface';
+/**
+ * An implementation of an undirected graph that has weights in its edges.
+ */
 export declare class WeightedUndirectedGraph<V, E> extends WeightedDirectedGraph<V, E> {
@@ -5,0 +8,0 @@ constructor(toKeyFn?: (v: V) => string);

dist/src/WeightedUndirectedGraph.js

@@ -20,2 +20,5 @@ "use strict";
 var typescript_collections_1 = require("typescript-collections");
+/**
+ * An implementation of an undirected graph that has weights in its edges.
+ */
 var WeightedUndirectedGraph = /** @class */ (function (_super) {
@@ -22,0 +25,0 @@ __extends(WeightedUndirectedGraph, _super);

package.json

 {
   "name": "graphs-for-js",
-  "version": "0.2.2",
+  "version": "0.3.0",
   "description": "Some JavaScript implementation of a graph data structure.\nFeatures:\n\t- Insert and remove nodes. \n\t- Connect and disconnect nodes. \n\t- Algorithms for graph structures.",
@@ -10,3 +10,3 @@ "main": "./dist/index.js",
     "test": "mocha -r ts-node/register 'test/**/*.test.ts'",
-    "coverage": "nyc mocha -r ts-node/register -r source-map-support/register --recursive test/**/*.test.ts",
+    "coverage": "nyc mocha -r ts-node/register -r source-map-support/register --recursive 'test/**/*.test.ts'",
     "prepare": "tsc",
@@ -13,0 +13,0 @@ "clean": "rm -rf ./dist"

No alert changes

Improved metrics

Total package byte prevSize

106308

increased by27.84%

Number of package files

71

increased by36.54%

Lines of code

1505

increased by34.74%

No dependency changes