Class computing the maximal weighted clique from a generic graph. More...

#include <clique_covering.hpp>

Collaboration diagram for TTT_maximal_weighted_clique< Graph >:

[legend]

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

int	get_last_W_Q_max ()
	return the last weight of the maximum clique More...

	TTT_maximal_weighted_clique (CustomUnorderedMap< C_vertex, 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 edge weight 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, int upper_bound)
	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< Graph >

Class computing the maximal weighted clique from a generic graph.

Definition at line 307 of file clique_covering.hpp.

Member Typedef Documentation

◆ adjacency_iterator

template<typename Graph>

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

private

adjacency iterator

Definition at line 314 of file clique_covering.hpp.

◆ edge_iterator

template<typename Graph>

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

private

out edge iterator

Definition at line 316 of file clique_covering.hpp.

◆ vertex

template<typename Graph>

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

private

vertex object

Definition at line 312 of file clique_covering.hpp.

◆ vertex_iterator

template<typename Graph>

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

private

vertex iterator

Definition at line 310 of file clique_covering.hpp.

Constructor & Destructor Documentation

◆ TTT_maximal_weighted_clique()

template<typename Graph>

TTT_maximal_weighted_clique< Graph >::TTT_maximal_weighted_clique ( CustomUnorderedMap< C_vertex, std::string > & _names )

inlineexplicit

Definition at line 485 of file clique_covering.hpp.

Member Function Documentation

◆ compute_delta_weight()

template<typename Graph>

int TTT_maximal_weighted_clique< 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 386 of file clique_covering.hpp.

References result, and lenet_tvm::target.

◆ expand()

template<typename Graph>

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

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 402 of file clique_covering.hpp.

References unordered_set_difference(), and unordered_set_intersection().

Here is the call graph for this function:

◆ get_last_W_Q_max()

template<typename Graph>

int TTT_maximal_weighted_clique< Graph >::get_last_W_Q_max ( )

inline

return the last weight of the maximum clique

Definition at line 481 of file clique_covering.hpp.

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

Here is the caller graph for this function:

◆ get_max_weight_vertex()

template<typename Graph>

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

inlineprivate

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

Definition at line 360 of file clique_covering.hpp.

References result, and THROW_ASSERT.

◆ get_max_weighted_adiacent_intersection()

template<typename Graph>

vertex TTT_maximal_weighted_clique< 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 330 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< Graph >::get_weighted_maximal_cliques	(	const Graph &	g,
		int	upper_bound
	)

inline

return the weighted maximal clique of a graph g

Definition at line 464 of file clique_covering.hpp.

References min.

Referenced by TTT_based_clique_covering< 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< Graph >::names

private

Definition at line 327 of file clique_covering.hpp.

◆ Q

template<typename Graph>

CustomUnorderedSet<vertex> TTT_maximal_weighted_clique< Graph >::Q

private

set of vertices of the current clique

Definition at line 319 of file clique_covering.hpp.

◆ Q_max

template<typename Graph>

CustomOrderedSet<vertex> TTT_maximal_weighted_clique< Graph >::Q_max

private

set of vertices of the maximum clique found so far

Definition at line 321 of file clique_covering.hpp.

◆ W_Q

template<typename Graph>

int TTT_maximal_weighted_clique< Graph >::W_Q

private

weight of Q

Definition at line 323 of file clique_covering.hpp.

◆ W_Q_max

template<typename Graph>

int TTT_maximal_weighted_clique< Graph >::W_Q_max

private

weight of Q_max

Definition at line 325 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< Graph >

Member Typedef Documentation

◆ adjacency_iterator

◆ edge_iterator

◆ vertex

◆ vertex_iterator

Constructor & Destructor Documentation

◆ TTT_maximal_weighted_clique()

Member Function Documentation

◆ compute_delta_weight()

◆ expand()

◆ get_last_W_Q_max()

◆ 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< Graph >