graph.js

// @flow

/*
struct Node {
  int firstIncoming;
  int firstOutgoing;
}

struct Edge {
  int type;
  int from;
  int to;
  int nextIn;
  int nextOut
}
*/

const NODE_SIZE = 2;
const EDGE_SIZE = 5;

const TYPE = 0;
const FROM = 1;
const TO = 2;
const NEXT_IN = 3;
const NEXT_OUT = 4;

const FIRST_IN = 0;
const FIRST_OUT = 1;

export class EfficientGraph {
  nodes: Uint32Array;
  edges: Uint32Array;
  numNodes: number;
  numEdges: number;

  constructor(nodeCapacity = 128, edgeCapacity = 256) {
    this.nodes = new Uint32Array(nodeCapacity * NODE_SIZE);
    this.edges = new Uint32Array(edgeCapacity * EDGE_SIZE);
    this.numNodes = 0;
    this.numEdges = 0;
  }

  static deserialize(opts) {
    let res = Object.create(EfficientGraph.prototype);
    res.nodes = opts.nodes;
    res.edges = opts.edges;
    res.numNodes = opts.numNodes;
    res.numEdges = opts.numEdges;
    return res;
  }

  serialize() {
    return {
      nodes: this.nodes,
      edges: this.edges,
      numNodes: this.numNodes,
      numEdges: this.numEdges,
    };
  }

  resizeNodes(size) {
    let nodes = this.nodes;
    this.nodes = new Uint32Array(size * NODE_SIZE);
    this.nodes.set(nodes);
  }

  resizeEdges(size) {
    let edges = this.edges;
    this.edges = new Uint32Array(size * EDGE_SIZE);

    for (let i = 0; i < this.nodes.length; i += NODE_SIZE) {
      let lastOut;
      for (
        let hash = this.nodes[i + FIRST_OUT];
        hash;
        hash = edges[hash - 1 + NEXT_OUT]
      ) {
        let to = edges[hash - 1 + TO];
        let newHash = this.index(i, to);
        if (newHash === -1) {
          continue;
        }

        this.edges[newHash + TYPE] = edges[hash - 1 + TYPE];
        this.edges[newHash + FROM] = i;
        this.edges[newHash + TO] = to;
        if (lastOut != null) {
          this.edges[lastOut + NEXT_OUT] = 1 + newHash;
        } else {
          this.nodes[i + FIRST_OUT] = 1 + newHash;
        }

        lastOut = newHash;
      }

      let lastIn;
      for (
        let hash = this.nodes[i + FIRST_IN];
        hash;
        hash = edges[hash - 1 + NEXT_IN]
      ) {
        let from = edges[hash - 1 + FROM];
        let newHash = this.hash(from, i);
        while (this.edges[newHash + TYPE]) {
          if (
            this.edges[newHash + FROM] === from &&
            this.edges[newHash + TO] === i
          ) {
            break;
          } else {
            newHash = (newHash + EDGE_SIZE) % this.edges.length;
          }
        }

        this.edges[newHash + TYPE] = edges[hash - 1 + TYPE];
        this.edges[newHash + FROM] = from;
        this.edges[newHash + TO] = i;
        if (lastIn != null) {
          this.edges[lastIn + NEXT_IN] = 1 + newHash;
        } else {
          this.nodes[i + FIRST_IN] = 1 + newHash;
        }

        lastIn = newHash;
      }
    }
  }

  addNode() {
    let id = this.numNodes;
    this.numNodes++;
    if (this.numNodes >= this.nodes.length / NODE_SIZE) {
      this.resizeNodes((this.nodes.length / NODE_SIZE) * 2);
    }
    return id;
  }

  addEdge(from, to, type = 1) {
    let load = this.numEdges / (this.edges.length / EDGE_SIZE);
    if (load > 0.7) {
      this.resizeEdges((this.edges.length / EDGE_SIZE) * 2);
    }

    let hash = this.index(from, to);
    if (hash === -1) {
      return false;
    }

    this.numEdges++;

    this.edges[hash + TYPE] = type;
    this.edges[hash + FROM] = from;
    this.edges[hash + TO] = to;
    this.edges[hash + NEXT_IN] = this.nodes[to + FIRST_IN];
    this.edges[hash + NEXT_OUT] = this.nodes[from + FIRST_OUT];
    this.nodes[to + FIRST_IN] = 1 + hash;
    this.nodes[from + FIRST_OUT] = 1 + hash;
    return true;
  }

  index(from, to) {
    let hash = this.hash(from, to);

    while (this.edges[hash + TYPE]) {
      if (this.edges[hash + FROM] === from && this.edges[hash + TO] === to) {
        return -1;
      } else {
        hash = (hash + EDGE_SIZE) % this.edges.length;
      }
    }

    return hash;
  }

  hasEdge(from, to) {
    return this.index(from, to) === -1;
  }

  *getNodesConnectedFrom(from) {
    for (
      let i = this.nodes[from + FIRST_OUT];
      i;
      i = this.edges[i - 1 + NEXT_OUT]
    ) {
      yield this.edges[i - 1 + TO];
    }
  }

  *getNodesConnectedTo(to) {
    for (
      let i = this.nodes[to + FIRST_IN];
      i;
      i = this.edges[i - 1 + NEXT_IN]
    ) {
      yield this.edges[i - 1 + FROM];
    }
  }

  hash(from, to) {
    return Math.abs(
      ((from + 111111) * (to - 333333) * EDGE_SIZE) % this.edges.length,
    );
  }
}

export class FileGraph {
  constructor() {
    this.graph = new EfficientGraph();
    this.files = new Map();
    this.inverse = new Map();
  }

  addFile(file) {
    let id = this.files.get(file);
    if (id == null) {
      id = this.graph.addNode();
      this.files.set(file, id);
      this.inverse.set(id, file);
    }

    return id;
  }

  addEdge(fromFile, toFile) {
    this.graph.addEdge(this.files.get(fromFile), this.files.get(toFile));
  }
}

// let g = new EfficientGraph();
// g.addEdge(2, 3);
// g.addEdge(2, 4);
// g.addEdge(3, 4);
// console.log(g.hasEdge(2, 3), g.hasEdge(3, 2));
// console.log(g);
// console.log([...g.getNodesConnectedFrom(2)], [...g.getNodesConnectedTo(4)])

// g.resizeEdges(500);
// console.log(g.hasEdge(2, 3), g.hasEdge(3, 2));
// console.log(g);
// console.log([...g.getNodesConnectedFrom(2)], [...g.getNodesConnectedTo(4)])

// import Benchmark from 'tiny-benchy';

// let suite = new Benchmark(25000);

// let data = new ArrayBuffer(16);
// let i = new Uint32Array(data);
// let d = new DataView(data);

// suite.add('int32array', () => {
//   i[0] = 2;
//   i[1] = i[0];
// });

// suite.add('dataview', () => {
//   d.setUint32(0, 2);
//   d.setUint32(1, d.getUint32(0));
// });

// suite.run();