Functor returning the vertices of a maximum clique of an input graph. More...

#include <Maximum_clique_finder.hpp>

Public Types
typedef T_Maximum_clique_finder< GraphType >	Self

typedef GraphType	Graph

typedef boost::graph_traits< Graph >	Graph_traits

typedef Graph_traits::vertex_descriptor	Vertex

Public Member Functions
template<class OutputIterator >
OutputIterator	operator() (const Graph &G, OutputIterator out)

Detailed Description

template<class GraphType>
class SBL::CADS::T_Maximum_clique_finder< GraphType >

Functor returning the vertices of a maximum clique of an input graph.

Given a boost graph, will find a maximum cardinality clique using P.R.J Ostergard algorithm.

Vertex colours are approximated using sequential vertex colouring
Time limit is not implemented

It is inspired from "A fast algorithm for the maximum clique problem", P. R. J. Östergård, Discrete Applied Mathematics 120 (2002), 197-207. The only difference is that here the number of colours in the neighbourhood of a vertex is crudely approximated.

Template Parameters

Graph Model of an undirected boost graph with vector for storing the vertices and the edges.

Member Typedef Documentation

◆ Graph

typedef GraphType Graph

◆ Graph_traits

typedef boost::graph_traits<Graph> Graph_traits

◆ Self

typedef T_Maximum_clique_finder<GraphType> Self

◆ Vertex

typedef Graph_traits::vertex_descriptor Vertex

Member Function Documentation

◆ operator()()

OutputIterator operator()	(	const Graph &	G,
		OutputIterator	out
	)

inline

Public Types

Public Member Functions