Quelle partition.hh Sprache: C

#ifndef BLISS_PARTITION_HH
#define BLISS_PARTITION_HH

/*
  Copyright (c) 2003-2015 Tommi Junttila
  Released under the GNU Lesser General Public License version 3.

  This file is part of bliss.

  bliss 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, version 3 of the License.

  bliss 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 Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with bliss.  If not, see <http://www.gnu.org/licenses/>.
*/

namespace bliss_digraphs {
  class Partition;
}

#include <cstdlib>
#include <cstdio>
#include <climits>
#include "kstack.hh"
#include "kqueue.hh"
#include "heap.hh"
#include "orbit.hh"
#include "graph.hh"

namespace bliss_digraphs {

/** \internal
* \brief A class for refinable, backtrackable ordered partitions.
*
* This is rather a data structure with some helper functions than
* a proper self-contained class.
* That is, for efficiency reasons the fields of this class are directly
* manipulated from bliss::AbstractGraph and its subclasses.
* Conversely, some methods of this class modify the fields of
* bliss::AbstractGraph, too.
*/
class Partition
{
public:
  /**
   * \brief Data structure for holding information about a cell in a Partition.
   */
  class Cell
  {
    friend class Partition;
  public:
    unsigned int length;
    /* Index of the first element of the cell in
       the Partition::elements array */
    unsigned int first;
    unsigned int max_ival;
    unsigned int max_ival_count;
  private:
    bool in_splitting_queue;
  public:
    bool in_neighbour_heap;
    /* Pointer to the next cell, null if this is the last one. */
    Cell* next;
    Cell* prev;
    Cell* next_nonsingleton;
    Cell* prev_nonsingleton;
    unsigned int split_level;
    /** Is this a unit cell? */
    bool is_unit() const {return(length == 1); }
    /** Is this cell in splitting queue? */
    bool is_in_splitting_queue() const {return(in_splitting_queue); }
  };

private:

  /** \internal
   * Data structure for remembering information about splits in order to
   * perform efficient backtracking over the splits.
   */
  class RefInfo {
  public:
    unsigned int split_cell_first;
    int prev_nonsingleton_first;
    int next_nonsingleton_first;
  };
  /** \internal
   * A stack for remembering the splits, used for backtracking.
   */
  KStack<RefInfo> refinement_stack;

  class BacktrackInfo {
  public:
    unsigned int refinement_stack_size;
    unsigned int cr_backtrack_point;
  };

  /** \internal
   * The main stack for enabling backtracking.
   */
  std::vector<BacktrackInfo> bt_stack;

public:
  AbstractGraph* graph;

  /* Used during equitable partition refinement */
  KQueue<Cell*> splitting_queue;
  void  splitting_queue_add(Cell* const cell);
  Cell* splitting_queue_pop();
  bool  splitting_queue_is_empty() const;
  void  splitting_queue_clear();

  /** Type for backtracking points. */
  typedef unsigned int BacktrackPoint;

  /**
   * Get a new backtrack point for the current partition
   */
  BacktrackPoint set_backtrack_point();

  /**
   * Backtrack to the point \a p and remove it.
   */
  void goto_backtrack_point(BacktrackPoint p);

  /**
   * Split the non-unit Cell \a cell = {\a element,e1,e2,...,en} containing
   * the element \a element in two:
   * \a cell = {e1,...,en} and \a newcell = {\a element}.
   * @param cell     a non-unit Cell
   * @param element  an element in \a cell
   * @return         the new unit Cell \a newcell
   */
  Cell* individualize(Cell* const cell,
        const unsigned int element);

  Cell* aux_split_in_two(Cell* const cell,
    const unsigned int first_half_size);

private:
  unsigned int N;
  std::vector<Cell> cells_vec;
  typedef std::vector<Cell>::iterator cell_pointer_substitute;
  cell_pointer_substitute cells;
  Cell* free_cells;
  unsigned int discrete_cell_count;
public:
  Cell* first_cell;
  Cell* first_nonsingleton_cell;

  typedef std::vector<unsigned int>::iterator uint_pointer_substitute;
  typedef std::vector<unsigned int>::const_iterator
                            uint_pointer_to_const_substitute;
  std::vector<unsigned int> elements_vec;
  uint_pointer_substitute elements;
  /* invariant_values[e] gives the invariant value of the element e */
  std::vector<unsigned int> invariant_values_vec;
  uint_pointer_substitute invariant_values;
  /* element_to_cell_map[e] gives the cell of the element e */

  typedef std::vector<Cell*>::iterator
      cell_pointer_pointer_substitute;

  std::vector<Cell*> element_to_cell_map_vec;
  cell_pointer_pointer_substitute element_to_cell_map;
  /** Get the cell of the element \a e */
  Cell* get_cell(const unsigned int e) const {
    return element_to_cell_map_vec[e];
  }
  /* in_pos[e] points to the elements array s.t. *in_pos[e] = e  */
  std::vector<uint_pointer_substitute> in_pos_vec;
  std::vector<uint_pointer_substitute>::iterator in_pos;

  Partition();
  ~Partition();

  /**
   * Initialize the partition to the unit partition (all elements in one cell)
   * over the \a N > 0 elements {0,...,\a N-1}.
   */
  void init(const unsigned int N);

  /**
   * Returns true iff the partition is discrete, meaning that all
   * the elements are in their own cells.
   */
  bool is_discrete() const {return(free_cells == 0); }

  unsigned int nof_discrete_cells() const {return(discrete_cell_count); }

  /**
   * Print the partition into the file stream \a fp.
   */
  size_t print(FILE* const fp, const bool add_newline = true) const;

  /**
   * Print the partition cell sizes into the file stream \a fp.
   */
  size_t print_signature(FILE* const fp, const bool add_newline = true) const;

  /*
   * Splits the Cell \a cell into [cell_1,...,cell_n]
   * according to the invariant_values of the elements in \a cell.
   * After splitting, cell_1 == \a cell.
   * Returns the pointer to the Cell cell_n;
   * cell_n != cell iff the Cell \a cell was actually splitted.
   * The flag \a max_ival_info_ok indicates whether the max_ival and
   * max_ival_count fields of the Cell \a cell have consistent values
   * when the method is called.
   * Clears the invariant values of elements in the Cell \a cell as well as
   * the max_ival and max_ival_count fields of the Cell \a cell.
   */
  Cell *zplit_cell(Cell * const cell, const bool max_ival_info_ok);

  /*
   * Routines for component recursion
   */
  void cr_init();
  void cr_free();
  unsigned int cr_get_level(const unsigned int cell_index) const;
  unsigned int cr_split_level(const unsigned int level,
         const std::vector<unsigned int>& cells);

  /** Clear the invariant_values of the elements in the Cell \a cell. */
  void clear_ivs(Cell* const cell);

  /* Is component recursion support in use? */
  bool cr_enabled;

private:
  /*
   * Component recursion data structures
   */

  class CRCell {
  public:
    unsigned int level;
    CRCell* next;
    CRCell** prev_next_ptr;
    void detach() {
      if(next)
next->prev_next_ptr = prev_next_ptr;
      *(prev_next_ptr) = next;
      level = UINT_MAX;
      next = 0;
      prev_next_ptr = 0;
    }
  };
  typedef std::vector<CRCell>::iterator crcell_pointer_substitute;
  std::vector<CRCell> cr_cells_vec;
  crcell_pointer_substitute cr_cells;

  typedef std::vector<CRCell*>::iterator crcell_pointer_pointer_substitute;
  std::vector<CRCell*> cr_levels_vec;
  crcell_pointer_pointer_substitute cr_levels;

  class CR_BTInfo {
  public:
    unsigned int created_trail_index;
    unsigned int splitted_level_trail_index;
  };
  std::vector<unsigned int> cr_created_trail;
  std::vector<unsigned int> cr_splitted_level_trail;
  std::vector<CR_BTInfo> cr_bt_info;
  unsigned int cr_max_level;
  void cr_create_at_level(const unsigned int cell_index, unsigned int level);
  void cr_create_at_level_trailed(const unsigned int cell_index, unsigned int level);
  unsigned int cr_get_backtrack_point();
  void cr_goto_backtrack_point(const unsigned int btpoint);

  /*
   *
   * Auxiliary routines for sorting and splitting cells
   *
   */
  Cell* sort_and_split_cell1(Cell* cell);
  Cell* sort_and_split_cell255(Cell* const cell, const unsigned int max_ival);
  bool shellsort_cell(Cell* cell);
  Cell* split_cell(Cell* const cell);

  /*
   * Some auxiliary stuff needed for distribution count sorting.
   * To make the code thread-safe (modulo the requirement that each graph is
   * only accessed in one thread at a time), the arrays are owned by
   * the partition instance, not statically defined.
   */
  unsigned int dcs_count[256];
  unsigned int dcs_start[256];
  void dcs_cumulate_count(const unsigned int max);
};

inline Partition::Cell*
Partition::splitting_queue_pop()
{
  Cell* const cell = splitting_queue.pop_front();
  cell->in_splitting_queue = false;
  return cell;
}

inline bool
Partition::splitting_queue_is_empty() const
{
  return splitting_queue.is_empty();
}

inline unsigned int
Partition::cr_get_level(const unsigned int cell_index) const
{
  return(cr_cells[cell_index].level);
}

} // namespace bliss_digraphs

#endif

quality100%

¤ Dauer der Verarbeitung: 0.17 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.