graph.js

const source = [
  {
    id: "A",
    next: ["B"]
  },
  {
    id: "B",
    next: ["C", "D", "E", "F", "M"]
  },
  {
    id: "C",
    next: ["G"]
  },
  {
    id: "D",
    next: ["H"]
  },
  {
    id: "E",
    next: ["H"]
  },
  {
    id: "F",
    next: ["N", "O"]
  },
  {
    id: "N",
    next: ["I"]
  },
  {
    id: "O",
    next: ["P"]
  },
  {
    id: "P",
    next: ["I"]
  },
  {
    id: "M",
    next: ["L"]
  },
  {
    id: "G",
    next: ["I"]
  },
  {
    id: "H",
    next: ["J"]
  },
  {
    id: "I",
    next: []
  },
  {
    id: "J",
    next: ["K"]
  },
  {
    id: "K",
    next: ["L"]
  },
  {
    id: "L",
    next: []
  }
];

const NODE_TYPE_SIMPLE = "simple";
const NODE_TYPE_SPLIT = "split";
const NODE_TYPE_JOIN = "join";

class TraverseQueue {
  constructor() {
    this._ = [];
  }

  add(incomeId, bufferQueue, ...ids) {
    ids.forEach(id => {
      const item =
        this._.find(item => item.id === id) ||
        (bufferQueue ? bufferQueue._.find(item => item.id === id) : null);
      if (item) {
        item.passedIncomes.push(incomeId);
        return;
      }
      this._.push({
        id,
        passedIncomes: incomeId ? [incomeId] : []
      });
    });
  }

  push(item) {
    this._.push(item);
  }

  get length() {
    return this._.length;
  }

  some(cb) {
    return this._.some(cb);
  }

  shift() {
    return this._.shift();
  }

  drain() {
    const newQueue = new TraverseQueue();
    newQueue._ = newQueue._.concat(this._);
    this._ = [];
    return newQueue;
  }
}

class Graph {
  constructor(list) {
    this.applyList(list);
  }

  applyList(list) {
    this._incomesByNodeIdMap = {};
    this._outcomesByNodeIdMap = {};
    this._nodesMap = {};
    this._list = list;
    list.forEach(node => {
      if (this._nodesMap[node.id]) {
        throw new Error(`Duplicate node id ${node.id}`);
      }
      this._nodesMap[node.id] = node;
      node.next.forEach(outcomeId => {
        this._incomesByNodeIdMap[outcomeId] = this._incomesByNodeIdMap[
          outcomeId
        ]
          ? [...this._incomesByNodeIdMap[outcomeId], node.id]
          : [node.id];
      });
      this._outcomesByNodeIdMap[node.id] = [...node.next];
    });
  }

  traverse() {
    const root = this.root();
    const state = {
      mtx: new MatrixMap(),
      queue: new TraverseQueue(),
      x: 0,
      y: 0
    };
    let _safe = 0;
    const { mtx, queue } = state;
    queue.add(null, null, root.id);
    let isInserted = false;
    while (queue.length) {
      const levelQueue = queue.drain();
      while (levelQueue.length) {
        _safe++;
        const item = levelQueue.shift();
        switch (this.nodeType(item.id)) {
          case NODE_TYPE_SIMPLE:
            isInserted = this._processOrSkipNodeOnMatrix(item, state);
            if (isInserted) {
              queue.add(item.id, levelQueue, ...this.outcomes(item.id));
            }
            break;
          case NODE_TYPE_SPLIT:
            isInserted = this._processOrSkipNodeOnMatrix(item, state);
            if (isInserted) {
              const outcomes = this.outcomes(item.id);
              // first will be on the same y level as parent split
              const firstOutcomeId = outcomes.shift();
              queue.add(item.id, levelQueue, firstOutcomeId);
              // rest will create anchor with shift down by one
              outcomes.forEach(outcomeId => {
                state.y++;
                const id = `${item.id}-${outcomeId}`;
                this._insertOrSkipNodeOnMatrix(
                  { id: id, passedIncomes: [item.id] },
                  state,
                  true
                );
                queue.push({
                  id: outcomeId,
                  passedIncomes: [id]
                });
              });
            }
            break;
          case NODE_TYPE_JOIN:
            if (this._joinHasUnresolvedIncomes(item)) {
              queue.push(item);
            } else {
              isInserted = this._processOrSkipNodeOnMatrix(item, state);
              if (isInserted) {
                const incomes = item.passedIncomes;
                const lowestY = this._getLowestYAmongIncomes(item, mtx);
                incomes.forEach(incomeId => {
                  const [x, y] = mtx.find(item => item.id === incomeId);
                  if (lowestY === y) {
                    return;
                  }
                  state.y = y;
                  const id = `${incomeId}-${item.id}`;
                  this._insertOrSkipNodeOnMatrix(
                    { id: id, passedIncomes: [incomeId] },
                    state,
                    false
                  );
                });
                queue.add(item.id, levelQueue, ...this.outcomes(item.id));
              }
            }
            break;
        }
        if (_safe > 1000) {
          console.error("Infinite loop");
          return mtx;
        }
      }
      state.x++;
    }
    return mtx;
  }

  _processOrSkipNodeOnMatrix(item, state) {
    const { mtx, queue } = state;
    state.y = this._getLowestYAmongIncomes(item, mtx);
    // if point collides by y vertex, skipp it to next x
    if (mtx.hasVerticalCollision([state.x, state.y])) {
      queue.push(item);
      return false;
    }
    return this._insertOrSkipNodeOnMatrix(item, state, false);
  }

  _getLowestYAmongIncomes(item, mtx) {
    const incomes = item.passedIncomes;
    if (incomes && incomes.length) {
      // get lowest income y
      const items = incomes.map(id => {
        const coords = mtx.find(item => item.id === id);
        return coords[1];
      });
      const y = Math.min(...items);
      return y;
    }
    return 0;
  }

  _insertOrSkipNodeOnMatrix(item, state, checkCollision) {
    const { mtx } = state;
    // if point collides by x vertex, insert new row before y position
    if (checkCollision && mtx.hasHorizontalCollision([state.x, state.y])) {
      mtx.insertRowBefore(state.y);
    }
    mtx.insert([state.x, state.y], item);
    return true;
  }

  _joinHasUnresolvedIncomes(item) {
    return item.passedIncomes.length != this.incomes(item.id).length;
  }

  node(id) {
    return this._nodesMap[id];
  }

  incomes(id) {
    return this._incomesByNodeIdMap[id];
  }

  outcomes(id) {
    return this._outcomesByNodeIdMap[id];
  }

  root() {
    return this._list.find(node => this.isRoot(node.id));
  }

  nodeType(id) {
    if (this.isSplit(id)) return NODE_TYPE_SPLIT;
    if (this.isJoin(id)) return NODE_TYPE_JOIN;
    return NODE_TYPE_SIMPLE;
  }

  isSplit(id) {
    return (
      this._outcomesByNodeIdMap[id] && this._outcomesByNodeIdMap[id].length > 1
    );
  }

  isJoin(id) {
    return (
      this._incomesByNodeIdMap[id] && this._incomesByNodeIdMap[id].length > 1
    );
  }

  isRoot(id) {
    return (
      !this._incomesByNodeIdMap[id] || !this._incomesByNodeIdMap[id].length
    );
  }
}

class MatrixMap {
  constructor() {
    this._ = [];
  }

  get width() {
    return (
      this._.reduce(
        (length, row) => (row.length > length ? row.length : length),
        0
      ) || 0
    );
  }

  get height() {
    return this._.length;
  }

  hasHorizontalCollision([x, y]) {
    const row = this._[y];
    if (!row) return false;
    return row.some(point => !!point);
  }

  hasVerticalCollision([x, y]) {
    if (x >= this.width) {
      return false;
    }
    return this._.some((row, index) => {
      if (index < y) {
        return false;
      }
      return !!row[x];
    });
  }

  _extendHeight(toValue) {
    while (this.height < toValue) {
      const row = [];
      row.length = this.width;
      row.fill(null);
      this._.push(row);
    }
  }

  _extendWidth(toValue) {
    this._.forEach(row => {
      while (row.length < toValue) {
        row.push(null);
      }
    });
  }

  insertRowBefore(y) {
    const row = [];
    row.length = this.width;
    row.fill(null);
    this._.splice(y, 0, row);
  }

  insertColumnBefore(x) {
    this._.forEach(row => {
      row.splice(x, 0, null);
    });
  }

  find(callback) {
    let result = null;
    this._.forEach((row, y) => {
      row.some((point, x) => {
        if (!point) return false;
        if (callback(point)) {
          result = [x, y];
          return true;
        }
        return false;
      });
    });
    return result;
  }

  insert([x, y], item) {
    if (this.height <= y) {
      this._extendHeight(y + 1);
    }
    if (this.width <= x) {
      this._extendWidth(x + 1);
    }

    this._[y][x] = item;
  }

  debug() {
    this._[0] &&
      console.log(this._[0].reduce((str, _, i) => str + ` ${i} |`, "   |"));
    this._.forEach((row, i) => {
      console.log(
        row.reduce(
          (str, item) =>
            str +
            (item
              ? item.id.length > 1
                ? item.id.toString() + "|"
                : ` ${item.id.toString()} |`
              : "   |"),
          ` ${i} |`
        )
      );
    });
  }
}

const graph = new Graph(source);
console.log(graph);
const mtx = graph.traverse();
mtx.debug();
console.log(mtx);