#include <clique_covering.hpp>

Inheritance diagram for coloring_based_clique_covering< vertex_type >:

[legend]

Collaboration diagram for coloring_based_clique_covering< vertex_type >:

Public Member Functions
	coloring_based_clique_covering (bool _all_edges, unsigned int nvert)
	constructor More...

	~coloring_based_clique_covering () override=default
	destructor 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...

virtual void	do_clique_covering (const cc_compatibility_graphRef filteredCG, boost::disjoint_sets< rank_pmap_type, pred_pmap_type > &ds, CustomUnorderedSet< C_vertex > &, const CustomUnorderedSet< C_vertex > &, const filter_clique< vertex_type > &)

void	build_partitions (CustomUnorderedSet< C_vertex > &support, boost::disjoint_sets< rank_pmap_type, pred_pmap_type > &ds, std::map< C_vertex, CustomOrderedSet< C_vertex >> &current_partitions)
	build partitions 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, vertex_type) override
	add subpartitions over which bipartite matching can start on More...

void	suggest_min_resources (size_t) override
	suggest that the problem have at least a given 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	min_resources (size_t) override
	specify the minimum number of resources More...

void	max_resources (size_t) 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...

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

Private Attributes
boost_cc_compatibility_graph	clique_covering_graph_bulk
	bulk undirected graph More...

std::vector< CustomOrderedSet< C_vertex > >	cliques
	set of maximal clique computed More...

CustomUnorderedMap< vertex_type, C_vertex >	v2uv
	map between vertex_type and C_vertex More...

int	max_level

bool	all_edges

unsigned	vindex

Static Private Attributes
static const int	COMPATIBILITY_ALL_EDGES = ~0
	edge selector to select all edges of the compatibility graph More...

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 coloring_based_clique_covering< vertex_type >

Definition at line 678 of file clique_covering.hpp.

Constructor & Destructor Documentation

◆ coloring_based_clique_covering()

template<typename vertex_type >

coloring_based_clique_covering< vertex_type >::coloring_based_clique_covering	(	bool	_all_edges,
		unsigned int	nvert
	)

inlineexplicit

constructor

Definition at line 700 of file clique_covering.hpp.

◆ ~coloring_based_clique_covering()

template<typename vertex_type >

coloring_based_clique_covering< vertex_type >::~coloring_based_clique_covering ( )

overridedefault

destructor

Member Function Documentation

◆ add_edge()

template<typename vertex_type >

void coloring_based_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 722 of file clique_covering.hpp.

References max, STR, and THROW_ASSERT.

◆ add_subpartitions()

template<typename vertex_type >

void coloring_based_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 1022 of file clique_covering.hpp.

◆ add_vertex()

template<typename vertex_type >

C_vertex coloring_based_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 709 of file clique_covering.hpp.

References result, and THROW_ASSERT.

◆ build_partitions()

template<typename vertex_type >

void coloring_based_clique_covering< vertex_type >::build_partitions	(	CustomUnorderedSet< C_vertex > &	support,
		boost::disjoint_sets< rank_pmap_type, pred_pmap_type > &	ds,
		std::map< C_vertex, CustomOrderedSet< C_vertex >> &	current_partitions
	)

inline

build partitions

Definition at line 836 of file clique_covering.hpp.

◆ do_clique_covering()

template<typename vertex_type >

virtual void coloring_based_clique_covering< vertex_type >::do_clique_covering	(	const cc_compatibility_graphRef	filteredCG,
		boost::disjoint_sets< rank_pmap_type, pred_pmap_type > &	ds,
		CustomUnorderedSet< C_vertex > &	,
		const CustomUnorderedSet< C_vertex > &	,
		const filter_clique< vertex_type > &
	)

inlinevirtual

conflict graph

the graph is an undirected graph...

coloring based on DSATUR 2 heuristic

Reimplemented in TS_based_clique_covering< vertex_type >, TTT_based_clique_covering< vertex_type >, and TTT_based_clique_covering_fast< vertex_type >.

Definition at line 753 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 coloring_based_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

color the conflict graph projection

build the current partitions

remove non conformant edges

remove edges given the current set of clique

restart the pruning

and then restart the whole partition analysis

recompute the support by keeping only the representative of each partition

rebuild the graph starting from which the coloring has performed

rebuild the partitions

and then fill the cliques

Implements clique_covering< vertex_type >.

Definition at line 871 of file clique_covering.hpp.

References test_panda::restart, lenet_tvm::target, and THRESHOLD_2_SIMPLIFY.

Referenced by RTS_based_clique_covering< vertex_type >::exec().

Here is the caller graph for this function:

◆ get_clique()

template<typename vertex_type >

CustomOrderedSet<vertex_type> coloring_based_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 740 of file clique_covering.hpp.

References result, and THROW_ASSERT.

◆ max_resources()

template<typename vertex_type >

void coloring_based_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 1038 of file clique_covering.hpp.

◆ min_resources()

template<typename vertex_type >

void coloring_based_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 1034 of file clique_covering.hpp.

◆ num_vertices()

template<typename vertex_type >

size_t coloring_based_clique_covering< vertex_type >::num_vertices ( )

inlineoverridevirtual

return the number of vertices of the clique

Implements clique_covering< vertex_type >.

Definition at line 735 of file clique_covering.hpp.

◆ suggest_max_resources()

template<typename vertex_type >

void coloring_based_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 1030 of file clique_covering.hpp.

◆ suggest_min_resources()

template<typename vertex_type >

void coloring_based_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 1026 of file clique_covering.hpp.

◆ writeDot()

template<typename vertex_type >

void coloring_based_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 1015 of file clique_covering.hpp.

Field Documentation

◆ all_edges

template<typename vertex_type >

bool coloring_based_clique_covering< vertex_type >::all_edges

private

Definition at line 689 of file clique_covering.hpp.

◆ clique_covering_graph_bulk

template<typename vertex_type >

boost_cc_compatibility_graph coloring_based_clique_covering< vertex_type >::clique_covering_graph_bulk

private

bulk undirected graph

Definition at line 681 of file clique_covering.hpp.

◆ cliques

template<typename vertex_type >

std::vector<CustomOrderedSet<C_vertex> > coloring_based_clique_covering< vertex_type >::cliques

private

set of maximal clique computed

Definition at line 683 of file clique_covering.hpp.

◆ COMPATIBILITY_ALL_EDGES

template<typename vertex_type >

const int coloring_based_clique_covering< vertex_type >::COMPATIBILITY_ALL_EDGES = ~0

staticprivate

edge selector to select all edges of the compatibility graph

Definition at line 687 of file clique_covering.hpp.

◆ max_level

template<typename vertex_type >

int coloring_based_clique_covering< vertex_type >::max_level

private

Definition at line 688 of file clique_covering.hpp.

◆ names

template<typename vertex_type >

CustomUnorderedMap<C_vertex, std::string> coloring_based_clique_covering< vertex_type >::names

protected

name map for the C_vertex vertices

Definition at line 696 of file clique_covering.hpp.

◆ uv2v

template<typename vertex_type >

CustomUnorderedMap<C_vertex, vertex_type> coloring_based_clique_covering< vertex_type >::uv2v

protected

map between C_vertex and vertex_type

Definition at line 694 of file clique_covering.hpp.

◆ v2uv

template<typename vertex_type >

CustomUnorderedMap<vertex_type, C_vertex> coloring_based_clique_covering< vertex_type >::v2uv

private

map between vertex_type and C_vertex

Definition at line 685 of file clique_covering.hpp.

◆ vindex

template<typename vertex_type >

unsigned coloring_based_clique_covering< vertex_type >::vindex

private

Definition at line 690 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

Protected Attributes

Private Attributes

Static Private Attributes

Additional Inherited Members

Detailed Description

template<typename vertex_type> class coloring_based_clique_covering< vertex_type >

Constructor & Destructor Documentation

◆ coloring_based_clique_covering()

◆ ~coloring_based_clique_covering()

Member Function Documentation

◆ add_edge()

◆ add_subpartitions()

◆ add_vertex()

◆ build_partitions()

◆ do_clique_covering()

◆ exec()

◆ get_clique()

◆ max_resources()

◆ min_resources()

◆ num_vertices()

◆ suggest_max_resources()

◆ suggest_min_resources()

◆ writeDot()

Field Documentation

◆ all_edges

◆ clique_covering_graph_bulk

◆ cliques

◆ COMPATIBILITY_ALL_EDGES

◆ max_level

◆ names

◆ uv2v

◆ v2uv

◆ vindex

template<typename vertex_type>
class coloring_based_clique_covering< vertex_type >