PandA-2024.02
Public Member Functions | Private Member Functions | Private Attributes | Static Private Attributes
bipartite_matching_clique_covering< vertex_type > Class Template Reference

clique covering based on bipartite matching procedure More...

#include <clique_covering.hpp>

Inheritance diagram for bipartite_matching_clique_covering< vertex_type >:
Inheritance graph
[legend]
Collaboration diagram for bipartite_matching_clique_covering< vertex_type >:
Collaboration graph
[legend]

Public Member Functions

 bipartite_matching_clique_covering (unsigned int nvert)
 constructor More...
 
C_vertex add_vertex (const vertex_type &element, const std::string &name) override
 add a vertex More...
 
void add_edge (const vertex_type &src, const vertex_type &dest, int _weight) override
 add an edge More...
 
size_t num_vertices () override
 return the number of vertices of the clique More...
 
CustomOrderedSet< vertex_type > get_clique (unsigned int i) override
 Returns a clique. More...
 
void exec (const filter_clique< vertex_type > &fc, check_clique< vertex_type > &) override
 Abstract method that will execute clique covering algorithm. More...
 
void writeDot (const std::string &filename) const override
 Writes a dotty representation of the actual graph. More...
 
void add_subpartitions (size_t id, vertex_type v) override
 add subpartitions over which bipartite matching can start on More...
 
void suggest_min_resources (size_t n_resources) override
 suggest that the problem have at least a given number of resources More...
 
void min_resources (size_t n_resources) override
 specify the minimum number of resources More...
 
void suggest_max_resources (size_t) override
 suggest that the problem have at worst no more than the given number of resources More...
 
void max_resources (size_t n_resources) override
 specify the maximum number of resources More...
 
- Public Member Functions inherited from clique_covering< vertex_type >
 clique_covering ()=default
 Default constructor. More...
 
virtual ~clique_covering ()=default
 Destructor. More...
 

Private Member Functions

size_t color_the_cc_compatibility_graph (const boost_cc_compatibility_graph &CG)
 partition the set of vertex in set where each element is in conflict with the others the maximum size of these sets is the number of the cliques used to cover the graph More...
 

Private Attributes

boost_cc_compatibility_graph clique_covering_graph_bulk
 bulk undirected graph More...
 
std::vector< CustomUnorderedSet< C_vertex > > cliques
 set of maximal clique computed More...
 
CustomUnorderedMap< vertex_type, C_vertexv2uv
 map between vertex_type and C_vertex More...
 
CustomUnorderedMap< C_vertex, vertex_type > uv2v
 map between C_vertex and vertex_type More...
 
CustomUnorderedMap< C_vertex, std::string > names
 name map for the C_vertex vertices More...
 
int max_weight
 maximum weight More...
 
unsigned int vindex
 
size_t num_cols
 number of columns More...
 
size_t max_num_cols
 maximum number of columns More...
 
std::map< size_t, CustomOrderedSet< boost::graph_traits< boost_cc_compatibility_graph >::vertex_descriptor > > partitions
 

Static Private Attributes

static const int COMPATIBILITY_EDGE = 1
 edge selector More...
 
static const int COMPATIBILITY_ALL_EDGES = ~0
 

Additional Inherited Members

- Static Public Member Functions inherited from clique_covering< vertex_type >
static refcount< clique_covering< vertex_type > > create_solver (CliqueCovering_Algorithm solver, unsigned int nvert)
 Creates a reference to desired solver. More...
 

Detailed Description

template<typename vertex_type>
class bipartite_matching_clique_covering< vertex_type >

clique covering based on bipartite matching procedure

Definition at line 1520 of file clique_covering.hpp.

Constructor & Destructor Documentation

◆ bipartite_matching_clique_covering()

template<typename vertex_type >
bipartite_matching_clique_covering< vertex_type >::bipartite_matching_clique_covering ( unsigned int  nvert)
inline

constructor

Definition at line 1588 of file clique_covering.hpp.

Member Function Documentation

◆ add_edge()

template<typename vertex_type >
void bipartite_matching_clique_covering< vertex_type >::add_edge ( const vertex_type &  src,
const vertex_type &  dest,
int  _weight 
)
inlineoverridevirtual

add an edge

Implements clique_covering< vertex_type >.

Definition at line 1611 of file clique_covering.hpp.

References max, and THROW_ASSERT.

◆ add_subpartitions()

template<typename vertex_type >
void bipartite_matching_clique_covering< vertex_type >::add_subpartitions ( size_t  id,
vertex_type  v 
)
inlineoverridevirtual

add subpartitions over which bipartite matching can start on

Parameters
idis the subpartition id
vertexis the vertex of the given subpartition

Implements clique_covering< vertex_type >.

Definition at line 1855 of file clique_covering.hpp.

References max, and THROW_ASSERT.

◆ add_vertex()

template<typename vertex_type >
C_vertex bipartite_matching_clique_covering< vertex_type >::add_vertex ( const vertex_type &  element,
const std::string &  name 
)
inlineoverridevirtual

add a vertex

vertex weight not considered

Implements clique_covering< vertex_type >.

Definition at line 1598 of file clique_covering.hpp.

References result, and THROW_ASSERT.

◆ color_the_cc_compatibility_graph()

template<typename vertex_type >
size_t bipartite_matching_clique_covering< vertex_type >::color_the_cc_compatibility_graph ( const boost_cc_compatibility_graph CG)
inlineprivate

partition the set of vertex in set where each element is in conflict with the others the maximum size of these sets is the number of the cliques used to cover the graph

coloring based on DSATUR 2 heuristic

Definition at line 1547 of file clique_covering.hpp.

References boost::dsatur2_coloring(), and max.

Here is the call graph for this function:

◆ exec()

template<typename vertex_type >
void bipartite_matching_clique_covering< vertex_type >::exec ( const filter_clique< vertex_type > &  fc,
check_clique< vertex_type > &  cq 
)
inlineoverridevirtual

Abstract method that will execute clique covering algorithm.

If you want to specialize the implementation with your favorite algorithm, you have to implement this method.

Parameters
fcis the filtering clique functor used to reduce the proposed clique

now color the graph and then do the bipartite matching on the vertex having the same color usually this reduces the number of the partitions and simplifies the problem

initializes the cliques with empty sets

compute the assignment for each element of a partition

check if already assigned

already assigned to a clique

clean the results from empty cliques

Implements clique_covering< vertex_type >.

Definition at line 1642 of file clique_covering.hpp.

References filter_clique< vertex_type >::clique_cost(), filter_clique< vertex_type >::select_candidate_to_remove(), STR, and THROW_ASSERT.

Here is the call graph for this function:

◆ get_clique()

template<typename vertex_type >
CustomOrderedSet<vertex_type> bipartite_matching_clique_covering< vertex_type >::get_clique ( unsigned int  i)
inlineoverridevirtual

Returns a clique.

Parameters
iis the i-th clique into graph
Returns
set of elements into clique

Implements clique_covering< vertex_type >.

Definition at line 1629 of file clique_covering.hpp.

References result, and THROW_ASSERT.

◆ max_resources()

template<typename vertex_type >
void bipartite_matching_clique_covering< vertex_type >::max_resources ( size_t  n_resources)
inlineoverridevirtual

specify the maximum number of resources

Parameters
n_resourcesis the number of resources

Implements clique_covering< vertex_type >.

Definition at line 1877 of file clique_covering.hpp.

References max.

◆ min_resources()

template<typename vertex_type >
void bipartite_matching_clique_covering< vertex_type >::min_resources ( size_t  n_resources)
inlineoverridevirtual

specify the minimum number of resources

Parameters
n_resourcesis the number of resources

Implements clique_covering< vertex_type >.

Definition at line 1868 of file clique_covering.hpp.

References max.

◆ num_vertices()

template<typename vertex_type >
size_t bipartite_matching_clique_covering< vertex_type >::num_vertices ( )
inlineoverridevirtual

return the number of vertices of the clique

Implements clique_covering< vertex_type >.

Definition at line 1624 of file clique_covering.hpp.

◆ suggest_max_resources()

template<typename vertex_type >
void bipartite_matching_clique_covering< vertex_type >::suggest_max_resources ( size_t  n_resources)
inlineoverridevirtual

suggest that the problem have at worst no more than the given number of resources

Parameters
n_resourcesis the number of resources

Implements clique_covering< vertex_type >.

Definition at line 1873 of file clique_covering.hpp.

◆ suggest_min_resources()

template<typename vertex_type >
void bipartite_matching_clique_covering< vertex_type >::suggest_min_resources ( size_t  n_resources)
inlineoverridevirtual

suggest that the problem have at least a given number of resources

Parameters
n_resourcesis the number of resources available

Implements clique_covering< vertex_type >.

Definition at line 1863 of file clique_covering.hpp.

References max.

◆ writeDot()

template<typename vertex_type >
void bipartite_matching_clique_covering< vertex_type >::writeDot ( const std::string &  filename) const
inlineoverridevirtual

Writes a dotty representation of the actual graph.

Parameters
filenameis the output filename

Implements clique_covering< vertex_type >.

Definition at line 1848 of file clique_covering.hpp.

Field Documentation

◆ clique_covering_graph_bulk

template<typename vertex_type >
boost_cc_compatibility_graph bipartite_matching_clique_covering< vertex_type >::clique_covering_graph_bulk
private

bulk undirected graph

Definition at line 1524 of file clique_covering.hpp.

◆ cliques

template<typename vertex_type >
std::vector<CustomUnorderedSet<C_vertex> > bipartite_matching_clique_covering< vertex_type >::cliques
private

set of maximal clique computed

Definition at line 1526 of file clique_covering.hpp.

◆ COMPATIBILITY_ALL_EDGES

template<typename vertex_type >
const int bipartite_matching_clique_covering< vertex_type >::COMPATIBILITY_ALL_EDGES = ~0
staticprivate

Definition at line 1543 of file clique_covering.hpp.

◆ COMPATIBILITY_EDGE

template<typename vertex_type >
const int bipartite_matching_clique_covering< vertex_type >::COMPATIBILITY_EDGE = 1
staticprivate

edge selector

Definition at line 1542 of file clique_covering.hpp.

◆ max_num_cols

template<typename vertex_type >
size_t bipartite_matching_clique_covering< vertex_type >::max_num_cols
private

maximum number of columns

Definition at line 1539 of file clique_covering.hpp.

◆ max_weight

template<typename vertex_type >
int bipartite_matching_clique_covering< vertex_type >::max_weight
private

maximum weight

Definition at line 1534 of file clique_covering.hpp.

◆ names

template<typename vertex_type >
CustomUnorderedMap<C_vertex, std::string> bipartite_matching_clique_covering< vertex_type >::names
private

name map for the C_vertex vertices

Definition at line 1532 of file clique_covering.hpp.

◆ num_cols

template<typename vertex_type >
size_t bipartite_matching_clique_covering< vertex_type >::num_cols
private

number of columns

Definition at line 1537 of file clique_covering.hpp.

◆ partitions

template<typename vertex_type >
std::map<size_t, CustomOrderedSet<boost::graph_traits<boost_cc_compatibility_graph>::vertex_descriptor> > bipartite_matching_clique_covering< vertex_type >::partitions
private

Definition at line 1540 of file clique_covering.hpp.

◆ uv2v

template<typename vertex_type >
CustomUnorderedMap<C_vertex, vertex_type> bipartite_matching_clique_covering< vertex_type >::uv2v
private

map between C_vertex and vertex_type

Definition at line 1530 of file clique_covering.hpp.

◆ v2uv

template<typename vertex_type >
CustomUnorderedMap<vertex_type, C_vertex> bipartite_matching_clique_covering< vertex_type >::v2uv
private

map between vertex_type and C_vertex

Definition at line 1528 of file clique_covering.hpp.

◆ vindex

template<typename vertex_type >
unsigned int bipartite_matching_clique_covering< vertex_type >::vindex
private

Definition at line 1535 of file clique_covering.hpp.


The documentation for this class was generated from the following file:

Generated on Mon Feb 12 2024 13:03:45 for PandA-2024.02 by doxygen 1.8.13