clique_covering.hpp File Reference

This header file includes four different algorithms heuristically solving the clique covering problem. More...

#include "clique_covering_graph.hpp"
#include "custom_map.hpp"
#include "custom_set.hpp"
#include "dsatur2_coloring.hpp"
#include "exceptions.hpp"
#include "ortools/graph/assignment.h"
#include "refcount.hpp"
#include "string_manipulation.hpp"
#include <algorithm>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/incremental_components.hpp>
#include <boost/graph/properties.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/version.hpp>
#include <cstddef>
#include <iterator>
#include <limits>
#include <ostream>
#include <string>
#include <utility>
#include <vector>

Include dependency graph for clique_covering.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	check_clique< vertex_type >
struct	filter_clique< vertex_type >
	Functor used to reduce the size of clique: the rationale of filtering is that too many sharing may create problem to the timing closure of the design. More...
class	clique_covering< VertexType >
class	compatibility_edge_writer
	Functor used by boost::write_graphviz to write the edge info. More...
class	compatibility_node_info_writer
	Functor used by boost::write_graphviz to write the node info. More...
class	TTT_maximal_weighted_clique< Graph >
	Class computing the maximal weighted clique from a generic graph. More...
class	TTT_maximal_weighted_clique_fast< Graph >
	fast version that just returns the first maximal clique found More...
class	coloring_based_clique_covering< vertex_type >
class	TTT_based_clique_covering_fast< vertex_type >
	second fast version of the TTT_based_clique_covering. More...
class	TTT_based_clique_covering< vertex_type >
class	TS_based_clique_covering< vertex_type >
class	RTS_based_clique_covering< vertex_type >
class	bipartite_matching_clique_covering< vertex_type >
	clique covering based on bipartite matching procedure More...

Macros
#define	THRESHOLD_2_SIMPLIFY   200
#define	MAX_EDGE_CONSIDERED   50

Enumerations
enum	CliqueCovering_Algorithm {   CliqueCovering_Algorithm::COLORING = 0, CliqueCovering_Algorithm::WEIGHTED_COLORING, CliqueCovering_Algorithm::TTT_CLIQUE_COVERING, CliqueCovering_Algorithm::TTT_CLIQUE_COVERING2,   CliqueCovering_Algorithm::TTT_CLIQUE_COVERING_FAST, CliqueCovering_Algorithm::TTT_CLIQUE_COVERING_FAST2, CliqueCovering_Algorithm::TS_CLIQUE_COVERING, CliqueCovering_Algorithm::TS_WEIGHTED_CLIQUE_COVERING,   CliqueCovering_Algorithm::BIPARTITE_MATCHING }
	Defines all clique covering algorithm. More...

Functions
template<typename IIter1 , typename Container , typename OIter >
OIter	unordered_set_difference (IIter1 first1, IIter1 last1, Container second, OIter result)
	unordered_set_difference More...
template<typename IIter1 , typename Container , typename OIter >
OIter	unordered_set_intersection (IIter1 first1, IIter1 last1, Container second, OIter result)
	unordered_set_intersection More...
const std::string	CliqueCovering_AlgorithmToString (const CliqueCovering_Algorithm clique_covering_algorithm)
	Return the name corresponding to an clique covering algorithm enum. More...

Detailed Description

This header file includes four different algorithms heuristically solving the clique covering problem.

This header has 4 classes solving clique covering problem. Three of them consider the weighted of the edges during the clique selection.

The first two heuristics are based on these two papers:

• E. Tomita, A. Tanaka, H. Takahashi "The worst-case time complexity for generating all maximal cliques and computational experiments", Theoretical Computer Science, Volume 363, Issue 1, 2006.
• K. C. Dukka Bahadur, Tatsuya Akutsu, Etsuji Tomita, and Tomokazu Seki. "Protein side-chain packing problem: a maximum edge-weight clique algorithmic approach", In Proceedings of the second conference on Asia-Pacific bioinformatics - Volume 29 (APBC '04), Yi-Ping Phoebe Chen (Ed.), Vol. 29. Australian Computer Society, Inc., Darlinghurst, Australia, Australia, 191-200. The third one is a simple clique covering obtained by coloring the complement graph. The last one performs iteratively the clique covering on a filtered graph induced by different edge weights.

Author

Fabrizio Ferrandi fabri.nosp@m.zio..nosp@m.ferra.nosp@m.ndi@.nosp@m.polim.nosp@m.i.it $Revision$ $Date$ Last modified by $Author$

Definition in file clique_covering.hpp.

Macro Definition Documentation

MAX_EDGE_CONSIDERED

#define MAX_EDGE_CONSIDERED   50

Definition at line 1252 of file clique_covering.hpp.

Referenced by TS_based_clique_covering< vertex_type >::select_edge(), and TS_based_clique_covering< vertex_type >::select_edge_start().

THRESHOLD_2_SIMPLIFY

#define THRESHOLD_2_SIMPLIFY   200

Definition at line 870 of file clique_covering.hpp.

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

Enumeration Type Documentation

CliqueCovering_Algorithm

enum CliqueCovering_Algorithm

strong

Defines all clique covering algorithm.

Enumerator
COLORING
WEIGHTED_COLORING
TTT_CLIQUE_COVERING
TTT_CLIQUE_COVERING2
TTT_CLIQUE_COVERING_FAST
TTT_CLIQUE_COVERING_FAST2
TS_CLIQUE_COVERING
TS_WEIGHTED_CLIQUE_COVERING
BIPARTITE_MATCHING

Definition at line 138 of file clique_covering.hpp.

Function Documentation

CliqueCovering_AlgorithmToString()

const std::string CliqueCovering_AlgorithmToString

(

const CliqueCovering_Algorithm

clique_covering_algorithm

)

Return the name corresponding to an clique covering algorithm enum.

Parameters

clique_covering_algorithm

is the clique covering algorithm

Returns

the name

Return the name corresponding to an clique covering algorithm enum.

Definition at line 41 of file clique_covering.cpp.

References BIPARTITE_MATCHING, COLORING, THROW_UNREACHABLE, TS_CLIQUE_COVERING, TS_WEIGHTED_CLIQUE_COVERING, TTT_CLIQUE_COVERING, TTT_CLIQUE_COVERING2, TTT_CLIQUE_COVERING_FAST, TTT_CLIQUE_COVERING_FAST2, and WEIGHTED_COLORING.

Referenced by WeightedCliqueRegisterBindingSpecialization::GetKindText(), and CDFCModuleBindingSpecialization::GetKindText().

Here is the caller graph for this function:

unordered_set_difference()

template<typename IIter1 , typename Container , typename OIter >

OIter unordered_set_difference	(	IIter1	first1,
		IIter1	last1,
		Container	second,
		OIter	result
	)

unordered_set_difference

Definition at line 107 of file clique_covering.hpp.

References result.

Referenced by TTT_maximal_weighted_clique< Graph >::expand(), and TTT_maximal_weighted_clique_fast< Graph >::expand().

Here is the caller graph for this function:

unordered_set_intersection()

template<typename IIter1 , typename Container , typename OIter >

OIter unordered_set_intersection	(	IIter1	first1,
		IIter1	last1,
		Container	second,
		OIter	result
	)

unordered_set_intersection

Definition at line 123 of file clique_covering.hpp.

References result.

Referenced by TTT_maximal_weighted_clique< Graph >::expand(), TTT_maximal_weighted_clique_fast< Graph >::expand(), TS_based_clique_covering< vertex_type >::select_edge(), and TS_based_clique_covering< vertex_type >::select_edge_start().

Here is the caller graph for this function: