clique covering based on bipartite matching procedure More...

#include <clique_covering.hpp>

Inheritance diagram for bipartite_matching_clique_covering< vertex_type >:

Collaboration diagram for bipartite_matching_clique_covering< vertex_type >:

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...

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

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.

◆ 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

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.

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

i	is 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_resources is 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_resources is 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_resources is 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_resources is 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

filename is 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:

/workspace/src/algorithms/clique_covering/clique_covering.hpp

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Additional Inherited Members

Detailed Description

template<typename vertex_type> class bipartite_matching_clique_covering< vertex_type >

Constructor & Destructor Documentation

◆ bipartite_matching_clique_covering()

Member Function Documentation

◆ add_edge()

◆ add_subpartitions()

◆ add_vertex()

◆ color_the_cc_compatibility_graph()

◆ exec()

◆ get_clique()

◆ max_resources()

◆ min_resources()

◆ num_vertices()

◆ suggest_max_resources()

◆ suggest_min_resources()

◆ writeDot()

Field Documentation

◆ clique_covering_graph_bulk

◆ cliques

◆ COMPATIBILITY_ALL_EDGES

◆ COMPATIBILITY_EDGE

◆ max_num_cols

◆ max_weight

◆ names

◆ num_cols

◆ partitions

◆ uv2v

◆ v2uv

◆ vindex

template<typename vertex_type>
class bipartite_matching_clique_covering< vertex_type >