problem.h

Go to the documentation of this file.

/*
 *   libpal - Automated Placement of Labels Library
 *
 *   Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
 *                      University of Applied Sciences, Western Switzerland
 *                      http://www.hes-so.ch
 *
 *   Contact:
 *      maxence.laurent <at> heig-vd <dot> ch
 *    or
 *      eric.taillard <at> heig-vd <dot> ch
 *
 * This file is part of libpal.
 *
 * libpal is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * libpal 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.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with libpal.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#ifndef _PROBLEM_H
#define _PROBLEM_H

#include <list>
#include <pal/pal.h>
#include "rtree.hpp"

namespace pal
{

  class LabelPosition;
  class Label;

  class Sol
  {
    public:
      int *s;
      double cost;
  };

  typedef struct _subpart
  {
    int probSize;

    int borderSize;

    int subSize;

    int *sub;
    int *sol;
    int seed;
  } SubPart;

  typedef struct _chain
  {
    int degree;
    double delta;
    int *feat;
    int *label;
  } Chain;

  class CORE_EXPORT Problem
  {

      friend class Pal;

    private:

      int nbLabelledLayers;

      char **labelledLayersName;

      int nblp;
      int all_nblp;

      int nbft;


      bool displayAll;

      double bbox[4];

      double scale;

      double *labelPositionCost;
      int *nbOlap;

      LabelPosition **labelpositions;

      RTree<LabelPosition*, double, 2, double> *candidates;  // index all candidates
      RTree<LabelPosition*, double, 2, double> *candidates_sol; // index active candidates
      RTree<LabelPosition*, double, 2, double> *candidates_subsol; // idem for subparts

      //int *feat;        // [nblp]
      int *featStartId; // [nbft]
      int *featNbLp;    // [nbft]
      double *inactiveCost; //

      Sol *sol;         // [nbft]
      int nbActive;

      double nbOverlap;

      int *featWrap;

      Chain *chain( SubPart *part, int seed );

      Chain *chain( int seed );

      Pal *pal;

      void solution_cost();
      void check_solution();

    public:
      Problem();

      //Problem(char *lorena_file, bool displayAll);

      ~Problem();

      // problem inspection functions
      int getNumFeatures() { return nbft; }
      // features counted 0...n-1
      int getFeatureCandidateCount( int i ) { return featNbLp[i]; }
      // both features and candidates counted 0..n-1
      LabelPosition* getFeatureCandidate( int fi, int ci ) { return labelpositions[ featStartId[fi] + ci]; }


      void reduce();


      void post_optimization();


      void popmusic();

      void chain_search();

      std::list<LabelPosition*> * getSolution( bool returnInactive );

      PalStat * getStats();

      /* useful only for postscript post-conversion*/
      //void toFile(char *label_file);

      SubPart *subPart( int r, int featseed, int *isIn );

      void initialization();

      double compute_feature_cost( SubPart *part, int feat_id, int label_id, int *nbOverlap );
      double compute_subsolution_cost( SubPart *part, int *s, int * nbOverlap );

      double popmusic_chain( SubPart *part );

      double popmusic_tabu( SubPart *part );
      double popmusic_tabu_chain( SubPart *part );

      void init_sol_empty();
      void init_sol_falp();

      static bool compareLabelArea( pal::LabelPosition* l1, pal::LabelPosition* l2 );

#ifdef _EXPORT_MAP_
      void drawLabels( std::ofstream &svgmap );
#endif

  };

} // namespace

#endif