Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
T_Maximum_clique_finder< GraphType > Class Template Reference

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< GraphGraph_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
GraphModel 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