fast version that just returns the first maximal clique found More...

#include <clique_covering.hpp>

Collaboration diagram for TTT_maximal_weighted_clique_fast< Graph >:

[legend]

Public Member Functions
const CustomOrderedSet< vertex >	get_weighted_maximal_cliques (const Graph &g)
	return the weighted maximal clique of a graph g More...

	TTT_maximal_weighted_clique_fast (CustomUnorderedMap< typename boost::graph_traits< Graph >::vertex_descriptor, std::string > &_names)

Private Types
using	vertex_iterator = typename boost::graph_traits< Graph >::vertex_iterator
	vertex iterator More...

using	vertex = typename boost::graph_traits< Graph >::vertex_descriptor
	vertex object More...

using	adjacency_iterator = typename boost::graph_traits< Graph >::adjacency_iterator
	adjacency iterator More...

using	edge_iterator = typename boost::graph_traits< Graph >::out_edge_iterator
	out edge iterator More...

Private Member Functions
vertex	get_max_weighted_adiacent_intersection (const CustomUnorderedSet< vertex > &subg, const CustomUnorderedSet< vertex > &cand, const Graph &g)
	return the vertex of subg with the maximum intersection with cand More...

vertex	get_max_weight_vertex (CustomUnorderedSet< vertex > &ext, const Graph &g)
	return the vertex of ext having the maximum degree with respect to the graph g More...

int	compute_delta_weight (vertex q_vertex, CustomUnorderedSet< vertex > Q_set, const Graph &g)
	compute the delta of the weight by adding q_vertex to the clique More...

void	expand (CustomUnorderedSet< vertex > &subg, CustomUnorderedSet< vertex > &cand, const Graph &g)
	recursive procedure expand defined in first cited paper More...

Private Attributes
CustomUnorderedSet< vertex >	Q
	set of vertices of the current clique More...

CustomOrderedSet< vertex >	Q_max
	set of vertices of the maximum clique found so far More...

int	W_Q
	weight of Q More...

int	W_Q_max
	weight of Q_max More...

CustomUnorderedMap< C_vertex, std::string > &	names

Detailed Description

template<typename Graph>
class TTT_maximal_weighted_clique_fast< Graph >

fast version that just returns the first maximal clique found

Definition at line 495 of file clique_covering.hpp.

Member Typedef Documentation

◆ adjacency_iterator

template<typename Graph>

using TTT_maximal_weighted_clique_fast< Graph >::adjacency_iterator = typename boost::graph_traits<Graph>::adjacency_iterator

private

adjacency iterator

Definition at line 502 of file clique_covering.hpp.

◆ edge_iterator

template<typename Graph>

using TTT_maximal_weighted_clique_fast< Graph >::edge_iterator = typename boost::graph_traits<Graph>::out_edge_iterator

private

out edge iterator

Definition at line 504 of file clique_covering.hpp.

◆ vertex

template<typename Graph>

using TTT_maximal_weighted_clique_fast< Graph >::vertex = typename boost::graph_traits<Graph>::vertex_descriptor

private

vertex object

Definition at line 500 of file clique_covering.hpp.

◆ vertex_iterator

template<typename Graph>

using TTT_maximal_weighted_clique_fast< Graph >::vertex_iterator = typename boost::graph_traits<Graph>::vertex_iterator

private

vertex iterator

Definition at line 498 of file clique_covering.hpp.

Constructor & Destructor Documentation

◆ TTT_maximal_weighted_clique_fast()

template<typename Graph>

TTT_maximal_weighted_clique_fast< Graph >::TTT_maximal_weighted_clique_fast ( CustomUnorderedMap< typename boost::graph_traits< Graph >::vertex_descriptor, std::string > & _names )

inlineexplicit

Definition at line 670 of file clique_covering.hpp.

Member Function Documentation

◆ compute_delta_weight()

template<typename Graph>

int TTT_maximal_weighted_clique_fast< Graph >::compute_delta_weight	(	vertex	q_vertex,
		CustomUnorderedSet< vertex >	Q_set,
		const Graph &	g
	)

inlineprivate

compute the delta of the weight by adding q_vertex to the clique

Definition at line 574 of file clique_covering.hpp.

References result, and lenet_tvm::target.

◆ expand()

template<typename Graph>

void TTT_maximal_weighted_clique_fast< Graph >::expand	(	CustomUnorderedSet< vertex > &	subg,
		CustomUnorderedSet< vertex > &	cand,
		const Graph &	g
	)

inlineprivate

recursive procedure expand defined in first cited paper

get the vertex in subg with the maximum of adjacent vertices in cand

get adjacent vertices of u

set of vertices adjacent to u

compute EXT_u = CAND - gamma_u

compute delta_weight

Definition at line 590 of file clique_covering.hpp.

References unordered_set_difference(), and unordered_set_intersection().

Here is the call graph for this function:

◆ get_max_weight_vertex()

template<typename Graph>

vertex TTT_maximal_weighted_clique_fast< Graph >::get_max_weight_vertex	(	CustomUnorderedSet< vertex > &	ext,
		const Graph &	g
	)

inlineprivate

return the vertex of ext having the maximum degree with respect to the graph g

Definition at line 548 of file clique_covering.hpp.

References result, and THROW_ASSERT.

◆ get_max_weighted_adiacent_intersection()

template<typename Graph>

vertex TTT_maximal_weighted_clique_fast< Graph >::get_max_weighted_adiacent_intersection	(	const CustomUnorderedSet< vertex > &	subg,
		const CustomUnorderedSet< vertex > &	cand,
		const Graph &	g
	)

inlineprivate

return the vertex of subg with the maximum intersection with cand

Definition at line 518 of file clique_covering.hpp.

References result, lenet_tvm::target, and THROW_ASSERT.

◆ get_weighted_maximal_cliques()

template<typename Graph>

const CustomOrderedSet<vertex> TTT_maximal_weighted_clique_fast< Graph >::get_weighted_maximal_cliques ( const Graph & g )

inline

return the weighted maximal clique of a graph g

Definition at line 654 of file clique_covering.hpp.

References min.

Referenced by TTT_based_clique_covering_fast< vertex_type >::do_clique_covering().

Here is the caller graph for this function:

Field Documentation

◆ names

template<typename Graph>

CustomUnorderedMap<C_vertex, std::string>& TTT_maximal_weighted_clique_fast< Graph >::names

private

Definition at line 515 of file clique_covering.hpp.

◆ Q

template<typename Graph>

CustomUnorderedSet<vertex> TTT_maximal_weighted_clique_fast< Graph >::Q

private

set of vertices of the current clique

Definition at line 507 of file clique_covering.hpp.

◆ Q_max

template<typename Graph>

CustomOrderedSet<vertex> TTT_maximal_weighted_clique_fast< Graph >::Q_max

private

set of vertices of the maximum clique found so far

Definition at line 509 of file clique_covering.hpp.

◆ W_Q

template<typename Graph>

int TTT_maximal_weighted_clique_fast< Graph >::W_Q

private

weight of Q

Definition at line 511 of file clique_covering.hpp.

◆ W_Q_max

template<typename Graph>

int TTT_maximal_weighted_clique_fast< Graph >::W_Q_max

private

weight of Q_max

Definition at line 513 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 Types

Private Member Functions

Private Attributes

Detailed Description

template<typename Graph> class TTT_maximal_weighted_clique_fast< Graph >

Member Typedef Documentation

◆ adjacency_iterator

◆ edge_iterator

◆ vertex

◆ vertex_iterator

Constructor & Destructor Documentation

◆ TTT_maximal_weighted_clique_fast()

Member Function Documentation

◆ compute_delta_weight()

◆ expand()

◆ get_max_weight_vertex()

◆ get_max_weighted_adiacent_intersection()

◆ get_weighted_maximal_cliques()

Field Documentation

◆ names

◆ Q

◆ Q_max

◆ W_Q

◆ W_Q_max

template<typename Graph>
class TTT_maximal_weighted_clique_fast< Graph >