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


.. _program_listing_file_pldl_netlist_algo.hpp:

Program Listing for File netlist_algo.hpp
=========================================

|exhale_lsh| :ref:`Return to documentation for file <file_pldl_netlist_algo.hpp>` (``pldl/netlist_algo.hpp``)

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

.. code-block:: cpp

   #include <algorithm>
   #include <memory>
   #include <pldl/netlist.hpp>
   #include <py2cpp/py2cpp.hpp>
   #include <range/v3/algorithm/any_of.hpp>
   #include <range/v3/algorithm/min_element.hpp>
   #include <tuple>
   #include <vector>
   
   using node_t = typename SimpleNetlist::node_t;
   
   namespace pldl {
   
   template <typename Netlist, typename C1, typename C2>
   auto min_vertex_cover(const Netlist &H, const C1 &weight, C2 &coverset) ->
       typename C1::mapped_type {
       using T = typename C1::mapped_type;
       auto in_coverset = [&](const auto &v) { return coverset.contains(v); };
       [[maybe_unused]] auto total_dual_cost = T(0);
       auto total_primal_cost = T(0);
       auto gap = weight;
       for (auto &&net : H.nets) {
           if (ranges::any_of(H.G[net], in_coverset)) {
               continue;
           }
   
           auto min_vtx =
               *ranges::min_element(H.G[net], [&](const auto &v1, const auto &v2) {
                   return gap[v1] < gap[v2];
               });
           auto min_val = gap[min_vtx];
           coverset.insert(min_vtx);
           total_primal_cost += weight[min_vtx];
           total_dual_cost += min_val;
           for (auto &&u : H.G[net]) {
               gap[u] -= min_val;
           }
       }
   
       assert(total_dual_cost <= total_primal_cost);
       return total_primal_cost;
   }
   
   template <typename Netlist, typename C1, typename C2>
   auto min_maximal_matching(const Netlist &H, const C1 &weight, C2 &&matchset,
                             C2 &&dep) -> typename C1::mapped_type {
       auto cover = [&](const auto &net) {
           for (auto &&v : H.G[net]) {
               dep.insert(v);
           }
       };
   
       auto in_dep = [&](const auto &v) { return dep.contains(v); };
   
       using T = typename C1::mapped_type;
   
       auto gap = weight;
       [[maybe_unused]] auto total_dual_cost = T(0);
       auto total_primal_cost = T(0);
       for (auto &&net : H.nets) {
           if (ranges::any_of(H.G[net], in_dep)) {
               continue;
           }
           if (matchset.contains(net)) { // pre-define independent
               cover(net);
               continue;
           }
           auto min_val = gap[net];
           auto min_net = net;
           for (auto &&v : H.G[net]) {
               for (auto &&net2 : H.G[v]) {
                   if (ranges::any_of(H.G[net2], in_dep)) {
                       continue;
                   }
                   if (min_val > gap[net2]) {
                       min_val = gap[net2];
                       min_net = net2;
                   }
               }
           }
           cover(min_net);
           matchset.insert(min_net);
           total_primal_cost += weight[min_net];
           total_dual_cost += min_val;
           if (min_net != net) {
               gap[net] -= min_val;
               for (auto &&v : H.G[net]) {
                   for (auto &&net2 : H.G[v]) {
                       gap[net2] -= min_val;
                   }
               }
           }
       }
       // assert(total_dual_cost <= total_primal_cost);
       return total_primal_cost;
   }
   
   } // namespace pldl