aca.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 ACA_H
#define ACA_H

#include <vector>
#include <string>
#include <utility>
#include <map>
#include <set>

#include "libcola/cola.h"

#include "libdialect/util.h"
#include "libdialect/commontypes.h"
#include "libdialect/constraints.h"
#include "libdialect/graphs.h"

namespace dialect {

enum ACAFlag {
    ACAHORIZ = 1,
    ACAVERT  = 2,
    ACADELIB = 4,
    ACACONN  = 8
};

enum ACASepFlag {
    ACANOSEP      =  0,

    ACANORTH      =  1,
    ACAEAST       =  2,
    ACASOUTH      =  4,
    ACAWEST       =  8,

    ACANORTHEAST  =  3,
    ACASOUTHEAST  =  6,
    ACANORTHWEST  =  9,
    ACASOUTHWEST  = 12,

    ACANORTHSOUTH =  5,
    ACAEASTWEST   = 10,

    ACANOTNORTH   = 14,
    ACANOTEAST    = 13,
    ACANOTSOUTH   = 11,
    ACANOTWEST    =  7,

    ACAALLSEP     = 15
};

ACASepFlag negateSepFlag(ACASepFlag sf);
ACAFlag sepToAlignFlag(ACASepFlag sf);
ACAFlag perpAlignFlag(ACAFlag af);
ACASepFlag vectorToSepFlag(double dx, double dy);
bool propsedSepConflictsWithExistingPosition(ACASepFlag pro, ACASepFlag ex);

struct OrderedAlignment {
    OrderedAlignment() :
        af(ACACONN), sf(ACANOSEP), src(-1), tgt(-1),
        offsetSrc(0), offsetTgt(0),
        separation(nullptr), alignment(nullptr), edgeIndex(-1) {}
    ~OrderedAlignment() {}
    ACAFlag af;
    ACASepFlag sf;
    vpsc::Dim dim;
    int src;
    int tgt;
    double offsetSrc;
    double offsetTgt;
    cola::SeparationConstraint* separation;
    cola::AlignmentConstraint* alignment;
    int edgeIndex;
    double penalty;
};

bool sortOrdAlignsByPenalty(const OrderedAlignment *lhs, const OrderedAlignment *rhs);

typedef std::vector<OrderedAlignment*> OrderedAlignments;
typedef std::pair<double,double> EdgeOffset;
typedef std::vector<EdgeOffset> EdgeOffsets;
typedef std::vector<ACASepFlag> ACASepFlags;

class ACALayout {
public:
    ACALayout(
        const vpsc::Rectangles& rs,
        const std::vector<cola::Edge>& es,
        cola::CompoundConstraints& ccs,
        const double idealLength,
        const cola::EdgeLengths& eLengths = cola::StandardEdgeLengths,
        cola::TestConvergence* doneTest = nullptr,
        cola::PreIteration* preIteration = nullptr);

    ACALayout(std::shared_ptr<dialect::Graph> G);
        
    // To prevent C++ objects from being destroyed in garbage collected languages
    // when the libraries are called from SWIG, we hide the declarations of the
    // destructors and prevent generation of default destructors.
    #ifndef SWIG
    ~ACALayout(void);
    #endif

    void createAlignments(void);
    bool createOneAlignment(void);
    bool applyOAsAllOrNothing(OrderedAlignments oas);
    void layout(void);
    void removeOverlaps(void);
    void layoutWithCurrentConstraints(void);
    void updateGraph(void);
    void updateSepMatrix(void);
    void updateSepMatrix(SepMatrix &M, const std::map<size_t, id_type> &ix2id);

    void outputInstanceToSVG(std::string filename);

    cola::ConstrainedFDLayout *getFDLayout(void);

    // Configuration methods:

    void addBendPointPenalty(bool b);
    void favourLongEdges(bool b);
    void postponeLeaves(bool b);
    void useNonLeafDegree(bool b);
    void allAtOnce(bool b);
    void aggressiveOrdering(bool b);
    void setAvoidNodeOverlaps(bool avoidOverlaps);
    void ignoreEdges(std::vector<bool> ignore);
    void ignoreNodesForOPWithOffsets(std::vector<bool> ignore);
    void setNodeAliases(std::map<int,int> aliases);
    void setAlignmentOffsetsForCompassDirection(ACASepFlag sf, EdgeOffsets offsets);
    void setAllowedDirections(ACASepFlags seps);
    void setClusterHierarchy(cola::RootCluster *rc);
    bool edgeIsAligned(int j) const;
    void addGroupOfNonOverlapExemptRectangles(std::vector<unsigned> rs);

    bool nodesAreAligned(int i, int j) const;

    void layoutPeriod(unsigned p);
    void doFinalLayout(bool b);

    void addOrderedAlignments(OrderedAlignments oas);
    OrderedAlignment *initOrdAlign(int j, ACASepFlag sf) const;
    OrderedAlignment *initOrdAlign(int s, int t, ACASepFlag sf, int edgeIndex=-1) const;

    // Useful for debugging:
    OrderedAlignment *mostRecentOA(void);
    std::string writeAlignmentTable(void) const;
    std::string aStateBeforeChop;
    std::string writeStateForNodeIds(id_type id1, id_type id2);

private:
    void computeDegrees(void);
    void generateVPSCConstraints(void);
    int adjustVarNumForExtraVars(vpsc::Dim dim, int k);
    void initStateTables(void);
    void recordAlignmentWithClosure(int i, int j, ACAFlag af, int numCols = 0);

    void initNOCs(void);

    bool acaLoopOnce(void);
    void acaLoopOneByOne(void);
    void acaLoopAllAtOnce(void);

    bool layoutIfAppropriate(void);
    cola::CompoundConstraints writeAllVPSCConstraintsAsCompound(void);
    vpsc::Rectangles properAndAuxRects(void);

    void updateStateTables(OrderedAlignment *oa);

    vpsc::Rectangle *makeRectForOA(OrderedAlignment *oa);
    vpsc::Rectangle *makeRectForEdge(int j, vpsc::Dim dim);
    void updateRectForEdge(vpsc::Rectangle *R, int j, vpsc::Dim dim);
    void recomputeEdgeShapes(vpsc::Dim dim);
    void updateNodeRectsFromVars(void);
    void updateVarsFromNodeRects(void);
    void pushState(void);
    void popState(void);
    void dropState(void);
    void pushRectCoords(void);
    void popRectCoords(void);
    void dropRectCoords(void);
    void removeNewEdgeShapesAccordingToStateStack(void);
    std::set<unsigned> exemptionSetForEdge(int j);
    OrderedAlignment *chooseOA(void);
    bool createsOverlap(OrderedAlignment *oa);
    bool allOrNothing(OrderedAlignments oas);
    bool applyIfFeasible(OrderedAlignment *oa);
    vpsc::IncSolver *satisfy(vpsc::Variables &vs, vpsc::Constraints &cs, bool &sat);

    // In the following methods, the separation flag always means the direction from src to tgt.
    void completeOrdAlign(OrderedAlignment *oa);
    bool badSeparation(int j, ACASepFlag sf);
    bool badSeparation(int l, int r, ACASepFlag sf);

    double computePenalty(int j, ACASepFlag sf);
    double lengthPenaltyForEdge(int j);
    double deflectionForEdge(int j, ACASepFlag sf);
    double deflection(double sx, double sy, double tx, double ty, ACASepFlag sf);
    double bendPointPenalty(int src, int tgt, ACASepFlag sf);
    double leafPenalty(int src, int tgt);

    EdgeOffset getEdgeOffsetForCompassDirection(int j, ACASepFlag sf);
    int alias(int i);
    vpsc::Rectangle *getRect(int i, bool doAlias=false);

    // The penalty values determine the order in which certain types of
    // alignments will be created. (See above.)
    // The PENALTY_BOUND must be greater than the sum of the other penalty
    // values plus 1 (the maximum possible deflection score).

    static const double BP_PENALTY; // can be applied twice for one edge
    static const double LEAF_PENALTY;
    static const double PENALTY_BOUND;

    static const double EDGE_SHAPE_HALF_THICKNESS;
    static const double EDGE_SHAPE_BUFFER;

    Graph_SP m_graph;

    int m_n; // number of nodes
    int m_m; // number of edges
    int m_numExtraXVars;
    int m_numExtraYVars;
    vpsc::Rectangles m_rs;
    std::vector<cola::Edge> m_es;
    cola::CompoundConstraints m_ccs;
    cola::RootCluster *m_rc;

    std::vector<bool> m_ignoreEdge;
    std::vector<bool> m_ignoreNodeForOPWithOffsets;
    std::map<ACASepFlag,EdgeOffsets> m_edgeOffsets;
    ACASepFlags m_allowedSeps;
    std::map<int,int> m_nodeAliases;

    vpsc::Constraints m_xEqCs;
    vpsc::Constraints m_xIneqCs;
    vpsc::Constraints m_yEqCs;
    vpsc::Constraints m_yIneqCs;
    vpsc::Variables m_xvs;
    vpsc::Variables m_yvs;

    vpsc::Constraints m_xcs;
    vpsc::Constraints m_ycs;

    vpsc::Rectangles m_xrs;
    vpsc::Rectangles m_yrs;

    cola::NonOverlapConstraints *m_xnocs = nullptr;
    cola::NonOverlapConstraints *m_ynocs = nullptr;

    vpsc::Rectangles m_extendedRS;
    std::map<int,int> m_xAuxRectIndexInExtendedRS;
    std::map<int,int> m_yAuxRectIndexInExtendedRS;

    double m_idealLength;
    bool m_preventOverlaps;
    cola::EdgeLengths m_edgeLengths;
    cola::TestConvergence *m_doneTest = nullptr;
    cola::PreIteration *m_preIteration = nullptr;

    // Configuration:
    bool m_addBendPointPenalty;
    bool m_favourLongEdges;
    bool m_postponeLeaves;
    bool m_useNonLeafDegree;
    bool m_allAtOnce;
    bool m_aggressiveOrdering;

    std::multimap<int,int> m_incidentEdges; // map node index to indices of incident edges
    std::multimap<int,int> m_nlincidentEdges; // map node index to indices of incident edges
    std::multimap<int,int> m_nbrs; // neighbours
    std::multimap<int,int> m_nlnbrs; // non-leaf neighbours
    std::set<int> m_leaves; // indices of rectangles that are leaves
    std::set<int> m_deg2Nodes; // degree-2 nodes w.r.t. ordinary nbrs
    std::set<int> m_nldeg2Nodes; // degree-2 nodes w.r.t. only non-leaf neighbours

    Matrix2d<int> *m_alignmentState = nullptr;
    // Keep a record of all OrderedAlignments created and applied.
    std::vector<OrderedAlignment*> m_ordAligns;
    std::set<int> m_alignedEdges;

    cola::ConstrainedFDLayout *m_fdlayout = nullptr;

    double m_lengthUpperBound;

    std::vector<unsigned> m_sizeStack;
    std::vector<double> m_rectXStack;
    std::vector<double> m_rectYStack;
    std::map<int,int> m_edgeIndexToGuidelineIndex;
    std::map<int,int> m_guidelineIndexToEdgeIndex;

    std::map<int,int> m_xGuidelineIndexToEdgeIndex;
    std::map<int,int> m_yGuidelineIndexToEdgeIndex;

    bool m_didLayoutForLastAlignment;
    bool m_doFinalFDLayout;

    std::vector < std::vector<unsigned> > m_nocExemptRects;
    cola::NonOverlapConstraintExemptions *m_nocExemptions = nullptr;
    bool m_nocsInitialised;
    // Map each rect index to the set of all rect indices with which it is
    // exempt from non-overlap constraints:
    std::multimap<unsigned,unsigned> m_nocExemptionSets;

    unsigned m_layoutPeriod;
};

} // namespace dialect


#endif // ACA_H