limbo::algorithms Namespace Reference

namespace for Limbo.algorithms More...

Namespaces
	coloring
	namespace for Limbo.Algorithms.Coloring
	partition
	namespace for Limbo.Algorithms.Partition
	placement
	namespace for Limbo.Algorithms.Placement

Classes
struct	EdgeLabelWriter
	default EdgeLabelWriter for write_graph More...
struct	max_clique_visitor_type
	callback for boost::bron_kerbosch_all_cliques More...
class	MaxIndependentSetByMaxClique
struct	VertexLabelWriter
	default VertexLabelWriter for write_graph More...

Functions
template<typename GraphType >
void	complement_graph (GraphType const &g, GraphType &gp, std::map< typename boost::graph_traits< GraphType >::vertex_descriptor, typename boost::graph_traits< GraphType >::vertex_descriptor > &mCompG2G)
	get the complement graph of original graph More...
template<typename GraphType , typename VertexLabelType , typename EdgeLabelType >
void	write_graph (std::ofstream &out, GraphType const &g, VertexLabelType const &vl, EdgeLabelType const &el)
	write graph to graphviz format and convert to pdf. Although Boost.Graph has write_graphviz component, it is not easy to use. More...
void	graphviz2pdf (std::string const &filename, const char *suffix=".gv")
	convert graphviz format to pdf. The input filename should be filename+suffix More...
template<typename GraphType >
vector< vector< typename boost::graph_traits< GraphType > ::vertex_descriptor > >	max_clique (GraphType const &g, size_t clique_num)
	use boost::bron_kerbosch_all_cliques to find all cliques and the maximum ones More...
template<typename GraphType , typename VisitorType , typename AlgorithmType >
void	max_independent_set (GraphType const &g, VisitorType vis, AlgorithmType const &)
template<typename GraphType , typename MisVisitorType >
void	max_independent_set (GraphType const &g, MisVisitorType vis, MaxIndependentSetByMaxClique const &)

Detailed Description

namespace for Limbo.algorithms

namespace for Limbo.Algorithms

Function Documentation

template<typename GraphType >

void limbo::algorithms::complement_graph	(	GraphType const &	g,
		GraphType &	gp,
		std::map< typename boost::graph_traits< GraphType >::vertex_descriptor, typename boost::graph_traits< GraphType >::vertex_descriptor > &	mCompG2G
	)

get the complement graph of original graph

Template Parameters

GraphType

graph type

Parameters

g	original graph
gp	complement graph
mCompG2G	a vertex mapping from complement graph to original graph

Definition at line 34 of file GraphUtility.h.

void limbo::algorithms::graphviz2pdf ( std::string const &  filename, const char *  suffix = ".gv"  )

inline

convert graphviz format to pdf. The input filename should be filename+suffix

Parameters

filename	output file name
suffix	file suffix

Definition at line 150 of file GraphUtility.h.

template<typename GraphType >

vector<vector<typename boost::graph_traits<GraphType>::vertex_descriptor> > limbo::algorithms::max_clique ( GraphType const &  g, size_t  clique_num  )

inline

use boost::bron_kerbosch_all_cliques to find all cliques and the maximum ones

Template Parameters

GraphType

graph type

Parameters

g	graph
clique_num	the minimum number of vertices the cliques contain

Returns

a set of cliques with at least clique_num vertices

Definition at line 71 of file MaxClique.h.

template<typename GraphType , typename VisitorType , typename AlgorithmType >

void limbo::algorithms::max_independent_set ( GraphType const &  g, VisitorType  vis, AlgorithmType const &    )

inline

generic function to calculate maximum independent sets with different algorithms

Template Parameters

GraphType	graph type
VisitorType	type of maximum independent set visitor
AlgorithmType	algorithm type

Parameters

g	graph
vis	once an independent set is found, callback vis.mis(MisType const&) will be called. In this way, user can choose to store all the independent sets or process one by one. Refer to limbo::algorithms::coloring::LawlerChromaticNumber::mis_visitor_type for example.

template<typename GraphType , typename MisVisitorType >

void limbo::algorithms::max_independent_set ( GraphType const &  g, MisVisitorType  vis, MaxIndependentSetByMaxClique const &    )

inline

A maximum independent set of a graph g is also a maximum clique of its complement graph. This function searches maximum cliques of the complement graph to get maximum independent sets

Template Parameters

GraphType	graph type
VisitorType	type of maximum independent set visitor

Parameters

g	graph
vis	once an independent set is found, callback vis.mis(MisType const&) will be called. In this way, user can choose to store all the independent sets or process one by one. Refer to limbo::algorithms::coloring::LawlerChromaticNumber::mis_visitor_type for example.

Definition at line 93 of file MaxIndependentSet.h.

template<typename GraphType , typename VertexLabelType , typename EdgeLabelType >

void limbo::algorithms::write_graph	(	std::ofstream &	out,
		GraphType const &	g,
		VertexLabelType const &	vl,
		EdgeLabelType const &	el
	)

write graph to graphviz format and convert to pdf. Although Boost.Graph has write_graphviz component, it is not easy to use.

Template Parameters

GraphType	graph type
VertexLabelType	must provide label() member function
EdgeLabelType	must provide label(), color(), and style() member function

Parameters

out	output stream
g	graph
vl	function object for vertex label
el	function object for edge label

Definition at line 119 of file GraphUtility.h.