diff options
| author | Marc Jeanmougin <marc.jeanmougin@telecom-paristech.fr> | 2018-04-29 14:25:32 +0000 |
|---|---|---|
| committer | Marc Jeanmougin <marc.jeanmougin@telecom-paristech.fr> | 2018-04-29 14:25:32 +0000 |
| commit | ab5f8ff5869021958f4ae8b838c3d707a2e85eaa (patch) | |
| tree | 4907675828a5401d013b7587538cc8541edd2764 /src/libcola/cluster.cpp | |
| parent | moved libcroco, libuemf, libdepixelize to 3rdparty folder (diff) | |
| download | inkscape-ab5f8ff5869021958f4ae8b838c3d707a2e85eaa.tar.gz inkscape-ab5f8ff5869021958f4ae8b838c3d707a2e85eaa.zip | |
Put adaptagrams into its own folder
Diffstat (limited to 'src/libcola/cluster.cpp')
| -rw-r--r-- | src/libcola/cluster.cpp | 719 |
1 files changed, 0 insertions, 719 deletions
diff --git a/src/libcola/cluster.cpp b/src/libcola/cluster.cpp deleted file mode 100644 index d8b37d7b6..000000000 --- a/src/libcola/cluster.cpp +++ /dev/null @@ -1,719 +0,0 @@ -/* - * 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 -*/ - -#include "libvpsc/assertions.h" -#include "libcola/commondefs.h" -#include "libcola/cola.h" -#include "libcola/convex_hull.h" -#include "libcola/cluster.h" - -using vpsc::generateXConstraints; -using vpsc::generateYConstraints; -using namespace std; - -namespace cola { - -Cluster::Cluster() - : bounds(), - clusterVarId(0), - varWeight(0.0001), - internalEdgeWeightFactor(1.), - desiredBoundsSet(false), - desiredBounds() -{ - // XXX We use a really low weight here until we properly set the source - // of the variable value back in updatePositions() type manner. - varWeight = 0.0000001; -} - -Cluster::~Cluster() -{ - for_each(clusters.begin(), clusters.end(), delete_object()); - clusters.clear(); -} - -void Cluster::setDesiredBounds(const vpsc::Rectangle db) -{ - desiredBoundsSet = true; - desiredBounds = db; -} - -void Cluster::unsetDesiredBounds(void) -{ - desiredBoundsSet=false; -} - - -// Checks to see if the shape at the given index is contained within this -// cluster or its child clusters. -// -void Cluster::countContainedNodes(std::vector<unsigned>& counts) -{ - vector<unsigned> invalidNodes; - for (set<unsigned>::iterator it = nodes.begin(); it != nodes.end(); ++it) - { - unsigned nodeIndex = *it; - if (nodeIndex < counts.size()) - { - // Node index is valid, increase count. - counts[*it] += 1; - } - else - { - fprintf(stderr, "Warning: Invalid node index %u specified in " - "cluster. Ignoring...\n", nodeIndex); - invalidNodes.push_back(nodeIndex); - } - } - for (size_t i = 0; i < invalidNodes.size(); ++i) - { - nodes.erase(invalidNodes[i]); - } - - for (vector<Cluster*>::const_iterator i = clusters.begin(); - i != clusters.end(); ++i) - { - (*i)->countContainedNodes(counts); - } -} - -void Cluster::computeBoundingRect(const vpsc::Rectangles& rs) -{ - bounds = vpsc::Rectangle(); - for (vector<Cluster*>::const_iterator i = clusters.begin(); - i != clusters.end(); ++i) - { - (*i)->computeBoundingRect(rs); - vpsc::Rectangle rectangle = - (*i)->margin().rectangleByApplyingBox((*i)->bounds); - bounds = bounds.unionWith(rectangle); - } - for (set<unsigned>::const_iterator i = nodes.begin(); - i != nodes.end(); ++i) - { - vpsc::Rectangle* r=rs[*i]; - bounds = bounds.unionWith(*r); - } - bounds = padding().rectangleByApplyingBox(bounds); -} - -void Cluster::computeVarRect(vpsc::Variables& vars, size_t dim) -{ - if ((clusterVarId > 0) && (vars.size() > clusterVarId)) - { - varRect.setMinD(dim, vars[clusterVarId]->finalPosition); - varRect.setMaxD(dim, vars[clusterVarId + 1]->finalPosition); - } - - for (vector<Cluster*>::const_iterator i = clusters.begin(); - i != clusters.end(); ++i) - { - (*i)->computeVarRect(vars, dim); - } -} - -bool Cluster::clusterIsFromFixedRectangle(void) const -{ - return false; -} - -void ConvexCluster::computeBoundary(const vpsc::Rectangles& rs) -{ - unsigned n = 4 * nodes.size(); - valarray<double> X(n); - valarray<double> Y(n); - unsigned pctr = 0; - vector<unsigned> nodesVector(nodes.begin(), nodes.end()); - for (size_t i = 0; i < nodesVector.size(); ++i) - { - vpsc::Rectangle* r=rs[nodesVector[i]]; - // Bottom Right - X[pctr]=r->getMaxX(); - Y[pctr++]=r->getMinY(); - // Top Right - X[pctr]=r->getMaxX(); - Y[pctr++]=r->getMaxY(); - // Top Left - X[pctr]=r->getMinX(); - Y[pctr++]=r->getMaxY(); - // Bottom Left - X[pctr]=r->getMinX(); - Y[pctr++]=r->getMinY(); - } - /* - for(unsigned i=0;i<n;i++) { - printf("X[%d]=%f, Y[%d]=%f;\n",i,X[i],i,Y[i]); - } - */ - vector<unsigned> hull; - hull::convex(X,Y,hull); - hullX.resize(hull.size()); - hullY.resize(hull.size()); - hullRIDs.resize(hull.size()); - hullCorners.resize(hull.size()); - for (unsigned j=0;j<hull.size();j++) - { - hullX[j]=X[hull[j]]; - hullY[j]=Y[hull[j]]; - hullRIDs[j]=nodesVector[hull[j]/4]; - hullCorners[j]=hull[j]%4; - } -} - - -void ConvexCluster::printCreationCode(FILE *fp) const -{ - fprintf(fp, " ConvexCluster *cluster%llu = new ConvexCluster();\n", - (unsigned long long) this); - for(set<unsigned>::const_iterator i = nodes.begin(); - i != nodes.end(); ++i) - { - fprintf(fp, " cluster%llu->addChildNode(%u);\n", - (unsigned long long) this, *i); - } - for(vector<Cluster *>::const_iterator i = clusters.begin(); - i != clusters.end(); ++i) - { - (*i)->printCreationCode(fp); - fprintf(fp, " cluster%llu->addChildCluster(cluster%llu);\n", - (unsigned long long) this, (unsigned long long) *i); - } -} - -void ConvexCluster::outputToSVG(FILE *fp) const -{ - for(vector<Cluster *>::const_iterator i = clusters.begin(); - i != clusters.end(); ++i) - { - (*i)->outputToSVG(fp); - } -} - - -RectangularCluster::RectangularCluster() - : Cluster(), - m_rectangle_index(-1), - m_margin(0), - m_padding(0) -{ - minEdgeRect[vpsc::XDIM] = NULL; - minEdgeRect[vpsc::YDIM] = NULL; - maxEdgeRect[vpsc::XDIM] = NULL; - maxEdgeRect[vpsc::YDIM] = NULL; -} - -RectangularCluster::RectangularCluster(unsigned rectIndex) - : Cluster(), - m_rectangle_index(rectIndex), - m_margin(0), - m_padding(0) -{ - minEdgeRect[vpsc::XDIM] = NULL; - minEdgeRect[vpsc::YDIM] = NULL; - maxEdgeRect[vpsc::XDIM] = NULL; - maxEdgeRect[vpsc::YDIM] = NULL; -} - -RectangularCluster::~RectangularCluster() -{ - for (size_t dim = 0; dim < 2; ++dim) - { - if (minEdgeRect[dim]) - { - delete minEdgeRect[dim]; - minEdgeRect[dim] = NULL; - } - if (maxEdgeRect[dim]) - { - delete maxEdgeRect[dim]; - maxEdgeRect[dim] = NULL; - } - } -} - -void RectangularCluster::setMargin(const Box margin) -{ - m_margin = margin; -} - - -void RectangularCluster::setMargin(double margin) -{ - m_margin = Box(margin); -} - - -Box RectangularCluster::margin(void) const -{ - return m_margin; -} - - -void RectangularCluster::setPadding(const Box padding) -{ - m_padding = padding; -} - - -void RectangularCluster::setPadding(double padding) -{ - m_padding = Box(padding); -} - - -Box RectangularCluster::padding(void) const -{ - return m_padding; -} - - -void RectangularCluster::countContainedNodes(std::vector<unsigned>& counts) -{ - if (m_rectangle_index >= 0) - { - // This cluster is the shape in question. - counts[m_rectangle_index] += 1; - } - Cluster::countContainedNodes(counts); -} - - -void RectangularCluster::generateFixedRectangleConstraints( - cola::CompoundConstraints& idleConstraints, - vpsc::Rectangles& rc, vpsc::Variables (&vars)[2]) const -{ - COLA_UNUSED(vars); - - if (m_rectangle_index < 0) - { - // Not based on a Rectangle. - return; - } - - double halfWidth = rc[m_rectangle_index]->width() / 2; - double halfHeight = rc[m_rectangle_index]->height() / 2; - - cola::SeparationConstraint *sc = - new cola::SeparationConstraint(vpsc::XDIM, clusterVarId, - m_rectangle_index, halfWidth, true); - idleConstraints.push_back(sc); - sc = new cola::SeparationConstraint(vpsc::XDIM, - m_rectangle_index, clusterVarId + 1, halfWidth, true); - idleConstraints.push_back(sc); - - sc = new cola::SeparationConstraint(vpsc::YDIM, - clusterVarId, m_rectangle_index, halfHeight, true); - idleConstraints.push_back(sc); - sc = new cola::SeparationConstraint(vpsc::YDIM, - m_rectangle_index, clusterVarId + 1, halfHeight, true); - idleConstraints.push_back(sc); -} - - -void RectangularCluster::computeBoundary(const vpsc::Rectangles& rs) -{ - double xMin=DBL_MAX, xMax=-DBL_MAX, yMin=DBL_MAX, yMax=-DBL_MAX; - for (std::set<unsigned>::iterator it = nodes.begin(); - it != nodes.end(); ++it) - { - xMin=std::min(xMin,rs[*it]->getMinX()); - xMax=std::max(xMax,rs[*it]->getMaxX()); - yMin=std::min(yMin,rs[*it]->getMinY()); - yMax=std::max(yMax,rs[*it]->getMaxY()); - } - hullX.resize(4); - hullY.resize(4); - hullX[3]=xMin; - hullY[3]=yMin; - hullX[2]=xMin; - hullY[2]=yMax; - hullX[1]=xMax; - hullY[1]=yMax; - hullX[0]=xMax; - hullY[0]=yMin; -} - - -void RectangularCluster::printCreationCode(FILE *fp) const -{ - fprintf(fp, " RectangularCluster *cluster%llu = " - "new RectangularCluster(", - (unsigned long long) this); - if (m_rectangle_index != -1) - { - fprintf(fp, "%d", m_rectangle_index); - } - fprintf(fp, ");\n"); - if (!m_margin.empty()) - { - fprintf(fp, " cluster%llu->setMargin(", - (unsigned long long) this); - m_margin.outputCode(fp); - fprintf(fp, ");\n"); - } - if (!m_padding.empty()) - { - fprintf(fp, " cluster%llu->setPadding(", - (unsigned long long) this); - m_padding.outputCode(fp); - fprintf(fp, ");\n"); - } - for(set<unsigned>::const_iterator i = nodes.begin(); - i != nodes.end(); ++i) - { - fprintf(fp, " cluster%llu->addChildNode(%u);\n", - (unsigned long long) this, *i); - } - for(vector<Cluster *>::const_iterator i = clusters.begin(); - i != clusters.end(); ++i) - { - (*i)->printCreationCode(fp); - fprintf(fp, " cluster%llu->addChildCluster(cluster%llu);\n", - (unsigned long long) this, (unsigned long long) *i); - } -} - -void RectangularCluster::outputToSVG(FILE *fp) const -{ - double rounding = 4; - if (varRect.isValid()) - { - fprintf(fp, "<rect id=\"cluster-%llu-r\" x=\"%g\" y=\"%g\" width=\"%g\" " - "height=\"%g\" style=\"stroke-width: 1px; stroke: black; " - "fill: green; fill-opacity: 0.3;\" rx=\"%g\" ry=\"%g\" />\n", - (unsigned long long) this, varRect.getMinX(), varRect.getMinY(), - varRect.getMaxX() - varRect.getMinX(), - varRect.getMaxY() - varRect.getMinY(), rounding, rounding); - } - else - { - fprintf(fp, "<rect id=\"cluster-%llu\" x=\"%g\" y=\"%g\" width=\"%g\" " - "height=\"%g\" style=\"stroke-width: 1px; stroke: black; " - "fill: red; fill-opacity: 0.3;\" rx=\"%g\" ry=\"%g\" />\n", - (unsigned long long) this, bounds.getMinX(), bounds.getMinY(), - bounds.getMaxX() - bounds.getMinX(), - bounds.getMaxY() - bounds.getMinY(), rounding, rounding); - } - - for(vector<Cluster *>::const_iterator i = clusters.begin(); - i != clusters.end(); ++i) - { - (*i)->outputToSVG(fp); - } -} - - - -int RectangularCluster::rectangleIndex(void) const -{ - return m_rectangle_index; -} - -bool RectangularCluster::clusterIsFromFixedRectangle(void) const -{ - return (m_rectangle_index >= 0); -} - -void RectangularCluster::computeBoundingRect(const vpsc::Rectangles& rs) -{ - if (clusterIsFromFixedRectangle()) - { - // For bounds, just use this shape's rectangle. - bounds = *(rs[m_rectangle_index]); - } - else - { - Cluster::computeBoundingRect(rs); - } -} -void RectangularCluster::addChildNode(unsigned index) -{ - if ((m_rectangle_index == (int) index) && (m_rectangle_index > 0)) - { - fprintf(stderr, "Warning: ignoring cluster (%u) added as child of " - "itself.\n", index); - return; - } - Cluster::addChildNode(index); -} - - -RootCluster::RootCluster() - : m_allows_multiple_parents(false) -{ -} - -void Cluster::recPathToCluster(RootCluster *rootCluster, Clusters currentPath) -{ - // Reset cluster-cluster overlap exceptions. - m_cluster_cluster_overlap_exceptions.clear(); - m_nodes_replaced_with_clusters.clear(); - m_overlap_replacement_map.clear(); - - // Add this cluster to the path. - currentPath.push_back(this); - - // Recusively all on each child cluster. - for (unsigned i = 0; i < clusters.size(); ++i) - { - clusters[i]->recPathToCluster(rootCluster, currentPath); - } - - // And store the path to each child node. - for (std::set<unsigned>::iterator it = nodes.begin(); - it != nodes.end(); ++it) - { - rootCluster->m_cluster_vectors_leading_to_nodes[*it]. - push_back(currentPath); - } -} - - -void RootCluster::calculateClusterPathsToEachNode(size_t nodesCount) -{ - m_cluster_vectors_leading_to_nodes.clear(); - m_cluster_vectors_leading_to_nodes.resize(nodesCount); - - recPathToCluster(this, Clusters()); - - for (unsigned i = 0; i < m_cluster_vectors_leading_to_nodes.size(); ++i) - { - size_t paths = m_cluster_vectors_leading_to_nodes[i].size(); - for (size_t j = 1; j < paths; ++j) - { - for (size_t k = 0; k < j; ++k) - { - // For each pair of paths. - - // Find the lowest common ancestor by finding where the two - // paths from the root cluster to node i diverge. - Clusters pathJ = m_cluster_vectors_leading_to_nodes[i][j]; - Clusters pathK = m_cluster_vectors_leading_to_nodes[i][k]; - size_t lcaIndex = 0; - while ((lcaIndex < pathJ.size()) && - (lcaIndex < pathK.size()) && - (pathJ[lcaIndex] == pathK[lcaIndex])) - { - ++lcaIndex; - } - COLA_ASSERT(lcaIndex > 0); - - // lcaIndex will be the clusters/nodes that need to overlap - // due to these two paths to node i. - size_t lcaChildJIndex = i; - size_t lcaChildKIndex = i; - Cluster *lcaChildJCluster = NULL; - Cluster *lcaChildKCluster = NULL; - - // lcaIndex < path{J,K}.size() means the child J or K of - // the lca is a Cluster. At least one of them will always - // be a cluster. - COLA_ASSERT((lcaIndex < pathJ.size()) || - (lcaIndex < pathK.size())); - if (lcaIndex < pathJ.size()) - { - lcaChildJCluster = pathJ[lcaIndex]; - lcaChildJIndex = lcaChildJCluster->clusterVarId; - } - if (lcaIndex < pathK.size()) - { - lcaChildKCluster = pathK[lcaIndex]; - lcaChildKIndex = lcaChildKCluster->clusterVarId; - } - - // We want to exclude the overlapping children of the lca - // from having non-overlap constraints generated for them - // (siblings of a particular cluster usually have - // non-overlap constraints generated for them). - Cluster *lcaCluster = pathJ[lcaIndex - 1]; - lcaCluster->m_cluster_cluster_overlap_exceptions.insert( - ShapePair(lcaChildJIndex, lcaChildKIndex)); - - if (lcaChildJCluster) - { - // In cluster J, replace node i with cluster K for the - // purpose of non-overlap with siblings, and remember - // this replacement so we can still generate non-overlap - // constraints between multiple nodes that are children - // of the same overlapping clusters. - lcaChildJCluster->m_overlap_replacement_map[i] = - lcaChildKCluster; - lcaChildJCluster->m_nodes_replaced_with_clusters.insert(i); - } - - if (lcaChildKCluster) - { - // In cluster K, replace node i with cluster J for the - // purpose of non-overlap with siblings, and remember - // this replacement so we can still generate non-overlap - // constraints between multiple nodes that are children - // of the same overlapping clusters. - lcaChildKCluster->m_overlap_replacement_map[i] = - lcaChildJCluster; - lcaChildKCluster->m_nodes_replaced_with_clusters.insert(i); - } - } - } - } -} - - -void RootCluster::computeBoundary(const vpsc::Rectangles& rs) -{ - for (unsigned i = 0; i < clusters.size(); ++i) - { - clusters[i]->computeBoundary(rs); - } -} - -void RootCluster::printCreationCode(FILE *fp) const -{ - fprintf(fp, " RootCluster *cluster%llu = new RootCluster();\n", - (unsigned long long) this); - for(set<unsigned>::const_iterator i = nodes.begin(); - i != nodes.end(); ++i) - { - fprintf(fp, " cluster%llu->addChildNode(%u);\n", - (unsigned long long) this, *i); - } - for(vector<Cluster *>::const_iterator i = clusters.begin(); - i != clusters.end(); ++i) - { - (*i)->printCreationCode(fp); - fprintf(fp, " cluster%llu->addChildCluster(cluster%llu);\n", - (unsigned long long) this, (unsigned long long) *i); - } -} - -void RootCluster::outputToSVG(FILE *fp) const -{ - for(vector<Cluster *>::const_iterator i = clusters.begin(); - i != clusters.end(); ++i) - { - (*i)->outputToSVG(fp); - } - -} - - -bool RootCluster::allowsMultipleParents(void) const -{ - return m_allows_multiple_parents; -} - -void RootCluster::setAllowsMultipleParents(const bool value) -{ - m_allows_multiple_parents = value; -} - -void Cluster::updateBounds(const vpsc::Dim dim) -{ - if (dim == vpsc::HORIZONTAL) - { - bounds = vpsc::Rectangle(vMin->finalPosition, vMax->finalPosition, - bounds.getMinY(), bounds.getMaxY()); - } - else - { - bounds = vpsc::Rectangle(bounds.getMinX(), bounds.getMaxX(), - vMin->finalPosition, vMax->finalPosition); - } - for (unsigned i=0; i < clusters.size(); ++i) - { - clusters[i]->updateBounds(dim); - } -} - - -void Cluster::createVars(const vpsc::Dim dim, const vpsc::Rectangles& rs, - vpsc::Variables& vars) -{ - for (vector<Cluster*>::iterator i = clusters.begin(); - i != clusters.end(); ++i) - { - (*i)->createVars(dim, rs, vars); - } - if (dim==vpsc::HORIZONTAL) - { - double desiredMinX = bounds.getMinX(), desiredMaxX = bounds.getMaxX(); - if (desiredBoundsSet) - { - desiredMinX = desiredBounds.getMinX(); - desiredMaxX = desiredBounds.getMaxX(); - } - clusterVarId = vars.size(); - vars.push_back(vXMin = new vpsc::Variable( - vars.size(), desiredMinX, varWeight)); - vars.push_back(vXMax = new vpsc::Variable( - vars.size(), desiredMaxX, varWeight)); - } - else - { - double desiredMinY = bounds.getMinY(), desiredMaxY = bounds.getMaxY(); - if (desiredBoundsSet) - { - desiredMinY = desiredBounds.getMinY(); - desiredMaxY = desiredBounds.getMaxY(); - } - clusterVarId = vars.size(); - vars.push_back(vYMin = new vpsc::Variable( - vars.size(), desiredMinY, varWeight)); - vars.push_back(vYMax = new vpsc::Variable( - vars.size(), desiredMaxY, varWeight)); - } -} - -// Returns the total area covered by contents of this cluster (not -// including space between nodes/clusters). -// -double Cluster::area(const vpsc::Rectangles& rs) -{ - double a = 0; - for (set<unsigned>::iterator i = nodes.begin(); i != nodes.end(); ++i) - { - vpsc::Rectangle *r = rs[*i]; - a += r->width() * r->height(); - } - for (Clusters::iterator i = clusters.begin(); i!= clusters.end(); ++i) - { - a += (*i)->area(rs); - } - return a; -} - -void Cluster::addChildNode(unsigned index) -{ - this->nodes.insert(index); -} - -void Cluster::addChildCluster(Cluster *cluster) -{ - if (cluster == this) - { - fprintf(stderr, "Warning: ignoring cluster added as child of itself.\n"); - return; - } - this->clusters.push_back(cluster); -} - - -} // namespace cola |
