From: asutton_at_[hidden]
Date: 2007-07-16 18:48:26
Author: asutton
Date: 2007-07-16 18:48:26 EDT (Mon, 16 Jul 2007)
New Revision: 7450
URL: http://svn.boost.org/trac/boost/changeset/7450
Log:
Added clique header
Added:
sandbox/SOC/2007/graphs/boost/graph/clique.hpp
Added: sandbox/SOC/2007/graphs/boost/graph/clique.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/clique.hpp 2007-07-16 18:48:26 EDT (Mon, 16 Jul 2007)
@@ -0,0 +1,181 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_CLIQUE_HXX
+#define BOOST_GRAPH_CLIQUE_HXX
+
+namespace boost
+{
+
+ // I'm basically reimplementing the networkX version of the
+ // algorithm since it's a little more clear than the published
+ // version. It also appears to operate on a non-matrix structure
+ // which makes the translation a little easier.
+
+ struct clique_visitor
+ {
+ template <typename VertexSet, typename Graph>
+ void clique(const VertexSet&, Graph&)
+ { }
+ };
+
+ namespace detail
+ {
+ template <typename Graph>
+ inline bool
+ is_clique_connected(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ typename graph_traits<Graph>::undirected_category)
+ {
+ return edge(u, v, g).second;
+ }
+
+ template <typename Graph>
+ inline bool
+ is_clique_connected(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 or to determine
+ // full connectivity. I believe that this should produce strongly
+ // connected components. Note that using && instead of || will
+ // change the results to a fully connected subgraph (i.e., symmetric
+ // edges between all vertices s.t., if a->b, then b->a.
+ //
+ // TODO: use this, the other, or allow switching based on a user-
+ // define strategy.
+ return edge(u, v, g).second || 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)
+ {
+ typename graph_traits<Graph>::directed_category cat;
+ typename Container::const_iterator i, end = in.end();
+ for(i = in.begin(); i != end; ++i) {
+ if(is_clique_connected(g, v, *i, cat)) {
+ out.push_back(*i);
+ }
+ }
+ }
+
+ template <
+ typename Graph,
+ typename Clique, // compsub type
+ typename Container, // candidates/not type
+ typename Visitor
+ >
+ void extend(const Graph& g,
+ Clique& clique,
+ Container& cands,
+ Container& nots,
+ Visitor vis)
+ {
+ 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) {
+ // if we don't find an edge, then we're okay.
+ if(!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 we broke early, we found *ni connected to all *ci
+ if(ni != nend) return;
+ }
+
+ // TODO: the original algorithm 457 describes an alternative
+ // (albeit really complicated) mechanism for selecting candidates.
+ // The given optimizaiton seeks to bring about the above
+ // condition sooner (i.e., there is a vertex in the not set
+ // that is connected to all candidates). unfortunately, the
+ // method they give for doing this is fairly unclear.
+
+ // basically, for every vertex in not, we should know how many
+ // vertices it is disconnected from in the candidate set. if
+ // we fix some vertex in the not set, then we want to keep
+ // choosing vertices that are not connected to that fixed vertex.
+ // apparently, by selecting fix point with the minimum number
+ // of disconnections (i.e., the maximum number of connections
+ // within the candidate set), then the previous condition wil
+ // be reached sooner.
+
+ // there's some other stuff about using the number of disconnects
+ // as a counter, but i'm jot really sure i followed it.
+
+ // otherwise, iterate over candidates and and test
+ // for maxmim cliquiness.
+ typename Container::iterator i, j, end = 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);
+
+ // remove it from the candidate set
+ i = cands.erase(i);
+
+ // build new candidate and not sets by removing all vertices
+ // that are not connected to the current candidate vertex.
+ // these actually invert the operation, adding them to the new
+ // sets if the vertices are connected. its semantically the same.
+ Container new_cands, new_nots;
+ filter_unconnected_vertices(g, candidate, cands, new_cands);
+ filter_unconnected_vertices(g, candidate, nots, new_nots);
+
+ 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
+ vis.clique(clique, g);
+ }
+ else {
+ // recurse to explore the new candidates
+ extend(g, clique, new_cands, new_nots, vis);
+ }
+
+ // we're done with this vertex, so we need to move it
+ // to the nots, and remove the candidate from the clique.
+ nots.push_back(candidate);
+ clique.erase(ci);
+ }
+ }
+ }
+
+
+ template <typename Graph, typename Visitor>
+ inline void
+ visit_cliques(const Graph& g, Visitor vis)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ typedef std::vector<Vertex> VertexSet;
+ typedef std::list<Vertex> Clique;
+
+ VertexIterator i, end;
+ tie(i, end) = vertices(g);
+
+ 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
+ detail::extend(g, clique, cands, nots, vis);
+ }
+}
+
+#endif