digraph.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 Digraph : 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_to(const unsigned int dest_vertex);
    void add_edge_from(const unsigned int source_vertex);
    void remove_duplicate_edges(std::vector<bool>& tmp);
    void sort_edges();
    unsigned int color;
    std::vector<unsigned int> edges_out;
    std::vector<unsigned int> edges_in;
    unsigned int nof_edges_in() const {return edges_in.size(); }
    unsigned int nof_edges_out() const {return edges_out.size(); }
  };
  std::vector<Vertex> vertices;
  void remove_duplicate_edges();
 
  static unsigned int vertex_color_invariant(const Digraph* const g,
                         const unsigned int v);
  static unsigned int indegree_invariant(const Digraph* const g,
                     const unsigned int v);
  static unsigned int outdegree_invariant(const Digraph* const g,
                      const unsigned int v);
  static unsigned int selfloop_invariant(const Digraph* const g,
                     const unsigned int v);
 
  bool refine_according_to_invariant(unsigned int (*inv)(const Digraph* 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 the cc-file. */
  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();
 
  void sort_edges();
 
  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:
  Digraph(const unsigned int N = 0);
 
  ~Digraph();
 
  static Digraph* 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(); }
  
  unsigned int add_vertex(const unsigned int color = 0);
 
  void add_edge(const unsigned int source, const unsigned int target);
 
  unsigned int get_color(const unsigned int vertex) const;
 
  void change_color(const unsigned int vertex, const unsigned int color);
 
  Digraph* copy() const;
  
  int cmp(Digraph& other);
 
  void set_splitting_heuristic(SplittingHeuristic shs) {sh = shs; }
 
  Digraph* permute(const unsigned int* const perm) const;  
 
  Digraph* 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;
};
 
} // namespace bliss