MinimumFeedbackSet.cc

/*
 * Copyright © 2009-2017 Dynare Team
 *
 * 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/>.
 */

#include <iostream>

#include "MinimumFeedbackSet.hh"

using namespace boost;

namespace MFS
{
  void
  Suppress(AdjacencyList_t::vertex_descriptor vertex_to_eliminate, AdjacencyList_t &G)
  {
    clear_vertex(vertex_to_eliminate, G);
    remove_vertex(vertex_to_eliminate, G);
  }

  void
  Suppress(int vertex_num, AdjacencyList_t &G)
  {
    Suppress(vertex(vertex_num, G), G);
  }

  void
  Eliminate(AdjacencyList_t::vertex_descriptor vertex_to_eliminate, AdjacencyList_t &G)
  {
    if (in_degree(vertex_to_eliminate, G) > 0 && out_degree(vertex_to_eliminate, G) > 0)
      {
        AdjacencyList_t::in_edge_iterator it_in, in_end;
        AdjacencyList_t::out_edge_iterator it_out, out_end;
        for (tie(it_in, in_end) = in_edges(vertex_to_eliminate, G); it_in != in_end; ++it_in)
          for (tie(it_out, out_end) = out_edges(vertex_to_eliminate, G); it_out != out_end; ++it_out)
            {
              AdjacencyList_t::edge_descriptor ed;
              bool exist;
              tie(ed, exist) = edge(source(*it_in, G), target(*it_out, G), G);
              if (!exist)
                add_edge(source(*it_in, G), target(*it_out, G), G);
            }
      }
    Suppress(vertex_to_eliminate, G);
  }

  bool
  has_cycle_dfs(AdjacencyList_t &g, AdjacencyList_t::vertex_descriptor u, color_t &color, vector<int> &circuit_stack)
  {
    property_map<AdjacencyList_t, vertex_index_t>::type v_index = get(vertex_index, g);
    color[u] = gray_color;
    graph_traits<AdjacencyList_t>::out_edge_iterator vi, vi_end;
    for (tie(vi, vi_end) = out_edges(u, g); vi != vi_end; ++vi)
      if (color[target(*vi, g)] == white_color && has_cycle_dfs(g, target(*vi, g), color, circuit_stack))
        {
          // cycle detected, return immediately