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