Graph.js

  1. import { _ } from '@kitmi/utils';
  2. import TopoSort from './TopoSort';
  4. class Graph {
  5.     /**
  6.      * Directed graph.
  7.      * @constructs Graph
  8.      * @param {object} json
  9.      * @property {object} json.nodes - key-value pairs of nodes
  10.      * @property {object} json.edges - key-value pairs of edges, source => [target1, target2, ...]
  11.      */
  12.     constructor(json) {
  13.         this.topo = new TopoSort();
  15.         if (json) {
  16.             this.nodes = _.cloneDeep(json.nodes);
  17.             if (!_.isEmpty(json.edges)) {
  18.                 _.forOwn(json.edges, (targets, source) => {
  19.                     this.topo.add(source, targets);
  20.                 });
  21.             }
  22.             this.startNodes = json.startNodes;
  23.             this.endNodes = json.endNodes;
  24.         } else {
  25.             this.nodes = {};
  26.         }
  27.     }
  29.     hasNode(key) {
  30.         return key in this.nodes;
  31.     }
  33.     getNode(key) {
  34.         return this.nodes[key];
  35.     }
  37.     setNode(key, value) {
  38.         this.nodes[key] = value;
  39.         return this;
  40.     }
  42.     setEdge(sourceNode, targetNode) {
  43.         if (!this.hasNode(sourceNode)) {
  44.             throw new Error(`Source node [${sourceNode}] not exists.`);
  45.         }
  46.         if (!this.hasNode(targetNode)) {
  47.             throw new Error(`Target node [${targetNode}] not exists.`);
  48.         }
  49.         this.topo.add(sourceNode, targetNode);
  50.         return this;
  51.     }
  53.     getTargetNodes(sourceNode) {
  54.         return Array.from(this.topo.mapOfDependents[sourceNode]);
  55.     }
  57.     getSourceNodes(targetNode) {
  58.         return Array.from(this.topo.mapOfDependencies[targetNode]);
  59.     }
  61.     /**
  62.      * Calculate start and end nodes.
  63.      * @returns {Graph}
  64.      */
  65.     calcStartEnd() {
  66.         const seq = this.topo.sort();
  67.         this.startNodes = _.takeWhile(seq, (e) => !this.topo.hasDependency(e));
  68.         this.endNodes = _.takeRightWhile(seq, (e) => !this.topo.hasDependent(e));
  70.         if (this.startNodes.length === 0) {
  71.             this.startNodes = Object.keys(this.nodes);
  72.         }
  74.         if (this.endNodes.length === 0) {
  75.             this.endNodes = Object.keys(this.nodes);
  76.         }
  78.         return this;
  79.     }
  81.     toJSON() {
  82.         return {
  83.             nodes: this.nodes,
  84.             edges: _.mapValues(this.topo.mapOfDependents, (nodes) => Array.from(nodes)),
  85.             startNodes: this.startNodes,
  86.             endNodes: this.endNodes,
  87.         };
  88.     }
  89. }
  91. export default Graph;