#include <boost/concept/assert.hpp>
#include <boost/concept/detail/concept_def.hpp>
-namespace boost {
- namespace concepts {
- BOOST_concept(CycleVisitor,(Visitor)(Path)(Graph))
- {
- BOOST_CONCEPT_USAGE(CycleVisitor)
- {
- vis.cycle(p, g);
- }
- private:
- Visitor vis;
- Graph g;
- Path p;
- };
- } /* namespace concepts */
+namespace boost
+{
+namespace concepts
+{
+ BOOST_concept(CycleVisitor, (Visitor)(Path)(Graph))
+ {
+ BOOST_CONCEPT_USAGE(CycleVisitor) { vis.cycle(p, g); }
+
+ private:
+ Visitor vis;
+ Graph g;
+ Path p;
+ };
+} /* namespace concepts */
using concepts::CycleVisitorConcept;
} /* namespace boost */
#include <boost/concept/detail/concept_undef.hpp>
-
namespace boost
{
//
// @article{362819,
// author = {James C. Tiernan},
-// title = {An efficient search algorithm to find the elementary circuits of a graph},
-// journal = {Commun. ACM},
-// volume = {13},
-// number = {12},
-// year = {1970},
-// issn = {0001-0782},
-// pages = {722--726},
-// doi = {http://doi.acm.org/10.1145/362814.362819},
+// title = {An efficient search algorithm to find the elementary
+// circuits of a graph}, journal = {Commun. ACM}, volume = {13}, number
+// = {12}, year = {1970}, issn = {0001-0782}, pages = {722--726}, doi =
+// {http://doi.acm.org/10.1145/362814.362819},
// publisher = {ACM Press},
// address = {New York, NY, USA},
// }
//
-// It should be pointed out that the author does not provide a complete analysis for
-// either time or space. This is in part, due to the fact that it's a fairly input
-// sensitive problem related to the density and construction of the graph, not just
-// its size.
+// It should be pointed out that the author does not provide a complete analysis
+// for either time or space. This is in part, due to the fact that it's a fairly
+// input sensitive problem related to the density and construction of the graph,
+// not just its size.
//
-// I've also taken some liberties with the interpretation of the algorithm - I've
-// basically modernized it to use real data structures (no more arrays and matrices).
-// Oh... and there's explicit control structures - not just gotos.
+// I've also taken some liberties with the interpretation of the algorithm -
+// I've basically modernized it to use real data structures (no more arrays and
+// matrices). Oh... and there's explicit control structures - not just gotos.
//
// The problem is definitely NP-complete, an unbounded implementation of this
// 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:
+// much more efficient (apparently based on spanning trees). Although not
+// implemented, it can be found here:
//
// @article{363232,
// author = {Keith Paton},
-// title = {An algorithm for finding a fundamental set of cycles of a graph},
-// journal = {Commun. ACM},
-// volume = {12},
-// number = {9},
-// year = {1969},
-// issn = {0001-0782},
-// pages = {514--518},
-// doi = {http://doi.acm.org/10.1145/363219.363232},
+// title = {An algorithm for finding a fundamental set of cycles of a
+// graph}, journal = {Commun. ACM}, volume = {12}, number = {9}, year =
+// {1969}, issn = {0001-0782}, pages = {514--518}, doi =
+// {http://doi.acm.org/10.1145/363219.363232},
// publisher = {ACM Press},
// address = {New York, NY, USA},
// }
*/
struct cycle_visitor
{
- template <typename Path, typename Graph>
+ template < typename Path, typename Graph >
inline void cycle(const Path& p, const Graph& g)
- { }
+ {
+ }
};
/**
struct min_max_cycle_visitor
{
min_max_cycle_visitor(std::size_t& min_, std::size_t& max_)
- : minimum(min_), maximum(max_)
- { }
+ : minimum(min_), maximum(max_)
+ {
+ }
- template <typename Path, typename Graph>
+ template < typename Path, typename Graph >
inline void cycle(const Path& p, const Graph& g)
{
BOOST_USING_STD_MIN();
BOOST_USING_STD_MAX();
std::size_t len = p.size();
- minimum = min BOOST_PREVENT_MACRO_SUBSTITUTION (minimum, len);
- maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION (maximum, len);
+ minimum = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum, len);
+ maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION(maximum, len);
}
std::size_t& minimum;
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_); }
+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>
- inline bool
- is_vertex_in_path(const Graph&,
- typename graph_traits<Graph>::vertex_descriptor v,
- const Path& p)
+ template < typename Graph, typename Path >
+ inline bool 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());
}
- template <typename Graph, typename ClosedMatrix>
- inline bool
- is_path_closed(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- const ClosedMatrix& closed)
+ template < typename Graph, typename ClosedMatrix >
+ inline bool is_path_closed(const Graph& g,
+ typename graph_traits< Graph >::vertex_descriptor u,
+ typename graph_traits< Graph >::vertex_descriptor v,
+ const ClosedMatrix& closed)
{
// the path from u to v is closed if v can be found in the list
// of closed vertices associated with u.
typedef typename ClosedMatrix::const_reference Row;
Row r = closed[get(vertex_index, g, u)];
- if(find(r.begin(), r.end(), v) != r.end()) {
+ if (find(r.begin(), r.end(), v) != r.end())
+ {
return true;
}
return false;
}
- 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,
- const ClosedMatrix& 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,
+ const ClosedMatrix& m)
{
- BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
- BOOST_CONCEPT_ASSERT(( VertexIndexGraphConcept<Graph> ));
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
+ BOOST_CONCEPT_ASSERT((VertexIndexGraphConcept< Graph >));
+ typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
// get the vertices in question
- Vertex
- u = source(e, g),
- v = target(e, g);
+ Vertex u = source(e, g), v = target(e, g);
// conditions for allowing a traversal along this edge are:
// 1. the index of v must be greater than that at which the
// 2. the vertex v cannot already be in the path
// 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 indices
+ = get(vertex_index, g, p.front()) < get(vertex_index, g, v);
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>
- inline bool
- can_wrap_path(const Graph& g, const Path& p)
+ template < typename Graph, typename Path >
+ inline bool can_wrap_path(const Graph& g, const Path& p)
{
- BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;
+ BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
+ 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, but we don't quite have the
// stringent requirements that we do in can_extend_path().
- Vertex
- u = p.back(),
- v = p.front();
+ Vertex u = p.back(), v = p.front();
OutIterator i, end;
- for(boost::tie(i, end) = out_edges(u, g); i != end; ++i) {
- if((target(*i, g) == v)) {
+ for (boost::tie(i, end) = out_edges(u, g); i != end; ++i)
+ {
+ if ((target(*i, g) == v))
+ {
return true;
}
}
return false;
}
- template <typename Graph,
- typename Path,
- typename ClosedMatrix>
- inline typename graph_traits<Graph>::vertex_descriptor
- extend_path(const Graph& g,
- Path& p,
- ClosedMatrix& closed)
+ template < typename Graph, typename Path, typename ClosedMatrix >
+ inline typename graph_traits< Graph >::vertex_descriptor extend_path(
+ const Graph& g, Path& p, ClosedMatrix& closed)
{
- BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;
+ BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
+ typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
+ typedef typename graph_traits< Graph >::out_edge_iterator OutIterator;
// get the current vertex
Vertex u = p.back();
- Vertex ret = graph_traits<Graph>::null_vertex();
+ Vertex ret = graph_traits< Graph >::null_vertex();
// AdjacencyIterator i, end;
OutIterator i, end;
- for(boost::tie(i, end) = out_edges(u, g); i != end; ++i) {
+ for (boost::tie(i, end) = out_edges(u, g); i != end; ++i)
+ {
Vertex v = target(*i, g);
// if we can actually extend along this edge,
// then that's what we want to do
- if(can_extend_path(g, *i, p, closed)) {
- p.push_back(v); // add the vertex to the path
+ if (can_extend_path(g, *i, p, closed))
+ {
+ p.push_back(v); // add the vertex to the path
ret = v;
break;
}
return ret;
}
- template <typename Graph, typename Path, typename ClosedMatrix>
- inline bool
- exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
+ template < typename Graph, typename Path, typename ClosedMatrix >
+ inline bool exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
{
- BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
+ typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
// if there's more than one vertex in the path, this closes
// of some possible routes and returns true. otherwise, if there's
// only one vertex left, the vertex has been used up
- if(p.size() > 1) {
+ if (p.size() > 1)
+ {
// get the last and second to last vertices, popping the last
// vertex off the path
Vertex last, prev;
closed[get(vertex_index, g, prev)].push_back(last);
return true;
}
- else {
+ else
+ {
return false;
}
}
- template <typename Graph, typename Visitor>
- inline void
- all_cycles_from_vertex(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor v,
- Visitor vis,
- std::size_t minlen,
- std::size_t maxlen)
+ template < typename Graph, typename Visitor >
+ inline void all_cycles_from_vertex(const Graph& g,
+ typename graph_traits< Graph >::vertex_descriptor v, Visitor vis,
+ std::size_t minlen, std::size_t maxlen)
{
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef std::vector<Vertex> Path;
- BOOST_CONCEPT_ASSERT(( CycleVisitorConcept<Visitor,Path,Graph> ));
- typedef std::vector<Vertex> VertexList;
- typedef std::vector<VertexList> ClosedMatrix;
+ BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
+ typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
+ typedef std::vector< Vertex > Path;
+ BOOST_CONCEPT_ASSERT((CycleVisitorConcept< Visitor, Path, Graph >));
+ typedef std::vector< Vertex > VertexList;
+ typedef std::vector< VertexList > ClosedMatrix;
Path p;
ClosedMatrix closed(num_vertices(g), VertexList());
- Vertex null = graph_traits<Graph>::null_vertex();
+ Vertex null = graph_traits< Graph >::null_vertex();
// each path investigation starts at the ith vertex
p.push_back(v);
- while(1) {
+ while (1)
+ {
// extend the path until we've reached the end or the
// maxlen-sized cycle
Vertex j = null;
- while(((j = detail::extend_path(g, p, closed)) != null)
- && (p.size() < maxlen))
+ while (((j = detail::extend_path(g, p, closed)) != null)
+ && (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(detail::can_wrap_path(g, p) && p.size() >= minlen) {
+ if (detail::can_wrap_path(g, p) && p.size() >= minlen)
+ {
vis.cycle(p, g);
}
- if(!detail::exhaust_paths(g, p, closed)) {
+ if (!detail::exhaust_paths(g, p, closed))
+ {
break;
}
}
// Select the minimum allowable length of a cycle based on the directedness
// of the graph - 2 for directed, 3 for undirected.
- template <typename D> struct min_cycles { enum { value = 2 }; };
- template <> struct min_cycles<undirected_tag> { enum { value = 3 }; };
+ template < typename D > struct min_cycles
+ {
+ enum
+ {
+ value = 2
+ };
+ };
+ template <> struct min_cycles< undirected_tag >
+ {
+ enum
+ {
+ value = 3
+ };
+ };
} /* namespace detail */
-template <typename Graph, typename Visitor>
-inline void
-tiernan_all_cycles(const Graph& g,
- Visitor vis,
- std::size_t minlen,
- std::size_t maxlen)
+template < typename Graph, typename Visitor >
+inline void tiernan_all_cycles(
+ const Graph& g, Visitor vis, std::size_t minlen, std::size_t maxlen)
{
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
- typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
+ typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
VertexIterator i, end;
- for(boost::tie(i, end) = vertices(g); i != end; ++i) {
+ for (boost::tie(i, end) = vertices(g); i != end; ++i)
+ {
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)
+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);
+ 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)
+template < typename Graph, typename Visitor >
+inline void tiernan_all_cycles(const Graph& g, Visitor vis)
{
- 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)());
+ 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)());
}
-template <typename Graph>
-inline std::pair<std::size_t, std::size_t>
-tiernan_girth_and_circumference(const Graph& g)
+template < typename Graph >
+inline std::pair< std::size_t, std::size_t > tiernan_girth_and_circumference(
+ const Graph& g)
{
- std::size_t
- min_ = (std::numeric_limits<std::size_t>::max)(),
- max_ = 0;
+ std::size_t min_ = (std::numeric_limits< std::size_t >::max)(), max_ = 0;
tiernan_all_cycles(g, find_min_max_cycle(min_, max_));
// if this is the case, the graph is acyclic...
- if(max_ == 0) max_ = min_;
+ if (max_ == 0)
+ max_ = min_;
return std::make_pair(min_, max_);
}
-template <typename Graph>
-inline std::size_t
-tiernan_girth(const Graph& g)
-{ return tiernan_girth_and_circumference(g).first; }
+template < typename Graph > inline std::size_t tiernan_girth(const Graph& g)
+{
+ return tiernan_girth_and_circumference(g).first;
+}
-template <typename Graph>
-inline std::size_t
-tiernan_circumference(const Graph& g)
-{ return tiernan_girth_and_circumference(g).second; }
+template < typename Graph >
+inline std::size_t tiernan_circumference(const Graph& g)
+{
+ return tiernan_girth_and_circumference(g).second;
+}
} /* namespace boost */
projects / ceph.git / blobdiff