PandA-2024.02
|
clique covering based on bipartite matching procedure More...
#include <clique_covering.hpp>
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_vertex > | v2uv |
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... | |
clique covering based on bipartite matching procedure
Definition at line 1520 of file clique_covering.hpp.
|
inline |
constructor
Definition at line 1588 of file clique_covering.hpp.
|
inlineoverridevirtual |
add an edge
Implements clique_covering< vertex_type >.
Definition at line 1611 of file clique_covering.hpp.
References max, and THROW_ASSERT.
|
inlineoverridevirtual |
add subpartitions over which bipartite matching can start on
id | is the subpartition id |
vertex | is 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.
|
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.
|
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.
|
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.
fc | is 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.
|
inlineoverridevirtual |
Returns a clique.
i | is the i-th clique into graph |
Implements clique_covering< vertex_type >.
Definition at line 1629 of file clique_covering.hpp.
References result, and THROW_ASSERT.
|
inlineoverridevirtual |
specify the maximum number of resources
n_resources | is the number of resources |
Implements clique_covering< vertex_type >.
Definition at line 1877 of file clique_covering.hpp.
References max.
|
inlineoverridevirtual |
specify the minimum number of resources
n_resources | is the number of resources |
Implements clique_covering< vertex_type >.
Definition at line 1868 of file clique_covering.hpp.
References max.
|
inlineoverridevirtual |
return the number of vertices of the clique
Implements clique_covering< vertex_type >.
Definition at line 1624 of file clique_covering.hpp.
|
inlineoverridevirtual |
suggest that the problem have at worst no more than the given number of resources
n_resources | is the number of resources |
Implements clique_covering< vertex_type >.
Definition at line 1873 of file clique_covering.hpp.
|
inlineoverridevirtual |
suggest that the problem have at least a given number of resources
n_resources | is the number of resources available |
Implements clique_covering< vertex_type >.
Definition at line 1863 of file clique_covering.hpp.
References max.
|
inlineoverridevirtual |
Writes a dotty representation of the actual graph.
filename | is the output filename |
Implements clique_covering< vertex_type >.
Definition at line 1848 of file clique_covering.hpp.
|
private |
bulk undirected graph
Definition at line 1524 of file clique_covering.hpp.
|
private |
set of maximal clique computed
Definition at line 1526 of file clique_covering.hpp.
|
staticprivate |
Definition at line 1543 of file clique_covering.hpp.
|
staticprivate |
edge selector
Definition at line 1542 of file clique_covering.hpp.
|
private |
maximum number of columns
Definition at line 1539 of file clique_covering.hpp.
|
private |
maximum weight
Definition at line 1534 of file clique_covering.hpp.
|
private |
name map for the C_vertex vertices
Definition at line 1532 of file clique_covering.hpp.
|
private |
number of columns
Definition at line 1537 of file clique_covering.hpp.
|
private |
Definition at line 1540 of file clique_covering.hpp.
|
private |
map between C_vertex and vertex_type
Definition at line 1530 of file clique_covering.hpp.
|
private |
map between vertex_type and C_vertex
Definition at line 1528 of file clique_covering.hpp.
|
private |
Definition at line 1535 of file clique_covering.hpp.