|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-02 12:08:52
Author: asutton
Date: 2007-08-02 12:08:52 EDT (Thu, 02 Aug 2007)
New Revision: 38399
URL: http://svn.boost.org/trac/boost/changeset/38399
Log:
Fixing some style issues with cycles, cliques, and clustering
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/bron_kerbosch_all_cliques.hpp | 20 +++----
sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp | 100 ++++++++++++++++++++++----------------
sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp | 102 ++++++++++++++++-----------------------
3 files changed, 107 insertions(+), 115 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-02 12:08:52 EDT (Thu, 02 Aug 2007)
@@ -7,6 +7,8 @@
#ifndef BOOST_GRAPH_CLIQUE_HXX
#define BOOST_GRAPH_CLIQUE_HXX
+#include <limits>
+
namespace boost
{
@@ -86,14 +88,11 @@
typename graph_traits<Graph>::vertex_descriptor v,
typename graph_traits<Graph>::directed_category)
{
- // Note that this could alternate between using an or to determine
+ // 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
// 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;
}
@@ -113,12 +112,10 @@
}
}
- template <
- typename Graph,
- typename Clique, // compsub type
- typename Container, // candidates/not type
- typename Visitor
- >
+ template <typename Graph,
+ typename Clique, // compsub type
+ typename Container, // candidates/not type
+ typename Visitor>
void extend_clique(const Graph& g,
Clique& clique,
Container& cands,
@@ -165,7 +162,7 @@
// as a counter, but i'm jot really sure i followed it.
// otherwise, iterate over candidates and and test
- // for maxmim cliquiness.
+ // for maxmimal cliquiness.
typename Container::iterator i, j, end = cands.end();
for(i = cands.begin(); i != cands.end(); ) {
Vertex candidate = *i;
@@ -203,7 +200,6 @@
}
}
-
template <typename Graph, typename Visitor>
inline void
bron_kerbosch_all_cliques(const Graph& g, Visitor vis)
Modified: sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp 2007-08-02 12:08:52 EDT (Thu, 02 Aug 2007)
@@ -15,22 +15,24 @@
namespace detail
{
template <class Graph>
- inline size_t
- num_possible_edges(const Graph& g, size_t k, directed_tag)
+ inline typename graph_traits<Graph>::degree_size_type
+ possible_edges(const Graph& g, std::size_t k, directed_tag)
{
- return k * (k - 1);
+ typedef typename graph_traits<Graph>::degree_size_type T;
+ return T(k) * (T(k) - 1);
}
template <class Graph>
- inline size_t
- num_possible_edges(const Graph& g, size_t k, undirected_tag)
+ inline typename graph_traits<Graph>::degree_size_type
+ possible_edges(const Graph& g, size_t k, undirected_tag)
{
- return k * (k - 1) / 2;
+ // dirty little trick...
+ return possible_edges(g, k, directed_tag()) / 2;
}
// This template matches directedS and bidirectionalS.
template <class Graph>
- inline size_t
+ inline typename graph_traits<Graph>::degree_size_type
count_edges(const Graph& g,
typename Graph::vertex_descriptor u,
typename Graph::vertex_descriptor v,
@@ -43,7 +45,7 @@
// This template matches undirectedS
template <class Graph>
- inline size_t
+ inline typename graph_traits<Graph>::degree_size_type
count_edges(const Graph& g,
typename Graph::vertex_descriptor u,
typename Graph::vertex_descriptor v,
@@ -53,30 +55,23 @@
}
}
- template <typename Graph>
- inline size_t
- num_centered_triples(const Graph& g,
- typename Graph::vertex_descriptor v)
+ template <typename Graph, typename Vertex>
+ inline typename graph_traits<Graph>::degree_size_type
+ vertex_num_routes(const Graph& g, Vertex v)
{
- // find all of the adjacent vertices
typename graph_traits<Graph>::directed_category cat;
typename graph_traits<Graph>::adjacency_iterator i, end;
tie(i, end) = adjacent_vertices(v, g);
- size_t k = std::distance(i, end);
-
- size_t ret = detail::num_possible_edges(g, k, cat);
- return ret;
+ std::size_t k = std::distance(i, end);
+ return detail::possible_edges(g, k, cat);
}
- // This is seriously flawed for directed graphs...
- // Adjacenct vertices correspond to out degrees.
-
- template <typename Graph>
- inline size_t
- num_centered_triangles(const Graph& g,
- typename Graph::vertex_descriptor v)
+ template <typename Graph, typename Vertex>
+ inline typename graph_traits<Graph>::degree_size_type
+ vertex_num_triangles(const Graph& g, Vertex v)
{
- size_t count = 0;
+ typedef typename graph_traits<Graph>::degree_size_type T;
+ T count = 0;
typename graph_traits<Graph>::directed_category cat;
typename graph_traits<Graph>::adjacency_iterator i, j, end;
for(tie(i, end) = adjacent_vertices(v, g); i != end; ++i) {
@@ -87,29 +82,50 @@
return count;
}
- template <typename Graph>
- double
- clustering_coefficient(const Graph& g,
- typename Graph::vertex_descriptor v)
- {
- double ret = 0.0;
- double triples = (double)num_centered_triples(g, v);
- if(triples > 0.0) {
- ret = (double)num_centered_triangles(g, v) / triples;
+ template <typename T, typename Graph, typename Vertex>
+ inline T
+ vertex_clustering_coefficient(const Graph& g, Vertex v)
+ {
+ T zero(0);
+ T routes = T(vertex_num_routes(g, v));
+ return (routes > zero) ?
+ T(vertex_num_triangles(g, v)) / routes : zero;
+ }
+
+ template <typename Graph, typename Vertex>
+ inline float
+ vertex_clustering_coefficient(const Graph& g, Vertex v)
+ {
+ return vertex_clustering_coefficient<float>(g, v);
+ }
+
+ template <typename Graph, typename ClusteringMap>
+ inline void
+ clustering_coefficient(const Graph& g, ClusteringMap cluster)
+ {
+ typename graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cluster[*i] = vertex_clustering_coefficient<T>(g, *i);
}
- return ret;
}
- template <typename Graph>
- double
- clustering_coefficient(const Graph& g)
+ template <typename T, typename Graph>
+ inline T
+ graph_clustering_coefficient(const Graph& g)
{
- double cc = 0.0;
- typename Graph::vertex_iterator i, end;
+ T cc(0);
+ typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- cc += clustering_coefficient(g, *i);
+ cc += vertex_clustering_coefficient<T>(g, *i);
}
- return cc / (double)num_vertices(g);
+ return cc / T(num_vertices(g));
+ }
+
+ template <typename Graph>
+ inline float
+ graph_clustering_coefficient(const Graph& g)
+ {
+ return graph_clustering_coefficient<float>(g);
}
}
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-02 12:08:52 EDT (Thu, 02 Aug 2007)
@@ -43,8 +43,8 @@
// Oh... and there's explicit control structures - not just gotos.
//
// The problem is definitely NP-complete, an an unbounded implementation of this
- // will probably run for quite a while (i.e.) on a large graph. The conclusions
- // of this paper alkso reference a Paton algorithm for undirected graphs as being
+ // will probably run for quite a while on a large graph. The conclusions
+ // of this paper also reference a Paton algorithm for undirected graphs as being
// much more efficient (apparently based on spanning trees). Although not implemented,
// it can be found here:
//
@@ -81,9 +81,9 @@
{
template <typename Graph, typename Path>
inline bool
- is_in_path(const Graph&,
- typename graph_traits<Graph>::vertex_descriptor v,
- const Path& p)
+ is_vertex_in_path(const Graph&,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ const Path& p)
{
return (std::find(p.begin(), p.end(), v) != p.end());
}
@@ -107,25 +107,6 @@
template <typename Graph, typename Path, typename ClosedMatrix>
inline bool
- ignore_vertex(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- const Path& p,
- const ClosedMatrix& m)
- {
- // notice the vth index must be greater than the first index of
- // path in order for it to be considered.
-
- return get(vertex_index, g, p.front()) > get(vertex_index, g, v) ||
- is_in_path(g, v, p) ||
- is_path_closed(g, u, v, m);
- }
-
- template <
- typename Graph,
- typename Path,
- typename ClosedMatrix>
- inline bool
can_extend_path(const Graph& g,
typename graph_traits<Graph>::edge_descriptor e,
const Path& p,
@@ -145,24 +126,22 @@
// 3. the vertex v cannot be closed to the vertex u
bool indices = get(vertex_index, g, p.front()) < get(vertex_index, g, v);
- bool path = !is_in_path(g, v, p);
+ bool path = !is_vertex_in_path(g, v, p);
bool closed = !is_path_closed(g, u, v, m);
return indices && path && closed;
}
- template <
- typename Graph,
- typename Path>
+ template <typename Graph, typename Path>
inline bool
- can_wrap_path(const Graph& g,
- const Path& p)
+ can_wrap_path(const Graph& g, const Path& p)
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;
// iterate over the out-edges of the back, looking for the
// front of the path. also, we can't travel along the same
- // edge that we did on the way here.
+ // edge that we did on the way here, but we don't quite have the
+ // stringent requirements that we do in can_extend_path().
Vertex
u = p.back(),
v = p.front();
@@ -175,8 +154,7 @@
return false;
}
- template <
- typename Graph,
+ template <typename Graph,
typename Path,
typename ClosedMatrix>
inline typename graph_traits<Graph>::vertex_descriptor
@@ -208,13 +186,9 @@
return ret;
}
- template <typename Graph,
- typename Path,
- typename ClosedMatrix>
+ template <typename Graph, typename Path, typename ClosedMatrix>
inline bool
- exhaust_paths(const Graph& g,
- Path& p,
- ClosedMatrix& closed)
+ exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
@@ -241,31 +215,21 @@
}
}
- template <typename Graph, typename Visitor>
+ template <typename Graph, typename Vertex, typename Visitor>
inline void
- all_cycles_at_vertex(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor v,
- Visitor vis,
- std::size_t maxlen,
- std::size_t minlen)
+ all_cycles_from_vertex(const Graph& g,
+ Vertex v,
+ Visitor vis,
+ std::size_t minlen,
+ std::size_t maxlen)
{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
typedef std::vector<Vertex> Path;
typedef std::vector<Vertex> VertexList;
typedef std::vector<VertexList> ClosedMatrix;
- // this is an added type that helps us determine traversability
- // for paths in undirected graphs. Specifically, when we consider
- // traversability, we have to ensure that the move to the next
- // vertex does not walk down the same path as this vertex.
-
- const Vertex null = graph_traits<Graph>::null_vertex();
-
- // The path is the sequence of vertices
Path p;
ClosedMatrix closed(num_vertices(g), VertexList());
+ const Vertex null = graph_traits<Graph>::null_vertex();
// each path investigation starts at the ith vertex
p.push_back(v);
@@ -275,13 +239,13 @@
// maxlen-sized cycle
Vertex j = null;
while(((j = detail::extend_path(g, p, closed)) != null)
- && (p.size() < maxlen))
+ && (p.size() < maxlen))
; // empty loop
// if we're done extending the path and there's an edge
// connecting the back to the front, then we should have
// a cycle.
- if(can_wrap_path(g, p) && p.size() > minlen) {
+ if(detail::can_wrap_path(g, p) && p.size() >= minlen) {
vis.cycle(p, g);
}
@@ -290,11 +254,16 @@
}
}
}
+
+
+ template <typename D> struct min_cycles { enum { value = 2 }; };
+ template <> struct min_cycles<undirected_tag> { enum { value = 3 }; };
}
template <typename Graph, typename Visitor>
inline void
- tiernan_all_cycles(const Graph& g, Visitor vis,
+ tiernan_all_cycles(const Graph& g,
+ Visitor vis,
std::size_t minlen,
std::size_t maxlen)
{
@@ -302,15 +271,26 @@
VertexIterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- detail::all_cycles_at_vertex(g, *i, vis, maxlen, minlen);
+ detail::all_cycles_from_vertex(g, *i, vis, minlen, maxlen);
}
}
template <typename Graph, typename Visitor>
inline void
+ tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t maxlen)
+ {
+ typedef typename graph_traits<Graph>::directed_category Dir;
+ tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value, maxlen);
+ }
+
+ template <typename Graph, typename Visitor>
+ inline void
tiernan_all_cycles(const Graph& g, Visitor vis)
{
- tiernan_all_cycles(g, vis, 2, std::numeric_limits<std::size_t>::max());
+ typedef typename graph_traits<Graph>::directed_category Dir;
+ tiernan_all_cycles(g, vis,
+ detail::min_cycles<Dir>::value,
+ std::numeric_limits<std::size_t>::max());
}
}
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