abstractgraph.hh

#pragma once
 
/*
  Copyright (c) 2003-2021 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 {
  class AbstractGraph;
}
 
#include <cstdio>
#include <functional>
#include <vector>
#include "stats.hh"
#include "kqueue.hh"
#include "heap.hh"
#include "orbit.hh"
#include "partition.hh"
#include "uintseqhash.hh"
 
namespace bliss {
 
 
class AbstractGraph
{
  friend class Partition;
 
public:
  AbstractGraph();
  virtual ~AbstractGraph();
 
  void set_verbose_level(const unsigned int level);
 
  void set_verbose_file(FILE * const fp);
 
  virtual unsigned int add_vertex(const unsigned int color = 0) = 0;
 
  virtual void add_edge(const unsigned int source, const unsigned int target) = 0;
 
  virtual unsigned int get_color(const unsigned int vertex) const = 0;
 
  virtual void change_color(const unsigned int vertex, const unsigned int color) = 0;
 
 
  void set_failure_recording(const bool active) {
    assert(not in_search);
    opt_use_failure_recording = active;
  }
 
  void set_component_recursion(const bool active) {
    assert(not in_search);
    opt_use_comprec = active;
  }
 
 
 
  virtual unsigned int get_nof_vertices() const = 0;
 
  virtual AbstractGraph* permute(const unsigned int* const perm) const = 0;
 
  virtual AbstractGraph* permute(const std::vector<unsigned int>& perm) const = 0;
 
  virtual bool is_automorphism(unsigned int* const perm) const = 0;
 
  virtual bool is_automorphism(const std::vector<unsigned int>& perm) const = 0;
 
  void find_automorphisms(Stats& stats,
              const std::function<void(unsigned int n, const unsigned int* aut)>& report = nullptr,
              const std::function<bool()>& terminate = nullptr);
 
  const unsigned int* canonical_form(Stats& stats,
                     const std::function<void(unsigned int n, const unsigned int* aut)>& report = nullptr,
                     const std::function<bool()>& terminate = nullptr);
 
  virtual void write_dimacs(FILE * const fp) = 0;
 
  virtual void write_dot(FILE * const fp) = 0;
 
  virtual void write_dot(const char * const file_name) = 0;
 
  virtual unsigned int get_hash() = 0;
 
  void set_long_prune_activity(const bool active) {
    assert(not in_search);
    opt_use_long_prune = active;
  }
 
 
 
protected:
  unsigned int verbose_level;
 
  FILE *verbstr;
 
  Partition p;
 
  bool in_search;
 
  bool opt_use_failure_recording;
 
  /* The "tree-specific" invariant value for the point when current path
   * got different from the first path */
  unsigned int failure_recording_fp_deviation;
 
  bool opt_use_comprec;
 
 
  unsigned int refine_current_path_certificate_index;
  bool refine_compare_certificate;
  bool refine_equal_to_first;
  unsigned int refine_first_path_subcertificate_end;
  int refine_cmp_to_best;
  unsigned int refine_best_path_subcertificate_end;
 
  static const unsigned int CERT_SPLIT = 0; //UINT_MAX;
  static const unsigned int CERT_EDGE  = 1; //UINT_MAX-1;
  void cert_add(const unsigned int v1,
        const unsigned int v2,
        const unsigned int v3);
 
  void cert_add_redundant(const unsigned int x,
              const unsigned int y,
              const unsigned int z);
 
  bool opt_use_long_prune;
  static const unsigned int long_prune_options_max_mem = 50;
  static const unsigned int long_prune_options_max_stored_auts = 100;
 
  unsigned int long_prune_max_stored_autss;
  std::vector<std::vector<bool> *> long_prune_fixed;
  std::vector<std::vector<bool> *> long_prune_mcrs;
  std::vector<bool> long_prune_temp;
  unsigned int long_prune_begin;
  unsigned int long_prune_end;
  void long_prune_init();
  void long_prune_deallocate();
  void long_prune_add_automorphism(const unsigned int *aut);
  std::vector<bool>& long_prune_get_fixed(const unsigned int index);
  std::vector<bool>& long_prune_allocget_fixed(const unsigned int index);
  std::vector<bool>& long_prune_get_mcrs(const unsigned int index);
  std::vector<bool>& long_prune_allocget_mcrs(const unsigned int index);
  void long_prune_swap(const unsigned int i, const unsigned int j);
 
  /*
   * Data structures and routines for refining the partition p into equitable
   */
  Heap neighbour_heap;
  virtual bool split_neighbourhood_of_unit_cell(Partition::Cell * const) = 0;
  virtual bool split_neighbourhood_of_cell(Partition::Cell * const) = 0;
  void refine_to_equitable();
  void refine_to_equitable(Partition::Cell * const unit_cell);
  void refine_to_equitable(Partition::Cell * const unit_cell1,
               Partition::Cell * const unit_cell2);
 
 
  bool do_refine_to_equitable();
 
  unsigned int eqref_max_certificate_index;
  bool compute_eqref_hash;
  UintSeqHash eqref_hash;
 
 
  virtual bool is_equitable() const = 0;
 
  unsigned int *first_path_labeling;
  unsigned int *first_path_labeling_inv;
  Orbit         first_path_orbits;
  unsigned int *first_path_automorphism;
 
  unsigned int *best_path_labeling;
  unsigned int *best_path_labeling_inv;
  Orbit         best_path_orbits;
  unsigned int *best_path_automorphism;
 
  void update_labeling(unsigned int * const lab);
  void update_labeling_and_its_inverse(unsigned int * const lab,
                       unsigned int * const lab_inv);
  void update_orbit_information(Orbit &o, const unsigned int *perm);
 
  void reset_permutation(unsigned int *perm);
 
  std::vector<unsigned int> certificate_current_path;
  std::vector<unsigned int> certificate_first_path;
  std::vector<unsigned int> certificate_best_path;
 
  unsigned int certificate_index;
  virtual void initialize_certificate() = 0;
 
  /* Remove duplicates from seq.
   * If m is the largest element in seq, them m < tmp.size() must hold.
   * All entries in tmp must be false when called.
   * Under that condition, all entries in tmp are false on exit as well.
   */
  static void remove_duplicates(std::vector<unsigned int>& seq, std::vector<bool>& tmp);
 
  virtual void remove_duplicate_edges() = 0;
  virtual void make_initial_equitable_partition() = 0;
  virtual Partition::Cell* find_next_cell_to_be_splitted(Partition::Cell *cell) = 0;
 
 
  typedef struct {
    unsigned int splitting_element;
    unsigned int certificate_index;
    unsigned int subcertificate_length;
    UintSeqHash eqref_hash;
  } PathInfo;
 
  void search(const bool canonical, Stats &stats,
          const std::function<void(unsigned int n, const unsigned int* aut)>& report_function = nullptr,
          const std::function<bool()>& terminate = nullptr);
 
 
  /*
   *
   * Nonuniform component recursion (NUCR)
   *
   */
 
  /* The currently traversed component */
  unsigned int cr_level;
 
  class CR_CEP {
  public:
    unsigned int creation_level;
    unsigned int discrete_cell_limit;
    unsigned int next_cr_level;
    unsigned int next_cep_index;
    bool first_checked;
    bool best_checked;
  };
  std::vector<CR_CEP> cr_cep_stack;
 
  virtual bool nucr_find_first_component(const unsigned int level) = 0;
  virtual bool nucr_find_first_component(const unsigned int level,
                     std::vector<unsigned int>& component,
                     unsigned int& component_elements,
                     Partition::Cell*& sh_return) = 0;
  std::vector<unsigned int> cr_component;
  unsigned int cr_component_elements;
 
  std::vector<PathInfo> first_path_info;
 
public:
 
  std::vector<PathInfo> get_first_path_info() { return first_path_info; }
 
};
 
} // namespace bliss