graphs.h

/*
 * vim: ts=4 sw=4 et tw=0 wm=0
 *
 * libdialect - A library for computing DiAlEcT layouts:
 *                 D = Decompose/Distribute
 *                 A = Arrange
 *                 E = Expand/Emend
 *                 T = Transform
 *
 * Copyright (C) 2018  Monash University
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * See the file LICENSE.LGPL distributed with the library.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Author(s):   Steve Kieffer   <http://skieffer.info>
*/

#ifndef DIALECT_GRAPHS_H
#define DIALECT_GRAPHS_H

#include <vector>
#include <cfloat>
#include <string>
#include <map>
#include <utility>
#include <stack>
#include <deque>
#include <functional>

#include "libvpsc/rectangle.h"
#include "libcola/compound_constraints.h"
#include "libcola/cluster.h"
#include "libcola/cola.h"
#include "libavoid/libavoid.h"

#include "libdialect/commontypes.h"
#include "libdialect/constraints.h"
#include "libdialect/routing.h"
#include "libdialect/ortho.h"
#include "libdialect/logging.h"

namespace dialect {

struct BoundingBox {

    BoundingBox(double x, double X, double y, double Y) :
        x(x), X(X), y(y), Y(Y) {}

    BoundingBox(void) :
        x(DBL_MAX), X(-DBL_MAX), y(DBL_MAX), Y(-DBL_MAX) {}

    BoundingBox &operator+=(const BoundingBox &rhs);

    std::string repr(void) const;

    double w(void) const { return X - x; }

    double h(void) const { return Y - y; }

    interval getInterval(vpsc::Dim dim) { return dim == vpsc::XDIM ? std::make_pair(x, X) : std::make_pair(y, Y); }

    Avoid::Point centre(void) const { return Avoid::Point((x+X)/2.0, (y+Y)/2.0); }

    LineSegment_SP buildSideSegment(CardinalDir side) const;

    double perimeter(void) const { return 2*(w() + h()); }

    double x;
    double X;
    double y;
    double Y;
};

struct ColaOptions {
    double idealEdgeLength = 0;
    bool preventOverlaps = false;
    bool solidifyAlignedEdges = false;
    EdgesById solidEdgeExemptions;
    bool xAxis = true;
    bool yAxis = true;
    bool makeFeasible = false;
    double makeFeasible_xBorder = 0;
    double makeFeasible_yBorder = 0;
    bool useNeighbourStress = false;
    double nbrStressIELScalar = 1/20.0;
    bool useMajorization = false;
    bool useScaling = false;
    cola::CompoundConstraints ccs;
    std::vector<NodesById> nodeClusters;
    cola::EdgeLengths eLengths = cola::StandardEdgeLengths;
    cola::TestConvergence* doneTest = nullptr;
    cola::PreIteration* preIteration = nullptr;
    Logger *logger = nullptr;
};

struct ColaGraphRep {
    vpsc::Rectangles rs;
    std::vector<cola::Edge> es;
    cola::RootCluster *rc = nullptr;
    std::map<id_type, size_t> id2ix;
    std::map<size_t, id_type> ix2id;
};

struct NodeIdCmp {
    bool operator()(id_type i, const std::pair<id_type, Node_SP> &p) const {
        return i < p.first;
    }
    bool operator()(const std::pair<id_type, Node_SP> &p, id_type i) const {
        return p.first < i;
    }
};

class Graph {
public:
    Graph(void) : m_sepMatrix(this) {}

    Graph(const Graph &G);

    ~Graph(void);

    friend void swap(Graph &first, Graph &second) {
        using std::swap;
        swap(first.m_debugOutputPath, second.m_debugOutputPath);
        swap(first.m_projectionDebugLevel, second.m_projectionDebugLevel);
        swap(first.m_sepMatrix, second.m_sepMatrix);
        swap(first.m_iel, second.m_iel);
        swap(first.m_cgr, second.m_cgr);
        swap(first.m_needNewRectangles, second.m_needNewRectangles);
        swap(first.m_cfdl, second.m_cfdl);
        swap(first.m_nodes, second.m_nodes);
        swap(first.m_edges, second.m_edges);
        swap(first.m_maxDeg, second.m_maxDeg);
    }

    Graph &operator=(const Graph other);

    unsigned getMaxDegree(void) const;

    void addNode(Node_SP node, bool takeOwnership = true);

    Node_SP addNode(void);

    Node_SP addNode(double w, double h);

    Node_SP addNode(double cx, double cy, double w, double h);

    void addEdge(Edge_SP edge, bool takeOwnership = true);

    Edge_SP addEdge(Node_SP src, Node_SP tgt);

    Edge_SP addEdge(const id_type &srcID, const id_type &tgtID);

    bool hasNode(const id_type &id) const;

    bool hasEdge(const id_type &id) const;

    void severEdge(dialect::Edge &edge);

    void severNode(const dialect::Node &node);

    std::vector<Node_SP> severNodeNotingNeighbours(const dialect::Node &node);

    void removeNode(const dialect::Node &node);

    void removeNodes(const NodesById &nodes);

    void severAndRemoveNode(const dialect::Node &node);

    void severAndRemoveNode(id_type nodeID);

    Nodes cloneNode(id_type id);

    Node_SP getNode(const id_type &id) const;

    const NodesById &getNodeLookup(void) const { return m_nodes; }

    NodesById getNodeLookupWithIgnore(const Nodes &ignore) const;

    NodesById getNodeLookupWithIgnore(const NodesById &ignore) const;

    const EdgesById &getEdgeLookup(void) const { return m_edges; }

    size_t getNumNodes(void) const { return m_nodes.size(); }

    size_t getNumEdges(void) const { return m_edges.size(); }

    bool isEmpty(void) const { return m_nodes.empty(); }

    bool isTree(void) const { return getNumEdges() == getNumNodes() - 1; }

    double computeAvgNodeDim(void) const;

    double getIEL(void);

    double recomputeIEL(void);

    BoundingBox getBoundingBox(
                const NodesById &ignore = NodesById(),
                bool includeBends = false
            ) const;

    std::vector<Graph_SP> getConnComps(void) const;

    void getChainsAndCycles(std::vector<std::deque<Node_SP>> &chains, std::vector<std::deque<Node_SP>> &cycles);

    std::string writeTglf(bool useExternalIds = false) const;

    std::string writeSvg(bool useExternalIds = false) const;

    std::string writeId2Ix(void) const;

    std::string writeIx2Id(void) const;

    void rotate90cw(ColaOptions *opts=nullptr);

    void rotate90acw(ColaOptions *opts=nullptr);

    void rotate180(void);

    void translate(double dx, double dy);

    void putInBasePosition(void);

    bool hasSameLayoutAs(const Graph &other, double tol=0.001, id_map *idMap = nullptr) const;

    SparseIdMatrix2d<Edge_SP>::type getEdgeBySrcIdTgtIdLookup(void) const;

    void destress(const ColaOptions &opts);

    void destress(void);

    void solidifyAlignedEdges(vpsc::Dim dim, const ColaOptions &opts);

    void makeFeasible(const ColaOptions &opts);

    int project(const ColaOptions &opts, vpsc::Dim dim, int accept=0);

    int projectOntoSepCo(const ColaOptions &opts, SepCo_SP sepco, int accept=0);

    bool applyProjSeq(const ColaOptions &opts, ProjSeq &ps, int accept=0);


    void updateNodesFromRects(bool xAxis=true, bool yAxis=true);

    ColaGraphRep &updateColaGraphRep(void);

    cola::RootCluster *buildRootCluster(const ColaOptions &opts);

    ColaGraphRep &getColaGraphRep(void) { return m_cgr; }

    SepMatrix &getSepMatrix(void) { return m_sepMatrix; }

    NodesById buildUniqueBendPoints(void);

    void pushNodePositions(void);

    bool popNodePositions(void);

    void setEdgeThickness(double t) { m_edge_thickness = t; }

    double getEdgeThickness(void) { return m_edge_thickness; }

    void padAllNodes(double dw, double dh);

    void setPosesInCorrespNodes(Graph &H);

    void setRoutesInCorrespEdges(Graph &H, bool directed=false);

    void route(Avoid::RouterFlag routingType);

    void clearAllRoutes(void);

    void buildRoutes(void);

    void addBendlessSubnetworkToRoutingAdapter(RoutingAdapter &ra);

    void clearAllConstraints(void);

    void setCorrespondingConstraints(Graph &H);

    // For debugging:
    std::string m_debugOutputPath = "";
    unsigned m_projectionDebugLevel = 0;

private:
    SepMatrix m_sepMatrix;

    double m_iel = 0;

    double m_edge_thickness = 10;

    double autoInferIEL(void);

    void recomputeMaxDegree(void);

    double computeStress(void);

    void rotate90(PlaneMap nodeMap, std::function<void(Edge_SP)> edgeMap, SepTransform st, ColaOptions *opts=nullptr);

    ColaGraphRep m_cgr;
    bool m_needNewRectangles = true;
    cola::ConstrainedFDLayout *m_cfdl = nullptr;

    NodesById m_nodes;
    EdgesById m_edges;
    unsigned m_maxDeg = 0;

    std::stack<std::map<id_type, Avoid::Point>> m_posStack;

};

class Node {
public:
    static Node_SP allocate(void);

    static Node_SP allocate(double w, double h);

    static Node_SP allocate(double cx, double dy, double w, double h);

    GhostNode_SP makeGhost(void) const;

    dialect::Node &operator=(const dialect::Node&) = default;

    virtual ~Node(void) = default;

    virtual id_type id(void) const { return m_ID; }

    unsigned getDegree(void) const { return m_degree; }

    void setGraph(Graph &graph) { m_graph = &graph; }

    Graph *getGraph(void) { return m_graph; }

    void addEdge(const Edge_SP &edge);

    void removeEdge(const dialect::Edge &edge);

    const EdgesById &getEdgeLookup(void) const { return m_edges; }

    EdgesById getCopyOfEdgeLookup(void) const { return m_edges; }

    void copyGeometry(const dialect::Node &other);

    void copyOtherGhostProperties(const dialect::Node &other);

    dimensions getHalfDimensions(void) const;

    dimensions getDimensions(void) const;

    BoundingBox getBoundingBox(void) const;

    Avoid::Point getBoundaryCompassPt(CompassDir dir) const;

    void setCentre(double cx, double cy);

    void translate(double dx, double dy);

    void applyPlaneMap(PlaneMap map);

    Avoid::Point getCentre(void) const;

    void setExternalId(unsigned id) { m_externalID = id; }

    int getExternalId(void) { return m_externalID; }

    dialect::Nodes getNeighbours(void) const;

    dialect::Nodes getNeighboursCwCyclic(void) const;

    virtual dialect::Nodes getChildren(void) const;

    void setDims(double w, double h);

    void setBoundingBox(double x, double X, double y, double Y);

    void addPadding(double dw, double dh);

    void updatePosnFromRect(vpsc::Rectangle *r);

    void updateXCoordFromRect(vpsc::Rectangle *r);

    void updateYCoordFromRect(vpsc::Rectangle *r);

    Avoid::Polygon makeLibavoidPolygon(void) const;

    bool isRoot(void) const { return m_isRoot; }

    void setIsRoot(bool isRoot) { m_isRoot = isRoot; }

    bool liesOppositeSegment(const LineSegment &seg, bool openInterval=false);

    std::string writeSvg(bool useExternalId = false) const;

protected:

    Node(void) : m_ID(nextID++) {}

    Node(double w, double h) : m_ID(nextID++), m_w(w), m_h(h) {}

    Node(double cx, double cy, double w, double h) : m_ID(nextID++), m_cx(cx), m_cy(cy), m_w(w), m_h(h) {}

    Node(const dialect::Node&) = default;

    const id_type m_ID;

    int m_externalID = -1;

    EdgesById m_edges;

private:
    static id_type nextID;

    Graph *m_graph = nullptr;

    EdgesById m_edges_by_opp_id;

    unsigned m_degree = 0;

    double m_cx = 0.0;
    double m_cy = 0.0;

    double m_w = 100.0;
    double m_h = 60.0;

    bool m_isRoot = false;

};

class GhostNode : public Node {
public:

    static GhostNode_SP allocate(const Node &node) { return GhostNode_SP(new GhostNode(node)); }

    virtual id_type id(void) const {
        return m_doMasquerade ? m_originalNodeId : m_ID;
    }

    id_type trueID(void) const { return m_ID; }

    virtual Nodes getChildren(void) const;

    void setMasquerade(bool doMasquerade) { m_doMasquerade = doMasquerade; }

protected:

    GhostNode(const Node &node)
      : Node(),
        m_doMasquerade(false),
        m_originalNodeId(node.id())
    {
        // We also copy the given Node's geometry.
        copyGeometry(node);
        // And copy other properties.
        copyOtherGhostProperties(node);
    }

private:

    GhostNode(void) = delete;

    GhostNode(const GhostNode&) = delete;

    bool m_doMasquerade;

    id_type m_originalNodeId;

};


class Edge {
public:
    static Edge_SP allocate(const Node_SP &src, const Node_SP &tgt);

    Edge &operator=(const dialect::Edge&) = default;

    ~Edge(void) = default;

    id_type id(void) const { return m_ID; }

    Node_SP getOtherEnd(const dialect::Node &end1) const;

    Node_SP getSourceEnd(void) const { return Node_SP(m_src); }

    Node_SP getTargetEnd(void) const { return Node_SP(m_tgt); }

    std::pair<id_type, id_type> getEndIds(void) const { return {Node_SP(m_src)->id(), Node_SP(m_tgt)->id()}; }

    void setGraph(Graph &graph) { m_graph = &graph; }

    void sever(void);

    BoundingBox getBoundingBox(void) const;

    void addRoutePoint(double x, double y);

    void setRoute(std::vector<Avoid::Point> route);

    std::vector<Avoid::Point> getRoute(void) const { return m_route; }

    std::vector<Avoid::Point> getRoutePoints(void) const;

    std::string writeRouteTglf(void) const;

    std::pair<Avoid::ConnEnd, Avoid::ConnEnd> makeLibavoidConnEnds(
            Avoid::ConnDirFlags srcDirs=Avoid::ConnDirAll, Avoid::ConnDirFlags tgtDirs=Avoid::ConnDirAll);

    void setBendNodes(Nodes bends) { m_bendNodes = bends; }

    void addBendNode(Node_SP bn) { m_bendNodes.push_back(bn); }

    Nodes getBendNodes(void) { return m_bendNodes; }

    bool hasBendNodes(void) { return !m_bendNodes.empty(); }

    void rotate90cw(void);

    void rotate90acw(void);

    void rotate180(void);

    void translate(double dx, double dy);

    void clearRouteAndBends(void);

    void buildRouteFromBends(void);

    std::string writeSvg(void) const;

    std::string writePolylineConnectorData(void) const;

    std::string writeRoundedOrthoConnectorData(void) const;

private:
    Edge(const Node_SP &src, const Node_SP &tgt);

    Edge(void) = delete;

    static id_type nextID;

    const id_type m_ID;

    Graph *m_graph = nullptr;

    Node_WP m_src;
    Node_WP m_tgt;

    std::vector<Avoid::Point> m_route;

    Nodes m_bendNodes;
};


} // namespace dialect

// Global Operators
dialect::BoundingBox operator+(const dialect::BoundingBox &lhs, const dialect::BoundingBox &rhs);
bool operator==(const dialect::BoundingBox &lhs, const dialect::BoundingBox &rhs);
bool operator!=(const dialect::BoundingBox &lhs, const dialect::BoundingBox &rhs);

#endif // DIALECT_GRAPHS_H