MinimumFeedbackSet.hh 4.64 KB
Newer Older
1
/*
2
 * Copyright © 2009-2019 Dynare Team
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
 *
 * This file is part of Dynare.
 *
 * Dynare is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * Dynare 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Dynare.  If not, see <http://www.gnu.org/licenses/>.
 */

20 21
#ifndef _MINIMUMFEEDBACKSET_HH
#define _MINIMUMFEEDBACKSET_HH
22 23 24

#include <map>
#include <vector>
25 26 27

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wold-style-cast"
28
#include <boost/graph/adjacency_list.hpp>
29
#pragma GCC diagnostic pop
30 31 32

using namespace std;

33 34
namespace MFS
{
35 36 37 38 39 40 41
  using VertexProperty_t = boost::property<boost::vertex_index_t, int,
                                           boost::property<boost::vertex_index1_t, int,
                                                           boost::property<boost::vertex_degree_t, int,
                                                                           boost::property<boost::vertex_in_degree_t, int,
                                                                                           boost::property<boost::vertex_out_degree_t, int >>>>>;
  using AdjacencyList_t = boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, VertexProperty_t>;
  using color_t = map<boost::graph_traits<AdjacencyList_t>::vertex_descriptor, boost::default_color_type>;
42
  using vector_vertex_descriptor_t = vector<AdjacencyList_t::vertex_descriptor>;
43

44
  //! Eliminate a vertex i
45
  /*! For a vertex i replace all edges e_k_i and e_i_j by a shorcut e_k_j and then Suppress the vertex i*/
46
  void Eliminate(AdjacencyList_t::vertex_descriptor vertex_to_eliminate, AdjacencyList_t &G);
47 48
  //! Collect all doublets (edges e_i_k such that there is an edge e_k_i with k!=i in the graph)
  /*! Returns the vector of doublets */
49
  vector_vertex_descriptor_t Collect_Doublet(AdjacencyList_t::vertex_descriptor vertex, AdjacencyList_t &G);
ferhat's avatar
ferhat committed
50
  //! Detect all the clique (all vertex in a clique are related to each other) in the graph
51
  bool Vertex_Belong_to_a_Clique(AdjacencyList_t::vertex_descriptor vertex, AdjacencyList_t &G);
ferhat's avatar
ferhat committed
52
  //! Graph reduction: eliminating purely intermediate variables or variables outside of any circuit
53
  bool Elimination_of_Vertex_With_One_or_Less_Indegree_or_Outdegree_Step(AdjacencyList_t &G);
54
  //! Graph reduction: elimination of a vertex inside a clique
55
  bool Elimination_of_Vertex_belonging_to_a_clique_Step(AdjacencyList_t &G);
56
  //! A vertex belong to the feedback vertex set if the vertex loops on itself.
57
  /*! We have to suppress this vertex and store it into the feedback set.*/
58
  bool Suppression_of_Vertex_X_if_it_loops_store_in_set_of_feedback_vertex_Step(set<int> &feed_back_vertices, AdjacencyList_t &G1);
ferhat's avatar
ferhat committed
59
  //! Print the Graph
60
  void Print(AdjacencyList_t &G);
ferhat's avatar
ferhat committed
61
  //! Create an adjacency graph from a Adjacency Matrix (an incidence Matrix without the diagonal terms)
62
  AdjacencyList_t AM_2_AdjacencyList(bool *AMp, unsigned int n);
63 64 65 66 67 68 69 70 71 72 73
  //! Extracts a subgraph
  /*!
    \param[in] G1 The original graph
    \param[in] select_index The vertex indices to select
    \return The subgraph

    The property vertex_index of the subgraph contains indices of the original
    graph, the property vertex_index1 contains new contiguous indices specific
    to the subgraph.
  */
  AdjacencyList_t extract_subgraph(AdjacencyList_t &G1, set<int> select_index);
ferhat's avatar
ferhat committed
74
  //! Check if the graph contains any cycle (true if the model contains at least one cycle, false otherwise)
75 76
  bool has_cycle(vector<int> &circuit_stack, AdjacencyList_t &g);
  bool has_cycle_dfs(AdjacencyList_t &g, AdjacencyList_t::vertex_descriptor u, color_t &color, vector<int> &circuit_stack);
ferhat's avatar
ferhat committed
77
  //! Return the feedback set
78
  AdjacencyList_t Minimal_set_of_feedback_vertex(set<int> &feed_back_vertices, const AdjacencyList_t &G);
79
  //! Clear all in and out edges of vertex_to_eliminate and remove vertex_to_eliminate from the graph
80 81
  void Suppress(AdjacencyList_t::vertex_descriptor vertex_to_eliminate, AdjacencyList_t &G);
  void Suppress(int vertex_num, AdjacencyList_t &G);
82 83
  //! Reorder the recursive variables
  /*! They appear first in a quasi triangular form and they are followed by the feedback variables */
84
  void Reorder_the_recursive_variables(const AdjacencyList_t &G1, set<int> &feedback_vertices, vector< int> &Reordered_Vertices);
85 86
};

87
#endif // _MINIMUMFEEDBACKSET_HH