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 "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