|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-21 14:05:04
Author: asutton
Date: 2007-08-21 14:05:03 EDT (Tue, 21 Aug 2007)
New Revision: 38830
URL: http://svn.boost.org/trac/boost/changeset/38830
Log:
Concept checks in bron kerbosch
Bug fixes in directed graph (broken renumber edges)
Added null_property_map that basically does noops.
Added:
sandbox/SOC/2007/graphs/boost/graph/null_property_map.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/bron_kerbosch_all_cliques.hpp | 91 +++++++++++++++++++++++++++++++++------
sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp | 58 ++++++++++++++++++++++--
sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp | 7 ++
sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp | 39 +++++++++++++++-
4 files changed, 169 insertions(+), 26 deletions(-)
Modified: sandbox/SOC/2007/graphs/boost/graph/bron_kerbosch_all_cliques.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/bron_kerbosch_all_cliques.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/bron_kerbosch_all_cliques.hpp 2007-08-21 14:05:03 EDT (Tue, 21 Aug 2007)
@@ -7,7 +7,10 @@
#ifndef BOOST_GRAPH_CLIQUE_HXX
#define BOOST_GRAPH_CLIQUE_HXX
-#include <limits>
+#include <vector>
+#include <deque>
+
+#include <boost/graph/new_graph_concepts.hpp>
namespace boost
{
@@ -60,7 +63,7 @@
// year = {2006},
// pages = {28-42}
// ee = {http://dx.doi.org/10.1016/j.tcs.2006.06.015}
- // }
+ // }
struct clique_visitor
{
@@ -69,6 +72,23 @@
{ }
};
+ struct max_clique_visitor
+ {
+ max_clique_visitor(std::size_t& max)
+ : maximum(max)
+ { }
+
+ template <typename Clique, typename Graph>
+ inline void clique(const Clique& p, const Graph& g)
+ {
+ maximum = std::max(maximum, p.size());
+ }
+ std::size_t& maximum;
+ };
+
+ inline max_clique_visitor find_max_clique(std::size_t& max)
+ { return max_clique_visitor(max); }
+
namespace detail
{
template <typename Graph>
@@ -78,6 +98,8 @@
typename graph_traits<Graph>::vertex_descriptor v,
typename graph_traits<Graph>::undirected_category)
{
+ function_requires< AdjacencyMatrixConcept<Graph> >();
+
return edge(u, v, g).second;
}
@@ -88,6 +110,7 @@
typename graph_traits<Graph>::vertex_descriptor v,
typename graph_traits<Graph>::directed_category)
{
+ function_requires< AdjacencyMatrixConcept<Graph> >();
// Note that this could alternate between using an || to determine
// full connectivity. I believe that this should produce strongly
// connected components. Note that using && instead of || will
@@ -103,6 +126,8 @@
const Container& in,
Container& out)
{
+ function_requires< GraphConcept<Graph> >();
+
typename graph_traits<Graph>::directed_category cat;
typename Container::const_iterator i, end = in.end();
for(i = in.begin(); i != end; ++i) {
@@ -120,13 +145,17 @@
Clique& clique,
Container& cands,
Container& nots,
- Visitor vis)
+ Visitor vis,
+ std::size_t min)
{
+ function_requires< GraphConcept<Graph> >();
+ function_requires< 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.
+ // This could be broken out into a separate function.
{
- // 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) {
@@ -161,6 +190,10 @@
// there's some other stuff about using the number of disconnects
// as a counter, but i'm jot really sure i followed it.
+ // TODO: If we min-sized cliques to visit, then theoretically, we
+ // should be able to stop recursing if the clique falls below that
+ // size - maybe?
+
// otherwise, iterate over candidates and and test
// for maxmimal cliquiness.
typename Container::iterator i, j, end = cands.end();
@@ -168,8 +201,8 @@
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
i = cands.erase(i);
@@ -184,38 +217,66 @@
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);
+ // 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) {
+ vis.clique(clique, g);
+ }
}
else {
// recurse to explore the new candidates
- extend_clique(g, clique, new_cands, new_nots, vis);
+ extend_clique(g, clique, new_cands, new_nots, vis, min);
}
// 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);
+ clique.pop_back();
}
}
}
template <typename Graph, typename Visitor>
inline void
- bron_kerbosch_all_cliques(const Graph& g, Visitor vis)
+ bron_kerbosch_all_cliques(const Graph& g, Visitor vis, std::size_t min)
{
+ function_requires< IncidenceGraphConcept<Graph> >();
+ function_requires< VertexListGraphConcept<Graph> >();
+ function_requires< VertexIndexGraphConcept<Graph> >();
+ function_requires< 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::list<Vertex> Clique;
+ typedef std::deque<Vertex> Clique;
+ function_requires< 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;
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_clique(g, clique, cands, nots, vis);
+ detail::extend_clique(g, clique, cands, nots, vis, min);
+ }
+
+ template <typename Graph, typename Visitor>
+ inline void
+ bron_kerbosch_all_cliques(const Graph& g, Visitor vis)
+ {
+ // Default is 2 since a single vertex isn't connected to anything.
+ 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));
+ return ret;
}
}
Modified: sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp 2007-08-21 14:05:03 EDT (Tue, 21 Aug 2007)
@@ -13,7 +13,7 @@
namespace boost
{
- struct directed_graph_tag {};
+ struct directed_graph_tag { };
template <
typename VertexProperty = no_property,
@@ -80,7 +80,7 @@
, m_num_edges(0)
, m_max_vertex_index(0)
, m_max_edge_index(0)
- {}
+ { }
inline directed_graph(const directed_graph& x)
: m_graph(x)
@@ -88,7 +88,7 @@
, m_num_edges(x.m_num_edges)
, m_max_vertex_index(x.m_max_vertex_index)
, m_max_edge_index(x.m_max_edge_index)
- {}
+ { }
inline directed_graph(vertices_size_type n,
const GraphProperty& p = GraphProperty())
@@ -97,7 +97,24 @@
, m_num_edges(0)
, m_max_vertex_index(n)
, m_max_edge_index(0)
- {}
+ { }
+
+ template <typename EdgeIterator>
+ inline directed_graph(EdgeIterator f,
+ EdgeIterator l,
+ vertices_size_type n,
+ edges_size_type m = 0,
+ const GraphProperty& p = GraphProperty())
+ : m_graph(f, l, n, m, p)
+ , m_num_vertices(n)
+ , m_num_edges(0)
+ , m_max_vertex_index(n)
+ , m_max_edge_index(0)
+ {
+ // Can't always guarantee that the number of edges is actually
+ // m if distance(f, l) != m (or is undefined).
+ m_num_edges = m_max_edge_index = boost::num_edges(m_graph);
+ }
inline directed_graph& operator =(const directed_graph& g)
{
@@ -221,14 +238,14 @@
renumber_edge_indices()
{
edge_iterator i, end;
- tie(i, end) = vertices(m_graph);
+ tie(i, end) = edges(m_graph);
m_max_edge_index = renumber_edge_indices(i, end, 0);
}
inline void
remove_edge_and_renumber_indices(edge_iterator i)
{
- edge_iterator j = next(i), end = vertices(m_graph).second;
+ edge_iterator j = next(i), end = edges(m_graph).second;
edge_index_type n = get(edge_index, m_graph, *i);
// remove the offending edge and renumber everything after
@@ -236,6 +253,13 @@
m_max_edge_index = renumber_edge_indices(j, end, n);
}
+ inline void
+ renumber_indices()
+ {
+ renumber_vertex_indices();
+ renumber_edge_indices();
+ }
+
// bundled property support
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
vertex_bundled& operator [](vertex_descriptor v)
@@ -255,6 +279,22 @@
static inline vertex_descriptor null_vertex()
{ return graph_type::null_vertex(); }
+ inline void clear()
+ {
+ m_graph.clear();
+ m_num_vertices = m_max_vertex_index = 0;
+ m_num_edges = m_max_edge_index = 0;
+ }
+
+ inline void swap(directed_graph& g)
+ {
+ m_graph.swap(g);
+ std::swap(m_num_vertices, g.m_num_vertices);
+ std::swap(m_max_vertex_index, g.m_max_vertex_index);
+ std::swap(m_num_edges, g.m_num_edges);
+ std::swap(m_max_edge_index, g.m_max_edge_index);
+ }
+
private:
inline vertices_size_type
renumber_vertex_indices(vertex_iterator i,
@@ -686,6 +726,12 @@
remove_edge_and_renumber_indices(typename directed_graph<VP,EP,GP>::edge_iterator i,
directed_graph<VP,EP,GP>& g)
{ g.remove_edge_and_renumber_indices(i); }
+
+ // Index management
+ template <class VP, class EP, class GP>
+ inline void
+ renumber_indices(directed_graph<VP,EP,GP>& g)
+ { g.renumber_indices(); }
}
#endif
Added: sandbox/SOC/2007/graphs/boost/graph/null_property_map.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/null_property_map.hpp 2007-08-21 14:05:03 EDT (Tue, 21 Aug 2007)
@@ -0,0 +1,38 @@
+// (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_NULL_PROPERTY_HPP
+#define BOOST_GRAPH_NULL_PROPERTY_HPP
+
+#include <boost/property_map.hpp>
+
+namespace boost
+{
+ // A null property is somewhat like the inverse of the constant
+ // property map except that instead of returning a single value,
+ // this eats any writes and cannot be read from.
+
+ template <typename Key, typename Value>
+ struct null_property_map
+ {
+ typedef Key key_type;
+ typedef Value value_type;
+ typedef void reference;
+ typedef boost::writable_property_map_tag category;
+ };
+
+ // The null_property_map<K,V> only has a put() function.
+ template <typename K, typename V>
+ void put(null_property_map<K,V>& pm, const K& key, const V& value)
+ { }
+
+ // A helper function for intantiating null property maps.
+ template <typename Key, typename Value>
+ inline null_property_map<Key, Value> make_null_property()
+ { return null_property_map<Key, Value>(); }
+}
+
+#endif
Modified: sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp 2007-08-21 14:05:03 EDT (Tue, 21 Aug 2007)
@@ -86,6 +86,10 @@
std::size_t& maximum;
};
+ inline min_max_cycle_visitor
+ find_min_max_cycle(std::size_t& min, std::size_t& max)
+ { return min_max_cycle_visitor(min, max); }
+
namespace detail
{
template <typename Graph, typename Path>
@@ -318,8 +322,7 @@
std::size_t
min = std::numeric_limits<std::size_t>::max(),
max = 0;
- min_max_cycle_visitor vis(min, max);
- tiernan_all_cycles(g, vis);
+ tiernan_all_cycles(g, find_min_max_cycle(min, max));
// if this is the case, the graph is acyclic...
if(max == 0) max = min;
Modified: sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp 2007-08-21 14:05:03 EDT (Tue, 21 Aug 2007)
@@ -77,7 +77,7 @@
, m_num_edges(0)
, m_max_vertex_index(0)
, m_max_edge_index(0)
- {}
+ { }
inline undirected_graph(const undirected_graph& x)
: m_graph(x)
@@ -85,7 +85,7 @@
, m_num_edges(x.m_num_edges)
, m_max_vertex_index(x.m_max_vertex_index)
, m_max_edge_index(x.m_max_edge_index)
- {}
+ { }
inline undirected_graph(vertices_size_type n,
const GraphProperty& p = GraphProperty())
@@ -94,7 +94,24 @@
, m_num_edges(0)
, m_max_vertex_index(n)
, m_max_edge_index(0)
- {}
+ { }
+
+ template <typename EdgeIterator>
+ inline undirected_graph(EdgeIterator f,
+ EdgeIterator l,
+ vertices_size_type n,
+ edges_size_type m = 0,
+ const GraphProperty& p = GraphProperty())
+ : m_graph(f, l, n, m, p)
+ , m_num_vertices(n)
+ , m_num_edges(0)
+ , m_max_vertex_index(n)
+ , m_max_edge_index(0)
+ {
+ // Can't always guarantee that the number of edges is actually
+ // m if distance(f, l) != m (or is undefined).
+ m_num_edges = m_max_edge_index = boost::num_edges(m_graph);
+ }
inline undirected_graph& operator =(const undirected_graph& g)
{
@@ -255,6 +272,22 @@
static inline vertex_descriptor null_vertex()
{ return graph_type::null_vertex(); }
+ inline void clear()
+ {
+ m_graph.clear();
+ m_num_vertices = m_max_vertex_index = 0;
+ m_num_edges = m_max_edge_index = 0;
+ }
+
+ inline void swap(undirected_graph& g)
+ {
+ m_graph.swap(g);
+ std::swap(m_num_vertices, g.m_num_vertices);
+ std::swap(m_max_vertex_index, g.m_max_vertex_index);
+ std::swap(m_num_edges, g.m_num_edges);
+ std::swap(m_max_edge_index, g.m_max_edge_index);
+ }
+
private:
inline vertices_size_type
renumber_vertex_indices(vertex_iterator i,
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk