compound_constraints.h

/*
 * vim: ts=4 sw=4 et tw=0 wm=0
 *
 * libcola - A library providing force-directed network layout using the 
 *           stress-majorization method subject to separation constraints.
 *
 * Copyright (C) 2006-2008  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.
 *
*/

#ifndef _COMPOUND_CONSTRAINTS_H
#define _COMPOUND_CONSTRAINTS_H

#include <vector>
#include <list>
#include <set>
#include <utility>

#include "libvpsc/rectangle.h"
#include "libvpsc/constraint.h"
#include "libcola/sparse_matrix.h"
#include "libcola/unused.h"

namespace vpsc {
    class Constraint;
    class Variable;

// Avoid SWIG redefinition warnings.
#ifndef SWIG
    typedef std::vector<vpsc::Constraint *> Constraints;
    typedef std::vector<vpsc::Variable *> Variables;
#endif
}
namespace cola {

class Cluster;
class RootCluster;


// A component of a CompoundConstraint.
class SubConstraint
{
    public:
        SubConstraint(vpsc::Dim dim, vpsc::Constraint constraint, 
                double cost = 0)
            : dim(dim),
              constraint(constraint),
              cost(cost)
        {
        }
        bool operator<(const SubConstraint& rhs) const
        {
            return cost < rhs.cost;
        }

        vpsc::Dim dim;
        vpsc::Constraint constraint;
        double cost;
};


// A list of alternative SubConstraints. 
typedef std::list<SubConstraint> SubConstraintAlternatives;

static const double freeWeight = 0.0001;

static const unsigned int DEFAULT_CONSTRAINT_PRIORITY = 30000;
static const unsigned int PRIORITY_NONOVERLAP = 
        DEFAULT_CONSTRAINT_PRIORITY - 2000;

class VariableIDMap
{
    public:
        VariableIDMap();
        ~VariableIDMap();

        bool addMappingForVariable(const unsigned from, const unsigned to);
        unsigned mappingForVariable(const unsigned var,
                bool forward = true) const;
        void clear(void);
        void printCreationCode(FILE *fp) const;

    private:
        std::list<std::pair<unsigned, unsigned> > m_mapping;
};

class SubConstraintInfo 
{
    public:
        SubConstraintInfo(unsigned ind) :
            varIndex(ind),
            satisfied(false)
        {
        }
        virtual ~SubConstraintInfo()
        {
        }
        virtual void updateVarIDsWithMapping(const VariableIDMap& idMap,
                bool forward);

        unsigned varIndex;
        bool satisfied;
};

typedef std::vector<SubConstraintInfo *> SubConstraintInfoList;


class CompoundConstraint {
public:
    CompoundConstraint(vpsc::Dim primaryDim, 
            unsigned int priority = DEFAULT_CONSTRAINT_PRIORITY);
    virtual void generateVariables(const vpsc::Dim dim, 
            vpsc::Variables& vars) = 0;
    virtual void generateSeparationConstraints(const vpsc::Dim dim, 
            vpsc::Variables& var, vpsc::Constraints& cs,
            vpsc::Rectangles& bbs) = 0;
    virtual void updatePosition(const vpsc::Dim dim)
    {
        COLA_UNUSED(dim);
    }

    virtual std::string toString(void) const = 0;

// 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
    virtual ~CompoundConstraint();
#endif

    vpsc::Dim dimension(void) const;
    unsigned int priority(void) const;
    virtual void updateVarIDsWithMapping(const VariableIDMap& idMap,
            bool forward = true);
    virtual void updateShapeOffsetsForDifferentCentres(
                const std::vector<double>& offsets, bool forward = true)
    {
        COLA_UNUSED(offsets);
        COLA_UNUSED(forward);
    }

    // The following methods are only needed for initially solving feasibility
    // of the constraints, and do not need to be implemented for most compound
    // constraints.
    virtual void markAllSubConstraintsAsInactive(void);
    virtual bool subConstraintsRemaining(void) const;
    virtual void markCurrSubConstraintAsActive(const bool satisfiable);
    virtual SubConstraintAlternatives getCurrSubConstraintAlternatives(
            vpsc::Variables vs[]) = 0;
    std::list<unsigned> subConstraintObjIndexes(void) const;
    virtual void printCreationCode(FILE *fp) const;
    bool shouldCombineSubConstraints(void) const;

protected:
    void assertValidVariableIndex(const vpsc::Variables& vars, 
            const unsigned index);

    // The dimension that this compound constraint operates.
    vpsc::Dim _primaryDim;
    // The alternate dimension.
    vpsc::Dim _secondaryDim;
    // The priority used to assign order for solving constraints.
    unsigned int _priority;
    // Describes whether to process sub constraints individually, or all
    // at once, during the makeFeasible opteration.
    bool _combineSubConstraints;
    
    // Info about the sub constraints within this compound constraint.
    SubConstraintInfoList _subConstraintInfo;
    // The index of the current subConstraint being made feasible.
    size_t _currSubConstraintIndex;
};
typedef std::vector<CompoundConstraint *> CompoundConstraints;


void generateVariablesAndConstraints(CompoundConstraints& ccs, 
        const vpsc::Dim dim, vpsc::Variables& vars, vpsc::Constraints& cs,
        vpsc::Rectangles& bbs);


void generateVariables(CompoundConstraints& ccs, const vpsc::Dim dim, 
        vpsc::Variables& vars);


class BoundaryConstraint : public CompoundConstraint 
{
    public:
        BoundaryConstraint(const vpsc::Dim dim);
        void addShape(const unsigned int index, const double offset);

        std::string toString(void) const;

        SubConstraintAlternatives getCurrSubConstraintAlternatives(
                vpsc::Variables vs[]);
        void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars);
        void generateSeparationConstraints(const vpsc::Dim dim, 
                vpsc::Variables& vars, vpsc::Constraints& cs,
                vpsc::Rectangles& bbs);
        void updatePosition(const vpsc::Dim dim);
        void printCreationCode(FILE *fp) const;
        
        double position;

        vpsc::Variable* variable;
};


class AlignmentConstraint : public CompoundConstraint 
{
    public:
        AlignmentConstraint(const vpsc::Dim dim, double position = 0.0);
        void addShape(const unsigned int index, const double offset);
        void fixPos(double pos);
        void unfixPos(void);
        bool isFixed(void) const;

        std::string toString(void) const;

        SubConstraintAlternatives getCurrSubConstraintAlternatives(
                vpsc::Variables vs[]);
        void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars);
        void generateSeparationConstraints(const vpsc::Dim dim, 
                vpsc::Variables& vars, vpsc::Constraints& cs,
                vpsc::Rectangles& bbs);
        void updatePosition(const vpsc::Dim dim);
        double position(void) const;
        void printCreationCode(FILE *fp) const;
        void updateShapeOffsetsForDifferentCentres(
                const std::vector<double>& offsets, bool forward = true);
        
        void *indicator;
        
        vpsc::Variable* variable;
    private:
        // The position of the alignment line
        double _position;
        bool _isFixed;
};


class SeparationConstraint : public CompoundConstraint 
{
    public:
        SeparationConstraint(const vpsc::Dim dim, unsigned l, unsigned r, 
                double g, bool equality = false);
        SeparationConstraint(const vpsc::Dim dim, AlignmentConstraint *l, 
                AlignmentConstraint *r, double g, bool equality = false);

        std::string toString(void) const;

        SubConstraintAlternatives getCurrSubConstraintAlternatives(
                vpsc::Variables vs[]);
        void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars);
        void generateSeparationConstraints(const vpsc::Dim dim, 
                vpsc::Variables& vs, vpsc::Constraints& cs,
                vpsc::Rectangles& bbs);
        void setSeparation(double gap);
        unsigned left(void) const;
        unsigned right(void) const;
        void printCreationCode(FILE *fp) const;

        double gap;
        bool equality;
        vpsc::Constraint *vpscConstraint;
};


// XXX: This is experimental
//
// Orthogonal edges must have their end points aligned horizontally or 
// vertically
class OrthogonalEdgeConstraint : public CompoundConstraint 
{
    public:
        OrthogonalEdgeConstraint(const vpsc::Dim dim, unsigned l, unsigned r);
        
        SubConstraintAlternatives getCurrSubConstraintAlternatives(
                vpsc::Variables vs[]);
        void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars);
        void generateSeparationConstraints(const vpsc::Dim dim, 
                vpsc::Variables& vs, vpsc::Constraints& cs,
                vpsc::Rectangles& bbs);
        void generateTopologyConstraints(const vpsc::Dim k, 
                vpsc::Rectangles const& rs, 
                std::vector<vpsc::Variable*> const& vars, 
                std::vector<vpsc::Constraint*>& cs);
        void printCreationCode(FILE *fp) const;
        std::string toString(void) const;

        unsigned left;
        unsigned right;
        vpsc::Constraint* vpscConstraint;
    private:
        void rectBounds(const vpsc::Dim k, vpsc::Rectangle const *r, 
                double& cmin, double& cmax, double& centre, double& l) const;
};


class MultiSeparationConstraint : public CompoundConstraint 
{
    public:
        MultiSeparationConstraint(const vpsc::Dim dim, double minSep = 0, 
                bool equality = false);
        void addAlignmentPair(AlignmentConstraint *ac1, 
                AlignmentConstraint *ac2);
        void setSeparation(double sep);

        std::string toString(void) const;

        SubConstraintAlternatives getCurrSubConstraintAlternatives(
                vpsc::Variables vs[]);
        void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars);
        void generateSeparationConstraints(const vpsc::Dim dim, 
                vpsc::Variables& vs, vpsc::Constraints& gcs,
                vpsc::Rectangles& bbs);
        void printCreationCode(FILE *fp) const;

        vpsc::Constraints cs;
        
        void *indicator;
        
        double sep;
        bool equality;
};


class DistributionConstraint : public CompoundConstraint {
    public:
        DistributionConstraint(const vpsc::Dim dim);
        void addAlignmentPair(AlignmentConstraint *ac1, 
                AlignmentConstraint *ac2);
        void setSeparation(double sep);

        std::string toString(void) const;

        SubConstraintAlternatives getCurrSubConstraintAlternatives(
                vpsc::Variables vs[]);
        void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars);
        void generateSeparationConstraints(const vpsc::Dim dim, 
                vpsc::Variables& vars, vpsc::Constraints& gcs,
                vpsc::Rectangles& bbs);
        void printCreationCode(FILE *fp) const;

        vpsc::Constraints cs;
        
        void *indicator;
        
        double sep;
};

class FixedRelativeConstraint : public CompoundConstraint {
    public:
        FixedRelativeConstraint(const vpsc::Rectangles& rs,
                std::vector<unsigned> shapeIds, 
                const bool fixedPosition = false);

        std::string toString(void) const;

        SubConstraintAlternatives getCurrSubConstraintAlternatives(
                vpsc::Variables vs[]);
        void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars);
        void generateSeparationConstraints(const vpsc::Dim dim, 
                vpsc::Variables& vars, vpsc::Constraints& gcs,
                vpsc::Rectangles& bbs);
        void printCreationCode(FILE *fp) const;
        void updateVarIDsWithMapping(const VariableIDMap& idMap,
            bool forward = true);

    private:
        bool m_fixed_position;
        std::vector<unsigned> m_shape_vars;
};


class PageBoundaryConstraints : public CompoundConstraint {
    public:
        PageBoundaryConstraints(double xLow, double xHigh, 
                double yLow, double yHigh, double weight = 100.0);
        void addShape(unsigned index, double halfW, double halfH);

        std::string toString(void) const;

        SubConstraintAlternatives getCurrSubConstraintAlternatives(
                vpsc::Variables vs[]);
        void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars);
        void generateSeparationConstraints(const vpsc::Dim dim, 
                vpsc::Variables& vars, vpsc::Constraints& gcs,
                vpsc::Rectangles& bbs);
        void updatePosition(const vpsc::Dim dim);
        double getActualLeftMargin(const vpsc::Dim dim);
        double getActualRightMargin(const vpsc::Dim dim);
        void printCreationCode(FILE *fp) const;

    private:
        double leftMargin[2];
        double rightMargin[2];
        double actualLeftMargin[2];
        double actualRightMargin[2];
        double leftWeight[2];    
        double rightWeight[2];  
        vpsc::Variable *vl[2], *vr[2];
};


class UnsatisfiableConstraintInfo {
    public:
        UnsatisfiableConstraintInfo(const vpsc::Constraint* c);
        
        unsigned leftVarIndex;
        unsigned rightVarIndex;
        double separation;
        bool equality;
        cola::CompoundConstraint *cc;

        std::string toString(void) const
        {
            std::stringstream stream;
            stream << "Unsatisfiable constraint: var(" << leftVarIndex << ") ";
            if (separation < 0)
            {
                stream << "- " << -separation;
            }
            else
            {
                stream << "+ " << separation;
            }
            stream << " " << ((equality) ? "== " : "<= ");
            stream << "var(" << rightVarIndex << ")";
            if (cc)
            {
                stream << "\n   From " << cc->toString();
            }

            return stream.str();
        }
};
typedef std::vector<UnsatisfiableConstraintInfo *> UnsatisfiableConstraintInfos;

} // namespace cola
#endif // _COMPOUND_CONSTRAINTS_H