#include <boost/graph/lookup_edge.hpp>
#include <boost/concept/detail/concept_def.hpp>
-namespace boost {
- namespace concepts {
- BOOST_concept(CliqueVisitor,(Visitor)(Clique)(Graph))
- {
- BOOST_CONCEPT_USAGE(CliqueVisitor)
- {
- vis.clique(k, g);
- }
- private:
- Visitor vis;
- Graph g;
- Clique k;
- };
- } /* namespace concepts */
+namespace boost
+{
+namespace concepts
+{
+ BOOST_concept(CliqueVisitor, (Visitor)(Clique)(Graph))
+ {
+ BOOST_CONCEPT_USAGE(CliqueVisitor) { vis.clique(k, g); }
+
+ private:
+ Visitor vis;
+ Graph g;
+ Clique k;
+ };
+} /* namespace concepts */
using concepts::CliqueVisitorConcept;
} /* namespace boost */
#include <boost/concept/detail/concept_undef.hpp>
//
// @article{DBLP:journals/tcs/TomitaTT06,
// author = {Etsuji Tomita and Akira Tanaka and Haruhisa Takahashi},
-// title = {The worst-case time complexity for generating all maximal cliques and computational experiments},
-// journal = {Theor. Comput. Sci.},
-// volume = {363},
-// number = {1},
-// year = {2006},
-// pages = {28-42}
+// title = {The worst-case time complexity for generating all maximal
+// cliques and computational experiments}, journal = {Theor. Comput.
+// Sci.}, volume = {363}, number = {1}, year = {2006}, pages = {28-42}
// ee = {https://doi.org/10.1016/j.tcs.2006.06.015}
// }
*/
struct clique_visitor
{
- template <typename VertexSet, typename Graph>
+ template < typename VertexSet, typename Graph >
void clique(const VertexSet&, Graph&)
- { }
+ {
+ }
};
/**
*/
struct max_clique_visitor
{
- max_clique_visitor(std::size_t& max)
- : maximum(max)
- { }
+ max_clique_visitor(std::size_t& max) : maximum(max) {}
- template <typename Clique, typename Graph>
+ template < typename Clique, typename Graph >
inline void clique(const Clique& p, const Graph& g)
{
BOOST_USING_STD_MAX();
- maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION (maximum, p.size());
+ maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION(maximum, p.size());
}
std::size_t& maximum;
};
inline max_clique_visitor find_max_clique(std::size_t& max)
-{ return max_clique_visitor(max); }
+{
+ return max_clique_visitor(max);
+}
namespace detail
{
- template <typename Graph>
- inline bool
- is_connected_to_clique(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- typename graph_traits<Graph>::undirected_category)
+ template < typename Graph >
+ inline bool is_connected_to_clique(const Graph& g,
+ typename graph_traits< Graph >::vertex_descriptor u,
+ typename graph_traits< Graph >::vertex_descriptor v,
+ typename graph_traits< Graph >::undirected_category)
{
return lookup_edge(u, v, g).second;
}
- template <typename Graph>
- inline bool
- is_connected_to_clique(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- typename graph_traits<Graph>::directed_category)
+ template < typename Graph >
+ inline bool is_connected_to_clique(const Graph& g,
+ typename graph_traits< Graph >::vertex_descriptor u,
+ typename graph_traits< Graph >::vertex_descriptor v,
+ typename graph_traits< Graph >::directed_category)
{
// Note that this could alternate between using an || to determine
// full connectivity. I believe that this should produce strongly
return lookup_edge(u, v, g).second && lookup_edge(v, u, g).second;
}
- template <typename Graph, typename Container>
- inline void
- filter_unconnected_vertices(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor v,
- const Container& in,
- Container& out)
+ template < typename Graph, typename Container >
+ inline void filter_unconnected_vertices(const Graph& g,
+ typename graph_traits< Graph >::vertex_descriptor v,
+ const Container& in, Container& out)
{
- BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
+ BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
- typename graph_traits<Graph>::directed_category cat;
+ typename graph_traits< Graph >::directed_category cat;
typename Container::const_iterator i, end = in.end();
- for(i = in.begin(); i != end; ++i) {
- if(is_connected_to_clique(g, v, *i, cat)) {
+ for (i = in.begin(); i != end; ++i)
+ {
+ if (is_connected_to_clique(g, v, *i, cat))
+ {
out.push_back(*i);
}
}
}
- template <
- typename Graph,
- typename Clique, // compsub type
- typename Container, // candidates/not type
- typename Visitor>
- void extend_clique(const Graph& g,
- Clique& clique,
- Container& cands,
- Container& nots,
- Visitor vis,
- std::size_t min)
+ template < typename Graph,
+ typename Clique, // compsub type
+ typename Container, // candidates/not type
+ typename Visitor >
+ void extend_clique(const Graph& g, Clique& clique, Container& cands,
+ Container& nots, Visitor vis, std::size_t min)
{
- BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
- BOOST_CONCEPT_ASSERT(( CliqueVisitorConcept<Visitor,Clique,Graph> ));
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
+ BOOST_CONCEPT_ASSERT((CliqueVisitorConcept< Visitor, Clique, Graph >));
+ typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
// Is there vertex in nots that is connected to all vertices
// in the candidate set? If so, no clique can ever be found.
{
typename Container::iterator ni, nend = nots.end();
typename Container::iterator ci, cend = cands.end();
- for(ni = nots.begin(); ni != nend; ++ni) {
- for(ci = cands.begin(); ci != cend; ++ci) {
+ for (ni = nots.begin(); ni != nend; ++ni)
+ {
+ for (ci = cands.begin(); ci != cend; ++ci)
+ {
// if we don't find an edge, then we're okay.
- if(!lookup_edge(*ni, *ci, g).second) break;
+ if (!lookup_edge(*ni, *ci, g).second)
+ break;
}
// if we iterated all the way to the end, then *ni
// is connected to all *ci
- if(ci == cend) break;
+ if (ci == cend)
+ break;
}
// if we broke early, we found *ni connected to all *ci
- if(ni != nend) return;
+ if (ni != nend)
+ return;
}
// TODO: the original algorithm 457 describes an alternative
// otherwise, iterate over candidates and and test
// for maxmimal cliquiness.
typename Container::iterator i, j;
- for(i = cands.begin(); i != cands.end(); ) {
+ for (i = cands.begin(); i != cands.end();)
+ {
Vertex candidate = *i;
// add the candidate to the clique (keeping the iterator!)
- // typename Clique::iterator ci = clique.insert(clique.end(), candidate);
+ // typename Clique::iterator ci = clique.insert(clique.end(),
+ // candidate);
clique.push_back(candidate);
// remove it from the candidate set
filter_unconnected_vertices(g, candidate, cands, new_cands);
filter_unconnected_vertices(g, candidate, nots, new_nots);
- if(new_cands.empty() && new_nots.empty()) {
+ if (new_cands.empty() && new_nots.empty())
+ {
// our current clique is maximal since there's nothing
// that's connected that we haven't already visited. If
// the clique is below our radar, then we won't visit it.
- if(clique.size() >= min) {
+ if (clique.size() >= min)
+ {
vis.clique(clique, g);
}
}
- else {
+ else
+ {
// recurse to explore the new candidates
extend_clique(g, clique, new_cands, new_nots, vis, min);
}
}
} /* namespace detail */
-template <typename Graph, typename Visitor>
-inline void
-bron_kerbosch_all_cliques(const Graph& g, Visitor vis, std::size_t min)
+template < typename Graph, typename Visitor >
+inline void bron_kerbosch_all_cliques(
+ const Graph& g, Visitor vis, std::size_t min)
{
- BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
- BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph> )); // Structural requirement only
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
- typedef std::vector<Vertex> VertexSet;
- typedef std::deque<Vertex> Clique;
- BOOST_CONCEPT_ASSERT(( CliqueVisitorConcept<Visitor,Clique,Graph> ));
+ BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
+ BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
+ BOOST_CONCEPT_ASSERT(
+ (AdjacencyMatrixConcept< Graph >)); // Structural requirement only
+ typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
+ typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
+ typedef std::vector< Vertex > VertexSet;
+ typedef std::deque< Vertex > Clique;
+ BOOST_CONCEPT_ASSERT((CliqueVisitorConcept< Visitor, Clique, Graph >));
// NOTE: We're using a deque to implement the clique, because it provides
// constant inserts and removals at the end and also a constant size.
VertexIterator i, end;
boost::tie(i, end) = vertices(g);
- VertexSet cands(i, end); // start with all vertices as candidates
- VertexSet nots; // start with no vertices visited
+ VertexSet cands(i, end); // start with all vertices as candidates
+ VertexSet nots; // start with no vertices visited
- Clique clique; // the first clique is an empty vertex set
+ Clique clique; // the first clique is an empty vertex set
detail::extend_clique(g, clique, cands, nots, vis, min);
}
// NOTE: By default the minimum number of vertices per clique is set at 2
// because singleton cliques aren't really very interesting.
-template <typename Graph, typename Visitor>
-inline void
-bron_kerbosch_all_cliques(const Graph& g, Visitor vis)
-{ bron_kerbosch_all_cliques(g, vis, 2); }
-
-template <typename Graph>
-inline std::size_t
-bron_kerbosch_clique_number(const Graph& g)
+template < typename Graph, typename Visitor >
+inline void bron_kerbosch_all_cliques(const Graph& g, Visitor vis)
+{
+ bron_kerbosch_all_cliques(g, vis, 2);
+}
+
+template < typename Graph >
+inline std::size_t bron_kerbosch_clique_number(const Graph& g)
{
std::size_t ret = 0;
bron_kerbosch_all_cliques(g, find_max_clique(ret));
projects / ceph.git / blobdiff