cluster.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-2014  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):  Tim Dwyer
 *             Michael Wybrow
*/

#ifndef COLA_CLUSTER_H
#define COLA_CLUSTER_H

#include <cstdio>

#include "libvpsc/rectangle.h"
#include "libvpsc/variable.h"

#include "libcola/compound_constraints.h"
#include "libcola/commondefs.h"
#include "libcola/box.h"
#include "libcola/shapepair.h"

namespace cola {

class Cluster;
typedef std::vector<Cluster *> Clusters;
typedef std::vector<Clusters> ClustersList;

class Cluster
{
    public:
        Cluster();

// 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 ~Cluster();
#endif
        virtual void computeBoundary(const vpsc::Rectangles& rs) = 0;
        virtual void computeBoundingRect(const vpsc::Rectangles& rs);

        virtual void addChildNode(unsigned index);
        void addChildCluster(Cluster *cluster);
        
        virtual cola::Box padding(void) const
        {
            return cola::Box();
        }
        virtual cola::Box margin(void) const
        {
            return cola::Box();
        }

        void setDesiredBounds(const vpsc::Rectangle bounds);
        void unsetDesiredBounds();
        void createVars(const vpsc::Dim dim, const vpsc::Rectangles& rs,
                vpsc::Variables& vars);
        virtual void printCreationCode(FILE *fp) const = 0;
        virtual void countContainedNodes(std::vector<unsigned>& counts);
        virtual bool clusterIsFromFixedRectangle(void) const;
        virtual void outputToSVG(FILE *fp) const = 0;
        
        // Returns the total area covered by contents of this cluster
        // (not including space between nodes/clusters).
        double area(const vpsc::Rectangles& rs);
        
        // Sets bounds based on the finalPositions of vMin and vMax.
        //
        void updateBounds(const vpsc::Dim dim);
        
        virtual void computeVarRect(vpsc::Variables& vs, size_t dim);

        vpsc::Rectangle bounds;
        vpsc::Rectangle varRect;
        vpsc::Variable *vXMin, *vXMax, *vYMin, *vYMax;

        // This will be the id of the left/bottom boundary, 
        // and the right/top will be clusterVarId + 1.
        unsigned clusterVarId; 

        double varWeight;
        double internalEdgeWeightFactor;
        std::set<unsigned> nodes;
        std::vector<Cluster*> clusters;
        std::valarray<double> hullX, hullY;
        
    protected:
        void recPathToCluster(RootCluster *rootCluster, 
                Clusters currentPath);
        bool includesAllNodesFrom(const Cluster *rhs) const;
        
        // The following are for handling the generation of the correct
        // set of non-overlap constraints in the case overlapping clusters
        // (i.e., multiple inheritence). 1) We need to exclude the overlapping
        // clusters from having non-overlap constraints.  2) We replace nodes
        // with multiple parent clusters when enforcing non-overlap with their 
        // siblings and instead inforce non-overlap with the other clusters 
        // they are part of, since otherwise there is nothing stopping the
        // other siblings of each cluster from overlapping each other.  3) We 
        // also need to enforce overlap still between the set of nodes replaced
        // from each cluster in this way, since they may now be part of some
        // new set.
        std::set<ShapePair> m_cluster_cluster_overlap_exceptions;
        std::map<unsigned, Cluster *> m_overlap_replacement_map;
        std::set<unsigned> m_nodes_replaced_with_clusters;

    private:
        friend class ConstrainedFDLayout;
        friend class RootCluster;

        bool desiredBoundsSet;
        vpsc::Rectangle desiredBounds;

        vpsc::Variable *vMin, *vMax;
};


class RootCluster : public Cluster 
{
    public:
        RootCluster();
        void computeBoundary(const vpsc::Rectangles& rs);
        // There are just shapes at the top level, so
        // effectively no clusters in the diagram scene.
        bool flat(void) const
        {
            return clusters.empty();
        }
        virtual void printCreationCode(FILE *fp) const;
        virtual void outputToSVG(FILE *fp) const;

        bool allowsMultipleParents(void) const;

        void setAllowsMultipleParents(const bool value);
   private:
        void calculateClusterPathsToEachNode(size_t nodesCount);
        
        friend class ConstrainedFDLayout;
        friend class Cluster;

        bool m_allows_multiple_parents;
        
        std::vector<ClustersList> m_cluster_vectors_leading_to_nodes;
};

class RectangularCluster : public Cluster
{
    public:
        RectangularCluster();
        RectangularCluster(unsigned rectIndex);

        void setMargin(double margin);
        void setMargin(const cola::Box margin);
        cola::Box margin(void) const;

        void setPadding(double padding);
        void setPadding(const cola::Box padding);
        cola::Box padding(void) const;

#ifndef SWIG
        virtual ~RectangularCluster();
#endif
        void computeBoundary(const vpsc::Rectangles& rs);
        virtual void countContainedNodes(std::vector<unsigned>& counts);
        virtual void printCreationCode(FILE *fp) const;
        virtual void outputToSVG(FILE *fp) const;
        virtual void computeBoundingRect(const vpsc::Rectangles& rs);
        virtual void addChildNode(unsigned index);
        inline vpsc::Rectangle *getMinEdgeRect(const vpsc::Dim dim)
        {
            if (minEdgeRect[dim])
            {
                delete minEdgeRect[dim];
            }
            minEdgeRect[dim] = new vpsc::Rectangle(bounds);

            // Set the Min and Max positions to be the min minus an offset.
            double edgePosition = minEdgeRect[dim]->getMinD(dim);
            minEdgeRect[dim]->setMinD(dim, edgePosition - m_margin.min(dim));
            minEdgeRect[dim]->setMaxD(dim, edgePosition);

            return minEdgeRect[dim];
        }

        inline vpsc::Rectangle *getMaxEdgeRect(const vpsc::Dim dim)
        {
            if (maxEdgeRect[dim])
            {
                delete maxEdgeRect[dim];
            }
            maxEdgeRect[dim] = new vpsc::Rectangle(bounds);

            // Set the Min and Max positions to be the max plus an offset.
            double edgePosition = maxEdgeRect[dim]->getMaxD(dim);
            maxEdgeRect[dim]->setMaxD(dim, edgePosition + m_margin.max(dim));
            maxEdgeRect[dim]->setMinD(dim, edgePosition);

            return maxEdgeRect[dim];
        }
        virtual bool clusterIsFromFixedRectangle(void) const;
        int rectangleIndex(void) const;
    
        // For fixed sized clusters based on a rectangle, this method 
        // generates the constraints that attach the cluster edges to the
        // centre position of the relevant rectangle.
        void generateFixedRectangleConstraints(
                cola::CompoundConstraints& idleConstraints,
                vpsc::Rectangles& rc, vpsc::Variables (&vars)[2]) const;
    
    private:
        vpsc::Rectangle *minEdgeRect[2];
        vpsc::Rectangle *maxEdgeRect[2];
        int m_rectangle_index;
        Box m_margin;
        Box m_padding;
};

class ConvexCluster : public Cluster
{
    public:
        void computeBoundary(const vpsc::Rectangles& rs);
        virtual void printCreationCode(FILE *fp) const;
        virtual void outputToSVG(FILE *fp) const;

        std::valarray<unsigned> hullRIDs;
        std::valarray<unsigned char> hullCorners;
};


} // namespace cola
#endif // COLA_CLUSTER_H