Subject: [Boost-commit] svn:boost r51094 - trunk/boost/graph
From: asutton_at_[hidden]
Date: 2009-02-08 09:51:58
Author: asutton
Date: 2009-02-08 09:51:58 EST (Sun, 08 Feb 2009)
New Revision: 51094
URL: http://svn.boost.org/trac/boost/changeset/51094
Log:
Importing all_cliques, all_cycles algorithms
Added:
trunk/boost/graph/bron_kerbosch_all_cliques.hpp (contents, props changed)
- copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/bron_kerbosch_all_cliques.hpp
trunk/boost/graph/tiernan_all_cycles.hpp (contents, props changed)
- copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp
Text files modified:
trunk/boost/graph/bron_kerbosch_all_cliques.hpp | 508 +++++++++++++++++---------------
trunk/boost/graph/directed_graph.hpp | 23
trunk/boost/graph/tiernan_all_cycles.hpp | 611 ++++++++++++++++++++-------------------
trunk/boost/graph/undirected_graph.hpp | 20 +
4 files changed, 612 insertions(+), 550 deletions(-)
Copied: trunk/boost/graph/bron_kerbosch_all_cliques.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/bron_kerbosch_all_cliques.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/bron_kerbosch_all_cliques.hpp (original)
+++ trunk/boost/graph/bron_kerbosch_all_cliques.hpp 2009-02-08 09:51:58 EST (Sun, 08 Feb 2009)
@@ -1,4 +1,4 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
@@ -10,274 +10,300 @@
#include <vector>
#include <deque>
-#include <boost/graph/new_graph_concepts.hpp>
+#include <boost/graph/graph_concepts.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 */
+using concepts::CliqueVisitorConcept;
+} /* namespace boost */
+#include <boost/concept/detail/concept_undef.hpp>
namespace boost
{
+// The algorithm implemented in this paper is based on the so-called
+// Algorithm 457, published as:
+//
+// @article{362367,
+// author = {Coen Bron and Joep Kerbosch},
+// title = {Algorithm 457: finding all cliques of an undirected graph},
+// journal = {Communications of the ACM},
+// volume = {16},
+// number = {9},
+// year = {1973},
+// issn = {0001-0782},
+// pages = {575--577},
+// doi = {http://doi.acm.org/10.1145/362342.362367},
+// publisher = {ACM Press},
+// address = {New York, NY, USA},
+// }
+//
+// Sort of. This implementation is adapted from the 1st version of the
+// algorithm and does not implement the candidate selection optimization
+// described as published - it could, it just doesn't yet.
+//
+// The algorithm is given as proportional to (3.14)^(n/3) power. This is
+// not the same as O(...), but based on time measures and approximation.
+//
+// Unfortunately, this implementation may be less efficient on non-
+// AdjacencyMatrix modeled graphs due to the non-constant implementation
+// of the edge(u,v,g) functions.
+//
+// TODO: It might be worthwhile to provide functionality for passing
+// a connectivity matrix to improve the efficiency of those lookups
+// when needed. This could simply be passed as a BooleanMatrix
+// s.t. edge(u,v,B) returns true or false. This could easily be
+// abstracted for adjacency matricies.
+//
+// The following paper is interesting for a number of reasons. First,
+// it lists a number of other such algorithms and second, it describes
+// a new algorithm (that does not appear to require the edge(u,v,g)
+// function and appears fairly efficient. It is probably worth investigating.
+//
+// @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}
+// ee = {http://dx.doi.org/10.1016/j.tcs.2006.06.015}
+// }
+
+/**
+ * The default clique_visitor supplies an empty visitation function.
+ */
+struct clique_visitor
+{
+ template <typename VertexSet, typename Graph>
+ void clique(const VertexSet&, Graph&)
+ { }
+};
+
+/**
+ * The max_clique_visitor records the size of the maximum clique (but not the
+ * clique itself).
+ */
+struct max_clique_visitor
+{
+ max_clique_visitor(std::size_t& max)
+ : maximum(max)
+ { }
- // The algorithm implemented in this paper is based on the so-called
- // Algorithm 457, published as:
- //
- // @article{362367,
- // author = {Coen Bron and Joep Kerbosch},
- // title = {Algorithm 457: finding all cliques of an undirected graph},
- // journal = {Communications of the ACM},
- // volume = {16},
- // number = {9},
- // year = {1973},
- // issn = {0001-0782},
- // pages = {575--577},
- // doi = {http://doi.acm.org/10.1145/362342.362367},
- // publisher = {ACM Press},
- // address = {New York, NY, USA},
- // }
- //
- // Sort of. This implementation is adapted from the 1st version of the
- // algorithm and does not implement the candidate selection optimization
- // described as published - it could, it just doesn't yet.
- //
- // The algorithm is given as proportional to (3.14)^(n/3) power. This is
- // not the same as O(...), but based on time measures and approximation.
- //
- // Unfortunately, this implementation may be less efficient on non-
- // AdjacencyMatrix modeled graphs due to the non-constant implementation
- // of the edge(u,v,g) functions.
- //
- // TODO: It might be worthwhile to provide functionality for passing
- // a connectivity matrix to improve the efficiency of those lookups
- // when needed. This could simply be passed as a BooleanMatrix
- // s.t. edge(u,v,B) returns true or false. This could easily be
- // abstracted for adjacency matricies.
- //
- // The following paper is interesting for a number of reasons. First,
- // it lists a number of other such algorithms and second, it describes
- // a new algorithm (that does not appear to require the edge(u,v,g)
- // function and appears fairly efficient. It is probably worth investigating.
- //
- // @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}
- // ee = {http://dx.doi.org/10.1016/j.tcs.2006.06.015}
- // }
-
- struct clique_visitor
+ template <typename Clique, typename Graph>
+ inline void clique(const Clique& p, const Graph& g)
{
- template <typename VertexSet, typename Graph>
- void clique(const VertexSet&, Graph&)
- { }
- };
+ maximum = std::max(maximum, p.size());
+ }
+ std::size_t& maximum;
+};
- struct max_clique_visitor
+inline max_clique_visitor find_max_clique(std::size_t& 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)
{
- max_clique_visitor(std::size_t& max)
- : maximum(max)
- { }
+ function_requires< AdjacencyMatrixConcept<Graph> >();
- template <typename Clique, typename Graph>
- inline void clique(const Clique& p, const Graph& g)
- {
- maximum = std::max(maximum, p.size());
- }
- std::size_t& maximum;
- };
+ return edge(u, v, g).second;
+ }
- inline max_clique_visitor find_max_clique(std::size_t& max)
- { return max_clique_visitor(max); }
+ 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)
+ {
+ 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
+ // change the results to a fully connected subgraph (i.e., symmetric
+ // edges between all vertices s.t., if a->b, then b->a.
+ return edge(u, v, g).second && edge(v, u, g).second;
+ }
- namespace detail
+ 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>
- 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)
- {
- function_requires< AdjacencyMatrixConcept<Graph> >();
+ function_requires< GraphConcept<Graph> >();
- return edge(u, v, g).second;
+ 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)) {
+ out.push_back(*i);
+ }
}
+ }
- 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)
- {
- 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
- // change the results to a fully connected subgraph (i.e., symmetric
- // edges between all vertices s.t., if a->b, then b->a.
- return edge(u, v, g).second && edge(v, u, g).second;
- }
+ 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)
+ {
+ function_requires< GraphConcept<Graph> >();
+ function_requires< CliqueVisitorConcept<Visitor,Clique,Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- 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)
+ // 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.
{
- 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) {
- if(is_connected_to_clique(g, v, *i, cat)) {
- out.push_back(*i);
+ 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;
}
- 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)
- {
- 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.
- {
- 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;
+ // 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.
+
+ // 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();
+ 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);
+ clique.push_back(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. If
+ // the clique is below our radar, then we won't visit it.
+ if(clique.size() >= min) {
+ vis.clique(clique, g);
}
- // 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.
-
- // 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();
- 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);
- clique.push_back(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. 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, 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.pop_back();
+ else {
+ // recurse to explore the new candidates
+ 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.pop_back();
}
}
+} /* namespace detail */
- template <typename Graph, typename Visitor>
- inline void
- 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::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, min);
- }
+template <typename Graph, typename Visitor>
+inline void
+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::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
- 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);
- }
+ Clique clique; // the first clique is an empty vertex set
+ detail::extend_clique(g, clique, cands, nots, vis, min);
+}
- 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;
- }
+// 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)
+{
+ std::size_t ret = 0;
+ bron_kerbosch_all_cliques(g, find_max_clique(ret));
+ return ret;
}
+} /* namespace boost */
+
#endif
Modified: trunk/boost/graph/directed_graph.hpp
==============================================================================
--- trunk/boost/graph/directed_graph.hpp (original)
+++ trunk/boost/graph/directed_graph.hpp 2009-02-08 09:51:58 EST (Sun, 08 Feb 2009)
@@ -16,21 +16,20 @@
struct directed_graph_tag { };
/**
-* The directed_graph class template is a simplified version of the BGL
-* adjacency list. This class is provided for ease of use, but may not
-* perform as well as custom-defined adjacency list classes. Instances of
-* this template model the BidirectionalGraph, VertexIndexGraph, and
-* EdgeIndexGraph concepts. The graph is also fully mutable, supporting
-* both insertions and removals.
-*
-* @note Special care must be taken when removing vertices or edges since
-* those operations can invalidate the numbering of vertices.
-*/
+ * The directed_graph class template is a simplified version of the BGL
+ * adjacency list. This class is provided for ease of use, but may not
+ * perform as well as custom-defined adjacency list classes. Instances of
+ * this template model the BidirectionalGraph, VertexIndexGraph, and
+ * EdgeIndexGraph concepts. The graph is also fully mutable, supporting
+ * both insertions and removals of vertices and edges.
+ *
+ * @note Special care must be taken when removing vertices or edges since
+ * those operations can invalidate the numbering of vertices.
+ */
template <
typename VertexProperty = no_property,
typename EdgeProperty = no_property,
- typename GraphProperty = no_property
->
+ typename GraphProperty = no_property>
class directed_graph
{
// Wrap the user-specified properties with an index.
Copied: trunk/boost/graph/tiernan_all_cycles.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp (original)
+++ trunk/boost/graph/tiernan_all_cycles.hpp 2009-02-08 09:51:58 EST (Sun, 08 Feb 2009)
@@ -1,4 +1,4 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
@@ -9,340 +9,365 @@
#include <vector>
-#include <boost/graph/new_graph_concepts.hpp>
+#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.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 */
+using concepts::CycleVisitorConcept;
+} /* namespace boost */
+#include <boost/concept/detail/concept_undef.hpp>
+
+
namespace boost
{
- // The implementation of this algorithm is a reproduction of the Teirnan
- // approach for directed graphs: bibtex follows
- //
- // @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},
- // 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.
- //
- // 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 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:
- //
- // @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},
- // publisher = {ACM Press},
- // address = {New York, NY, USA},
- // }
+// The implementation of this algorithm is a reproduction of the Teirnan
+// approach for directed graphs: bibtex follows
+//
+// @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},
+// 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.
+//
+// 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 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:
+//
+// @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},
+// publisher = {ACM Press},
+// address = {New York, NY, USA},
+// }
+
+/**
+ * The default cycle visitor providse an empty visit function for cycle
+ * visitors.
+ */
+struct cycle_visitor
+{
+ template <typename Path, typename Graph>
+ inline void cycle(const Path& p, const Graph& g)
+ { }
+};
+
+/**
+ * The min_max_cycle_visitor simultaneously records the minimum and maximum
+ * cycles in a graph.
+ */
+struct min_max_cycle_visitor
+{
+ min_max_cycle_visitor(std::size_t& min, std::size_t& max)
+ : minimum(min), maximum(max)
+ { }
- struct cycle_visitor
+ template <typename Path, typename Graph>
+ inline void cycle(const Path& p, const Graph& g)
{
- template <typename Path, typename Graph>
- inline void cycle(const Path& p, const Graph& g)
- { }
- };
+ std::size_t len = p.size();
+ minimum = std::min(minimum, len);
+ maximum = std::max(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); }
- struct min_max_cycle_visitor
+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)
{
- min_max_cycle_visitor(std::size_t& min, std::size_t& max)
- : minimum(min), maximum(max)
- { }
+ return (std::find(p.begin(), p.end(), v) != p.end());
+ }
- template <typename Path, typename Graph>
- inline void cycle(const Path& p, const Graph& g)
- {
- std::size_t len = p.size();
- minimum = std::min(minimum, len);
- maximum = std::max(maximum, len);
+ 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()) {
+ return true;
}
- 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); }
+ return false;
+ }
- namespace detail
+ 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>
- 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());
- }
+ function_requires< IncidenceGraphConcept<Graph> >();
+ function_requires< VertexIndexGraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // get the vertices in question
+ 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
+ // the path is rooted (p.front()).
+ // 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 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 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()) {
+ template <typename Graph, typename Path>
+ inline bool
+ can_wrap_path(const Graph& g, const Path& p)
+ {
+ function_requires< 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();
+ OutIterator i, end;
+ for(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 bool
- can_extend_path(const Graph& g,
- typename graph_traits<Graph>::edge_descriptor e,
- const Path& p,
- const ClosedMatrix& m)
- {
- function_requires< IncidenceGraphConcept<Graph> >();
- function_requires< VertexIndexGraphConcept<Graph> >();
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- // get the vertices in question
- 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
- // the path is rooted (p.front()).
- // 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 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)
- {
- function_requires< 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();
- OutIterator i, end;
- for(tie(i, end) = out_edges(u, g); i != end; ++i) {
- if((target(*i, g) == v)) {
- return true;
- }
- }
- return false;
}
+ 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)
- {
- function_requires< IncidenceGraphConcept<Graph> >();
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
- typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;
-
- // get the current vertex
- Vertex u = p.back();
- Vertex ret = graph_traits<Graph>::null_vertex();
-
- // AdjacencyIterator i, end;
- OutIterator i, end;
- for(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
- ret = v;
- break;
- }
+ template <typename Graph,
+ typename Path,
+ typename ClosedMatrix>
+ inline typename graph_traits<Graph>::vertex_descriptor
+ extend_path(const Graph& g,
+ Path& p,
+ ClosedMatrix& closed)
+ {
+ function_requires< IncidenceGraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+ typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;
+
+ // get the current vertex
+ Vertex u = p.back();
+ Vertex ret = graph_traits<Graph>::null_vertex();
+
+ // AdjacencyIterator i, end;
+ OutIterator i, end;
+ for(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
+ ret = v;
+ break;
}
- return ret;
}
+ return ret;
+ }
- template <typename Graph, typename Path, typename ClosedMatrix>
- inline bool
- exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
- {
- function_requires< GraphConcept<Graph> >();
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ template <typename Graph, typename Path, typename ClosedMatrix>
+ inline bool
+ exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
+ {
+ function_requires< 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) {
- // get the last and second to last vertices, popping the last
- // vertex off the path
- Vertex last, prev;
- last = p.back();
- p.pop_back();
- prev = p.back();
-
- // reset the closure for the last vertex of the path and
- // indicate that the last vertex in p is now closed to
- // the next-to-last vertex in p
- closed[get(vertex_index, g, last)].clear();
- closed[get(vertex_index, g, prev)].push_back(last);
- return true;
- }
- else {
- return false;
- }
+ // 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) {
+ // get the last and second to last vertices, popping the last
+ // vertex off the path
+ Vertex last, prev;
+ last = p.back();
+ p.pop_back();
+ prev = p.back();
+
+ // reset the closure for the last vertex of the path and
+ // indicate that the last vertex in p is now closed to
+ // the next-to-last vertex in p
+ closed[get(vertex_index, g, last)].clear();
+ closed[get(vertex_index, g, prev)].push_back(last);
+ return true;
}
-
- 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)
- {
- function_requires< VertexListGraphConcept<Graph> >();
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef std::vector<Vertex> Path;
- function_requires< 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();
-
- // each path investigation starts at the ith vertex
- p.push_back(v);
-
- 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))
- ; // 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) {
- vis.cycle(p, g);
- }
-
- if(!detail::exhaust_paths(g, p, closed)) {
- break;
- }
- }
+ else {
+ return false;
}
-
-
- 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,
- std::size_t minlen,
- std::size_t maxlen)
+ all_cycles_from_vertex(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ Visitor vis,
+ std::size_t minlen,
+ std::size_t maxlen)
{
function_requires< VertexListGraphConcept<Graph> >();
- typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef std::vector<Vertex> Path;
+ function_requires< 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();
+
+ // each path investigation starts at the ith vertex
+ p.push_back(v);
+
+ 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))
+ ; // 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) {
+ vis.cycle(p, g);
+ }
- VertexIterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- detail::all_cycles_from_vertex(g, *i, vis, minlen, maxlen);
+ if(!detail::exhaust_paths(g, p, closed)) {
+ break;
+ }
}
}
- 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);
- }
+ // 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 }; };
+} /* 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)
+{
+ function_requires< VertexListGraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
- 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());
+ VertexIterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ detail::all_cycles_from_vertex(g, *i, vis, minlen, maxlen);
}
+}
- 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;
- tiernan_all_cycles(g, find_min_max_cycle(min, max));
+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);
+}
- // if this is the case, the graph is acyclic...
- if(max == 0) max = min;
+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());
+}
- return std::make_pair(min, max);
- }
+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;
+ tiernan_all_cycles(g, find_min_max_cycle(min, max));
- template <typename Graph>
- inline std::size_t
- tiernan_girth(const Graph& g)
- {
- return tiernan_girth_and_circumference(g).first;
- }
+ // if this is the case, the graph is acyclic...
+ if(max == 0) max = min;
- template <typename Graph>
- inline std::size_t
- tiernan_circumference(const Graph& g)
- {
- return tiernan_girth_and_circumference(g).second;
- }
+ 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_circumference(const Graph& g)
+{ return tiernan_girth_and_circumference(g).second; }
+
+} /* namespace boost */
+
#endif
Modified: trunk/boost/graph/undirected_graph.hpp
==============================================================================
--- trunk/boost/graph/undirected_graph.hpp (original)
+++ trunk/boost/graph/undirected_graph.hpp 2009-02-08 09:51:58 EST (Sun, 08 Feb 2009)
@@ -13,11 +13,23 @@
namespace boost
{
- struct undirected_graph_tag { };
+struct undirected_graph_tag { };
- template <typename VertexProperty = no_property,
- typename EdgeProperty = no_property,
- typename GraphProperty = no_property>
+/**
+ * The undirected_graph class template is a simplified version of the BGL
+ * adjacency list. This class is provided for ease of use, but may not
+ * perform as well as custom-defined adjacency list classes. Instances of
+ * this template model the VertexIndexGraph, and EdgeIndexGraph concepts. The
+ * graph is also fully mutable, supporting both insertions and removals of
+ * vertices and edges.
+ *
+ * @note Special care must be taken when removing vertices or edges since
+ * those operations can invalidate the numbering of vertices.
+ */
+template <
+ typename VertexProperty = no_property,
+ typename EdgeProperty = no_property,
+ typename GraphProperty = no_property>
class undirected_graph
{
typedef property<vertex_index_t, unsigned, VertexProperty> vertex_property;