Skip to content
Snippets Groups Projects
Select Git revision
  • e616667f7550db339d5e5d4f492f5fc3106f0ff5
  • master default protected
  • julia protected
  • 6.x protected
  • python-codegen
  • llvm-15
  • 5.x protected
  • 4.6 protected
  • uop
  • rework_pac
  • aux_vars_fix
  • julia-7.0.0
  • julia-6.4.0
  • julia-6.3.0
  • julia-6.2.0
15 results

MinimumFeedbackSet.cc

Blame
  • MinimumFeedbackSet.cc 17.37 KiB
    /*
     * Copyright (C) 2009 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"
    
    namespace MFS
    {
      void
      Suppress(AdjacencyList_type::vertex_descriptor vertex_to_eliminate, AdjacencyList_type &G)
      {
        clear_vertex(vertex_to_eliminate, G);
        remove_vertex(vertex_to_eliminate, G);
      }
    
      void
      Suppress(int vertex_num, AdjacencyList_type &G)
      {
        Suppress(vertex(vertex_num, G), G);
      }
    
      void
      Eliminate(AdjacencyList_type::vertex_descriptor vertex_to_eliminate, AdjacencyList_type &G)
      {
        if (in_degree(vertex_to_eliminate, G) > 0 && out_degree(vertex_to_eliminate, G) > 0)
          {
            AdjacencyList_type::in_edge_iterator it_in, in_end;
            AdjacencyList_type::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_type::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_type &g, AdjacencyList_type::vertex_descriptor u, color_type &color, vector<int> &circuit_stack)
      {
        property_map<AdjacencyList_type, vertex_index_t>::type v_index = get(vertex_index, g);
        color[u] = gray_color;
        graph_traits<AdjacencyList_type>::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
              circuit_stack.push_back(v_index[target(*vi, g)]);
              return true;