netlist_algo.hpp file
Functions
-
template<typename Gnl, typename C1, typename C2>auto min_vertex_cover(const Gnl& hyprgraph, const C1& weight, C2& coverset) -> typename C1::mapped_type -> auto
- Solves the minimum weighted vertex cover problem using the primal-dual paradigm.
-
template<typename Gnl, typename C1, typename C2>auto min_maximal_matching(const Gnl& hyprgraph, const C1& weight, C2& matchset, C2& dep) -> typename C1::mapped_type -> auto
- Solves the minimum weighted maximal matching problem using the primal-dual paradigm.
Function documentation
template<typename Gnl, typename C1, typename C2>
auto min_vertex_cover(const Gnl& hyprgraph,
const C1& weight,
C2& coverset) -> typename C1::mapped_type
Solves the minimum weighted vertex cover problem using the primal-dual paradigm.
| Template parameters | |
|---|---|
| Gnl | The type of the hypergraph. |
| C1 | The type of the weight function. |
| C2 | The type of the cover set. |
| Parameters | |
| hyprgraph | The input hypergraph. |
| weight | The weight function. |
| coverset in/out | The set of pre-covered vertices, which will be updated with the solution set. |
| Returns | The total primal cost of the minimum weighted vertex cover. |
This function takes a hypergraph, a weight function, and a set of pre-covered vertices. It computes the minimum weighted vertex cover by iterating over the hypergraph's nets and selecting the vertex with the minimum weight gap to add to the cover set. The total primal and dual costs are computed and returned.
template<typename Gnl, typename C1, typename C2>
auto min_maximal_matching(const Gnl& hyprgraph,
const C1& weight,
C2& matchset,
C2& dep) -> typename C1::mapped_type
Solves the minimum weighted maximal matching problem using the primal-dual paradigm.
| Template parameters | |
|---|---|
| Gnl | The type of the hypergraph. |
| C1 | The type of the weight function. |
| C2 | The type of the matching set and dependency set. |
| Parameters | |
| hyprgraph | The input hypergraph. |
| weight | The weight function. |
| matchset in/out | The output matching set. |
| dep in/out | The output dependency set. |
| Returns | The total primal cost of the minimum weighted maximal matching. |
This function takes a hypergraph, a weight function, and two output parameters: a matching set and a dependency set. It computes the minimum weighted maximal matching by iterating over the hypergraph's nets and greedily selecting the minimum-weight net that does not conflict with the current dependency set. The total primal cost of the minimum weighted maximal matching is returned.