Loading...
Searching...
No Matches
graph.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/>.
*/
#include <bliss/abstractgraph.hh>
namespace bliss {
class Graph : public AbstractGraph
{
public:
typedef enum {
shs_f = 0,
shs_fs,
shs_fl,
shs_fm,
shs_fsm,
shs_flm
} SplittingHeuristic;
protected:
class Vertex {
public:
Vertex();
~Vertex();
void add_edge(const unsigned int other_vertex);
void remove_duplicate_edges(std::vector<bool>& tmp);
void sort_edges();
unsigned int color;
std::vector<unsigned int> edges;
unsigned int nof_edges() const {return edges.size(); }
};
std::vector<Vertex> vertices;
void sort_edges();
void remove_duplicate_edges();
static unsigned int vertex_color_invariant(const Graph* const g,
const unsigned int v);
static unsigned int degree_invariant(const Graph* const g,
const unsigned int v);
static unsigned int selfloop_invariant(const Graph* const g,
const unsigned int v);
bool refine_according_to_invariant(unsigned int (*inv)(const Graph* const g,
const unsigned int v));
/*
* Routines needed when refining the partition p into equitable
*/
bool split_neighbourhood_of_unit_cell(Partition::Cell * const);
bool split_neighbourhood_of_cell(Partition::Cell * const);
bool is_equitable() const;
/* Splitting heuristics, documented in more detail in graph.cc */
SplittingHeuristic sh;
Partition::Cell* find_next_cell_to_be_splitted(Partition::Cell *cell);
Partition::Cell* sh_first();
Partition::Cell* sh_first_smallest();
Partition::Cell* sh_first_largest();
Partition::Cell* sh_first_max_neighbours();
Partition::Cell* sh_first_smallest_max_neighbours();
Partition::Cell* sh_first_largest_max_neighbours();
/* A data structure used in many functions.
* Allocated only once to reduce allocation overhead,
* may be used only in one function at a time.
*/
std::vector<Partition::Cell*> _neighbour_cells;
void make_initial_equitable_partition();
void initialize_certificate();
bool nucr_find_first_component(const unsigned int level);
bool nucr_find_first_component(const unsigned int level,
std::vector<unsigned int>& component,
unsigned int& component_elements,
Partition::Cell*& sh_return);
public:
Graph(const unsigned int N = 0);
~Graph();
static Graph* read_dimacs(FILE* const fp, FILE* const errstr = stderr);
void write_dimacs(FILE* const fp);
void write_dot(FILE* const fp);
void write_dot(const char* const file_name);
virtual unsigned int get_hash();
unsigned int get_nof_vertices() const {return vertices.size(); }
Graph* permute(const unsigned int* const perm) const;
Graph* permute(const std::vector<unsigned int>& perm) const;
bool is_automorphism(unsigned int* const perm) const;
bool is_automorphism(const std::vector<unsigned int>& perm) const;
unsigned int add_vertex(const unsigned int color = 0);
void add_edge(const unsigned int v1, const unsigned int v2);
unsigned int get_color(const unsigned int vertex) const;
void change_color(const unsigned int vertex, const unsigned int color);
Graph* copy() const;
int cmp(Graph& other);
void set_splitting_heuristic(const SplittingHeuristic shs) {sh = shs; }
};
} // namespace bliss
bliss::Graph
The class for undirected, vertex colored graphs.
Definition graph.hh:32
bliss::Graph::add_edge
void add_edge(const unsigned int v1, const unsigned int v2)
Definition graph.cc:115
bliss::Graph::copy
Graph * copy() const
Definition graph.cc:141
bliss::Graph::SplittingHeuristic
SplittingHeuristic
Definition graph.hh:42
bliss::Graph::shs_f
@ shs_f
Definition graph.hh:46
bliss::Graph::shs_fl
@ shs_fl
Definition graph.hh:52
bliss::Graph::shs_fsm
@ shs_fsm
Definition graph.hh:60
bliss::Graph::shs_fm
@ shs_fm
Definition graph.hh:56
bliss::Graph::shs_fs
@ shs_fs
Definition graph.hh:49
bliss::Graph::shs_flm
@ shs_flm
Definition graph.hh:64
bliss::Graph::set_splitting_heuristic
void set_splitting_heuristic(const SplittingHeuristic shs)
Definition graph.hh:276
bliss::Graph::get_nof_vertices
unsigned int get_nof_vertices() const
Definition graph.hh:210
bliss::Graph::cmp
int cmp(Graph &other)
Definition graph.cc:377
bliss::Graph::write_dimacs
void write_dimacs(FILE *const fp)
Definition graph.cc:327
bliss::Graph::get_color
unsigned int get_color(const unsigned int vertex) const
Definition graph.cc:126
bliss::Graph::read_dimacs
static Graph * read_dimacs(FILE *const fp, FILE *const errstr=stderr)
Definition graph.cc:165
bliss::Graph::change_color
void change_color(const unsigned int vertex, const unsigned int color)
Definition graph.cc:132
bliss::Graph::is_automorphism
bool is_automorphism(unsigned int *const perm) const
Definition graph.cc:1387
bliss::Graph::permute
Graph * permute(const unsigned int *const perm) const
Definition graph.cc:450
bliss::Graph::Graph
Graph(const unsigned int N=0)
Definition graph.cc:91
bliss::Graph::write_dot
void write_dot(FILE *const fp)
Definition graph.cc:498
bliss::Graph::get_hash
virtual unsigned int get_hash()
Definition graph.cc:539
bliss::Graph::~Graph
~Graph()
Definition graph.cc:98
bliss::Graph::add_vertex
unsigned int add_vertex(const unsigned int color=0)
Definition graph.cc:105
bliss
Definition abstractgraph.cc:35