:github_url: https://github.com/svenevs/exhale-companion


.. _program_listing_file_netoptim_neg_cycle.hpp:

Program Listing for File neg_cycle.hpp
======================================

|exhale_lsh| :ref:`Return to documentation for file <file_netoptim_neg_cycle.hpp>` (``netoptim/neg_cycle.hpp``)

.. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS

.. code-block:: cpp

   // -*- coding: utf-8 -*-
   #pragma once
   
   #include <cassert>
   #include <py2cpp/py2cpp.hpp>
   #include <vector>
   
   template <typename Graph> //
   class negCycleFinder
   {
       using node_t = typename Graph::node_t;
       using edge_t = typename Graph::edge_t;
   
       py::dict<node_t, node_t> _pred {};
       py::dict<node_t, edge_t> _edge {};
   
     private:
       const Graph& _G; // const???
   
     public:
       explicit negCycleFinder(const Graph& G)
           : _G {G}
       {
       }
   
   
       template <typename Container, typename WeightFn>
       auto find_neg_cycle(Container&& dist, WeightFn&& get_weight)
           -> std::vector<edge_t>
       {
           this->_pred.clear();
           this->_edge.clear();
   
           while (this->_relax(dist, get_weight))
           {
               const auto v = this->_find_cycle();
               if (v != this->_G.null_vertex())
               {
                   assert(this->_is_negative(v, dist, get_weight));
                   return this->_cycle_list(v);
               }
           }
           return std::vector<edge_t> {}; // ???
       }
   
     private:
       auto _find_cycle() -> node_t
       {
           auto visited = py::dict<node_t, node_t> {};
   
           for (auto&& v : this->_G)
           {
               if (visited.contains(v))
               {
                   continue;
               }
               auto u = v;
               while (true)
               {
                   visited[u] = v;
                   if (!this->_pred.contains(u))
                   {
                       break;
                   }
                   u = this->_pred[u];
                   if (visited.contains(u))
                   {
                       if (visited[u] == v)
                       {
                           // if (this->_is_negative(u)) {
                           // should be "yield u";
                           return u;
                           // }
                       }
                       break;
                   }
               }
           }
   
           return this->_G.null_vertex();
       }
   
       template <typename Container, typename WeightFn>
       auto _relax(Container&& dist, WeightFn&& get_weight) -> bool
       {
           auto changed = false;
           for (auto&& e : this->_G.edges())
           {
               const auto vs = this->_G.end_points(e);
               const auto& u = vs.first;
               const auto& v = vs.second;
               const auto wt = get_weight(e);
               const auto d = dist[u] + wt;
   
               if (dist[v] > d)
               {
                   this->_pred[v] = u;
                   this->_edge[v] = e; // ???
                   dist[v] = d;
                   changed = true;
               }
           }
           return changed;
       }
   
       auto _cycle_list(const node_t& handle) -> std::vector<edge_t>
       {
           auto v = handle;
           auto cycle = std::vector<edge_t> {}; // ???
           do
           {
               const auto& u = this->_pred[v];
               cycle.push_back(this->_edge[v]); // ???
               v = u;
           } while (v != handle);
           return cycle;
       }
   
       template <typename Container, typename WeightFn>
       auto _is_negative(const node_t& handle, const Container& dist,
           WeightFn&& get_weight) -> bool
       {
           auto v = handle;
           do
           {
               const auto u = this->_pred[v];
               const auto e = this->_edge[v];
               const auto wt = get_weight(e); // ???
               if (dist[v] > dist[u] + wt)
               {
                   return true;
               }
               v = u;
           } while (v != handle);
   
           return false;
       }
   };