Graph.ts

import { Node } from "./Node.js";
import { Edge } from "./Edge.js";
import { EdgeRing } from "./EdgeRing.js";
import { flattenEach, coordReduce } from "@turf/meta";
import { featureOf } from "@turf/invariant";
import {
  FeatureCollection,
  LineString,
  MultiLineString,
  Feature,
} from "geojson";
import { AllGeoJSON } from "@turf/helpers";

/**
 * Validates the geoJson.
 *
 * @param {GeoJSON} geoJson - input geoJson.
 * @throws {Error} if geoJson is invalid.
 */
function validateGeoJson(geoJson: AllGeoJSON) {
  if (!geoJson) throw new Error("No geojson passed");

  if (
    geoJson.type !== "FeatureCollection" &&
    geoJson.type !== "GeometryCollection" &&
    geoJson.type !== "MultiLineString" &&
    geoJson.type !== "LineString" &&
    geoJson.type !== "Feature"
  )
    throw new Error(
      `Invalid input type '${geoJson.type}'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature`
    );
}

/**
 * Represents a planar graph of edges and nodes that can be used to compute a polygonization.
 *
 * Although, this class is inspired by GEOS's `geos::operation::polygonize::PolygonizeGraph`,
 * it isn't a rewrite. As regards algorithm, this class implements the same logic, but it
 * isn't a javascript transcription of the C++ source.
 *
 * This graph is directed (both directions are created)
 */
class Graph {
  private nodes: Map<number, Map<number, Node>> = new Map(); // Map<longitude, Map<latitude, Node>>
  private nodeId = 0; // the next node id to use
  private edges = new Map<Node, Map<Node, Edge>>(); // Map<from, Map<to, Edge>>

  /**
   * Creates a graph from a GeoJSON.
   *
   * @param {FeatureCollection<LineString>} geoJson - it must comply with the restrictions detailed in the index
   * @returns {Graph} - The newly created graph
   * @throws {Error} if geoJson is invalid.
   */
  static fromGeoJson(
    geoJson:
      | FeatureCollection<LineString | MultiLineString>
      | LineString
      | MultiLineString
      | Feature<LineString | MultiLineString>
  ) {
    validateGeoJson(geoJson);

    const graph = new Graph();
    flattenEach(geoJson, (feature) => {
      featureOf(feature, "LineString", "Graph::fromGeoJson");
      // When a LineString if formed by many segments, split them
      coordReduce<number[]>(feature, (prev, cur) => {
        if (prev) {
          const start = graph.getNode(prev),
            end = graph.getNode(cur);

          graph.addEdge(start, end);
        }
        return cur;
      });
    });

    return graph;
  }

  /**
   * Creates or get a Node.
   *
   * @param {number[]} coordinates - Coordinates of the node
   * @returns {Node} - The created or stored node
   */
  getNode(coordinates: number[]) {
    let node = this.nodes.get(coordinates[0])?.get(coordinates[1]);

    if (node == null) {
      const node = new Node(this.nodeId++, coordinates);
      let byLat = this.nodes.get(coordinates[0]);
      if (byLat == null) {
        byLat = new Map();
        this.nodes.set(coordinates[0], byLat);
      }
      byLat.set(coordinates[1], node);
      return node;
    }

    return node;
  }

  /**
   * Adds an Edge and its symetricall.
   *
   * Edges are added symetrically, i.e.: we also add its symetric
   *
   * @param {Node} from - Node which starts the Edge
   * @param {Node} to - Node which ends the Edge
   */
  addEdge(from: Node, to: Node) {
    const edge = new Edge(from, to),
      symetricEdge = edge.getSymetric();

    // add the forward edge
    let toMap = this.edges.get(from);
    if (toMap == null) {
      toMap = new Map();
      this.edges.set(from, toMap);
    }
    toMap.set(to, edge);

    // add the symmetric edge
    let symToMap = this.edges.get(to);
    if (symToMap == null) {
      symToMap = new Map();
      this.edges.set(to, symToMap);
    }
    symToMap.set(from, symetricEdge);
  }

  /**
   * Removes Dangle Nodes (nodes with grade 1).
   */
  deleteDangles() {
    this._forEachNode((node) => this._removeIfDangle(node));
  }

  /**
   * Check if node is dangle, if so, remove it.
   *
   * It calls itself recursively, removing a dangling node might cause another dangling node
   *
   * @param {Node} node - Node to check if it's a dangle
   */
  _removeIfDangle(node: Node) {
    // As edges are directed and symetrical, we count only innerEdges
    if (node.innerEdges.length <= 1) {
      const outerNodes = node.getOuterEdges().map((e) => e.to);
      this.removeNode(node);
      outerNodes.forEach((n) => this._removeIfDangle(n));
    }
  }

  /**
   * Delete cut-edges (bridge edges).
   *
   * The graph will be traversed, all the edges will be labeled according the ring
   * in which they are. (The label is a number incremented by 1). Edges with the same
   * label are cut-edges.
   */
  deleteCutEdges() {
    this._computeNextCWEdges();
    this._findLabeledEdgeRings();

    // Cut-edges (bridges) are edges where both edges have the same label
    this._forEachEdge((edge) => {
      if (edge.label === edge.symetric!.label) {
        this.removeEdge(edge.symetric!);
        this.removeEdge(edge);
      }
    });
  }

  /**
   * Set the `next` property of each Edge.
   *
   * The graph will be transversed in a CW form, so, we set the next of the symetrical edge as the previous one.
   * OuterEdges are sorted CCW.
   *
   * @param {Node} [node] - If no node is passed, the function calls itself for every node in the Graph
   */
  _computeNextCWEdges(node?: Node) {
    if (node == null) {
      this._forEachNode((node) => this._computeNextCWEdges(node));
    } else {
      node.getOuterEdges().forEach((edge, i) => {
        node.getOuterEdge(
          (i === 0 ? node.getOuterEdges().length : i) - 1
        ).symetric!.next = edge;
      });
    }
  }

  /**
   * Computes the next edge pointers going CCW around the given node, for the given edgering label.
   *
   * This algorithm has the effect of converting maximal edgerings into minimal edgerings
   *
   * XXX: method literally transcribed from `geos::operation::polygonize::PolygonizeGraph::computeNextCCWEdges`,
   * could be written in a more javascript way.
   *
   * @param {Node} node - Node
   * @param {number} label - Ring's label
   */
  _computeNextCCWEdges(node: Node, label: number) {
    const edges = node.getOuterEdges();
    let firstOutDE, prevInDE;

    for (let i = edges.length - 1; i >= 0; --i) {
      let de = edges[i],
        sym = de.symetric,
        outDE,
        inDE;

      if (de.label === label) outDE = de;

      if (sym!.label === label) inDE = sym;

      if (!outDE || !inDE)
        // This edge is not in edgering
        continue;

      if (inDE) prevInDE = inDE;

      if (outDE) {
        if (prevInDE) {
          prevInDE.next = outDE;
          prevInDE = undefined;
        }

        if (!firstOutDE) firstOutDE = outDE;
      }
    }

    if (prevInDE) prevInDE.next = firstOutDE;
  }

  /**
   * Finds rings and labels edges according to which rings are.
   *
   * The label is a number which is increased for each ring.
   *
   * @returns {Edge[]} edges that start rings
   */
  _findLabeledEdgeRings() {
    const edgeRingStarts: Edge[] = [];
    let label = 0;
    this._forEachEdge((edge) => {
      if (edge.label! >= 0) return;

      edgeRingStarts.push(edge);

      let e = edge;
      do {
        e.label = label;
        e = e.next!;
      } while (!edge.isEqual(e));

      label++;
    });

    return edgeRingStarts;
  }

  /**
   * Computes the EdgeRings formed by the edges in this graph.
   *
   * @returns {EdgeRing[]} - A list of all the EdgeRings in the graph.
   */
  getEdgeRings() {
    this._computeNextCWEdges();

    // Clear labels
    this._forEachEdge((edge) => {
      edge.label = undefined;
    });

    this._findLabeledEdgeRings().forEach((edge) => {
      // convertMaximalToMinimalEdgeRings
      this._findIntersectionNodes(edge).forEach((node) => {
        this._computeNextCCWEdges(node, edge.label!);
      });
    });

    const edgeRingList: EdgeRing[] = [];

    // find all edgerings
    this._forEachEdge((edge) => {
      if (edge.ring) return;
      edgeRingList.push(this._findEdgeRing(edge));
    });

    return edgeRingList;
  }

  /**
   * Find all nodes in a Maxima EdgeRing which are self-intersection nodes.
   *
   * @param {Node} startEdge - Start Edge of the Ring
   * @returns {Node[]} - intersection nodes
   */
  _findIntersectionNodes(startEdge: Edge) {
    const intersectionNodes = [];
    let edge = startEdge;
    do {
      // getDegree
      let degree = 0;
      edge.from.getOuterEdges().forEach((e) => {
        if (e.label === startEdge.label) ++degree;
      });

      if (degree > 1) intersectionNodes.push(edge.from);

      edge = edge.next!;
    } while (!startEdge.isEqual(edge));

    return intersectionNodes;
  }

  /**
   * Get the edge-ring which starts from the provided Edge.
   *
   * @param {Edge} startEdge - starting edge of the edge ring
   * @returns {EdgeRing} - EdgeRing which start Edge is the provided one.
   */
  _findEdgeRing(startEdge: Edge) {
    let edge = startEdge;
    const edgeRing = new EdgeRing();

    do {
      edgeRing.push(edge);
      edge.ring = edgeRing;
      edge = edge.next!;
    } while (!startEdge.isEqual(edge));

    return edgeRing;
  }

  /**
   * Removes a node from the Graph.
   *
   * It also removes edges asociated to that node
   * @param {Node} node - Node to be removed
   */
  removeNode(node: Node) {
    node.getOuterEdges().forEach((edge) => this.removeEdge(edge));
    node.innerEdges.forEach((edge) => this.removeEdge(edge));
    this.nodes.get(node.coordinates[0])?.delete(node.coordinates[1]);
  }

  /**
   * Remove edge from the graph and deletes the edge.
   *
   * @param {Edge} edge - Edge to be removed
   */
  removeEdge(edge: Edge) {
    this.edges.get(edge.from)?.delete(edge.to);
    edge.deleteEdge();
  }

  _forEachNode(fn: (n: Node) => void) {
    for (const latMap of this.nodes.values()) {
      for (const node of latMap.values()) {
        fn(node);
      }
    }
  }

  _forEachEdge(fn: (e: Edge) => void) {
    for (const toMap of this.edges.values()) {
      for (const edge of toMap.values()) {
        fn(edge);
      }
    }
  }
}

export { Graph };
export default Graph;