Loading...
Searching...
No Matches
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 <bliss/stats.hh>
#include <bliss/kqueue.hh>
#include <bliss/heap.hh>
#include <bliss/orbit.hh>
#include <bliss/partition.hh>
#include <bliss/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;
};
} // namespace bliss
bliss::AbstractGraph
An abstract base class for different types of graphs.
Definition abstractgraph.hh:48
bliss::AbstractGraph::set_long_prune_activity
void set_long_prune_activity(const bool active)
Definition abstractgraph.hh:247
bliss::AbstractGraph::set_verbose_level
void set_verbose_level(const unsigned int level)
Definition abstractgraph.cc:89
bliss::AbstractGraph::write_dot
virtual void write_dot(const char *const file_name)=0
bliss::AbstractGraph::is_automorphism
virtual bool is_automorphism(const std::vector< unsigned int > &perm) const =0
bliss::AbstractGraph::permute
virtual AbstractGraph * permute(const unsigned int *const perm) const =0
bliss::AbstractGraph::is_automorphism
virtual bool is_automorphism(unsigned int *const perm) const =0
bliss::AbstractGraph::get_hash
virtual unsigned int get_hash()=0
bliss::AbstractGraph::add_vertex
virtual unsigned int add_vertex(const unsigned int color=0)=0
bliss::AbstractGraph::add_edge
virtual void add_edge(const unsigned int source, const unsigned int target)=0
bliss::AbstractGraph::get_nof_vertices
virtual unsigned int get_nof_vertices() const =0
bliss::AbstractGraph::permute
virtual AbstractGraph * permute(const std::vector< unsigned int > &perm) const =0
bliss::AbstractGraph::change_color
virtual void change_color(const unsigned int vertex, const unsigned int color)=0
bliss::AbstractGraph::write_dot
virtual void write_dot(FILE *const fp)=0
bliss::AbstractGraph::get_color
virtual unsigned int get_color(const unsigned int vertex) const =0
bliss::AbstractGraph::canonical_form
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)
Definition abstractgraph.cc:1757
bliss::AbstractGraph::set_verbose_file
void set_verbose_file(FILE *const fp)
Definition abstractgraph.cc:95
bliss::AbstractGraph::set_component_recursion
void set_component_recursion(const bool active)
Definition abstractgraph.hh:110
bliss::AbstractGraph::find_automorphisms
void find_automorphisms(Stats &stats, const std::function< void(unsigned int n, const unsigned int *aut)> &report=nullptr, const std::function< bool()> &terminate=nullptr)
Definition abstractgraph.cc:1745
bliss::AbstractGraph::write_dimacs
virtual void write_dimacs(FILE *const fp)=0
bliss::AbstractGraph::set_failure_recording
void set_failure_recording(const bool active)
Definition abstractgraph.hh:96
bliss::Heap
A min-heap of unsigned integers.
Definition heap.hh:32
bliss::Orbit
A class for representing orbit information.
Definition orbit.hh:37
bliss::Partition::Cell
Data structure for holding information about a cell in a Partition.
Definition partition.hh:51
bliss::Partition
A class for refinable, backtrackable ordered partitions.
Definition partition.hh:45
bliss::Stats
Statistics returned by the bliss search algorithm.
Definition stats.hh:32
bliss::UintSeqHash
A updatable hash for sequences of unsigned ints.
Definition uintseqhash.hh:28
bliss
Definition abstractgraph.cc:35