Limbo
|
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 &) |
namespace for Limbo.algorithms
namespace for Limbo.Algorithms
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
GraphType | graph type |
g | original graph |
gp | complement graph |
mCompG2G | a vertex mapping from complement graph to original graph |
Definition at line 34 of file GraphUtility.h.
|
inline |
convert graphviz format to pdf. The input filename should be filename+suffix
filename | output file name |
suffix | file suffix |
Definition at line 150 of file GraphUtility.h.
|
inline |
use boost::bron_kerbosch_all_cliques to find all cliques and the maximum ones
GraphType | graph type |
g | graph |
clique_num | the minimum number of vertices the cliques contain |
Definition at line 71 of file MaxClique.h.
|
inline |
generic function to calculate maximum independent sets with different algorithms
GraphType | graph type |
VisitorType | type of maximum independent set visitor |
AlgorithmType | algorithm type |
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. |
|
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
GraphType | graph type |
VisitorType | type of maximum independent set visitor |
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.
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.
GraphType | graph type |
VertexLabelType | must provide label() member function |
EdgeLabelType | must provide label(), color(), and style() member function |
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.