From: asutton_at_[hidden]
Date: 2007-07-18 07:37:16
Author: asutton
Date: 2007-07-18 07:37:13 EDT (Wed, 18 Jul 2007)
New Revision: 7465
URL: http://svn.boost.org/trac/boost/changeset/7465
Log:
Fixed cycle algorithm.
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/cycle.hpp | 219 +++++++++++++++++++++++----------------
sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp | 90 +++++++++++-----
sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp | 7
3 files changed, 195 insertions(+), 121 deletions(-)
Modified: sandbox/SOC/2007/graphs/boost/graph/cycle.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/cycle.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/cycle.hpp 2007-07-18 07:37:13 EDT (Wed, 18 Jul 2007)
@@ -92,20 +92,6 @@
{ }
};
- struct cycle_counter
- : public cycle_visitor
- {
- cycle_counter(std::size_t& num)
- : m_num(num)
- { }
-
- template <class Path, class Graph>
- inline void cycle(const Path& p, Graph& g)
- { ++m_num; }
-
- size_t& m_num;
- };
-
namespace detail
{
template <typename Graph, typename Path>
@@ -142,48 +128,108 @@
const Path& p,
const ClosedMatrix& m)
{
- // for undirected graphs, we're actually going to follow the
- // original algorithm and disallow back-tracking over the
- // undirected edge.
- return get(vertex_index, g, v) < get(vertex_index, g, u) ||
+ // 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 typename graph_traits<Graph>::vertex_descriptor
- extend_path(const Graph& g, Path& p, ClosedMatrix& closed)
+ 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)
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
- // basically, p is a sequence of vertex descriptors.
- // we want to find an adjacent vertex that the path
- // can extend over.
+ // 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_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)
+ {
+ 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.
+ 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 typename graph_traits<Graph>::vertex_descriptor
+ extend_path(const Graph& g,
+ Path& p,
+ ClosedMatrix& closed)
+ {
+ 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;
- for(tie(i, end) = adjacent_vertices(u, g); i != end; ++i) {
- Vertex v = *i;
- if(ignore_vertex(g, u, v, p, closed)) {
- continue;
+ // 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;
}
-
- // if we get here, we've actually satisfied the loop
- // so we can just break and return
- p.push_back(v);
- ret = v;
- break;
}
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;
@@ -209,52 +255,50 @@
return false;
}
}
- }
- // TODO: I may need to templatize the path type - it would add a little extra
- // flexibility, but I'm not certain its a great idea.
+ template <typename Graph, typename Visitor>
+ inline void
+ visit_cycles_at_vertex(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ Visitor vis,
+ std::size_t maxlen,
+ std::size_t minlen)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
- template <typename Graph, typename Visitor>
- inline void
- visit_cycles(const Graph& g,
- Visitor vis,
- std::size_t maxlen = std::numeric_limits<std::size_t>::max(),
- std::size_t minlen = 3)
- {
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
- typedef std::vector<Vertex> Path;
- typedef std::vector<Vertex> VertexList;
- typedef std::vector<VertexList> ClosedMatrix;
-
- // closed contains the list of vertices that are "closed" to a vertex. this
- // is a kind of strange half-mapped matrix. rows are indexed by vertex, but
- // the columns are not - they simply store the list of vertices that are
- // closed to the vertex represented by the row.
+ typedef std::vector<Vertex> Path;
+ typedef std::vector<Vertex> VertexList;
+ typedef std::vector<VertexList> ClosedMatrix;
- const Vertex null = graph_traits<Graph>::null_vertex();
+ // 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.
- VertexIterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
+ const Vertex null = graph_traits<Graph>::null_vertex();
+
+ // The path is the sequence of vertices
Path p;
ClosedMatrix closed(num_vertices(g), VertexList());
- p.push_back(*i);
- vis.start_vertex(*i, g);
+ // each path investigation starts at the ith vertex
+ p.push_back(v);
+ vis.start_vertex(v, g);
while(1) {
- // extend the path until we've reached the end or the maximum
- // sized cycle
+ // 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))
+ && (p.size() < maxlen))
; // empty loop
- // at this point, we need to see if there's a cycle
- if(edge(p.back(), p.front(), g).second) {
- if(p.size() >= minlen) {
- vis.cycle(p, g);
- }
+ // 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) {
+ vis.cycle(p, g);
}
if(!detail::exhaust_paths(g, p, closed)) {
@@ -262,33 +306,26 @@
}
}
- vis.finish_vertex(*i, g);
+ vis.finish_vertex(v, g);
}
}
- template <typename Graph>
- inline size_t
- count_cycles(const Graph& g,
- std::size_t maxlen = std::numeric_limits<std::size_t>::max(),
- std::size_t minlen = 3)
- {
- size_t ret = 0;
- visit_triangles(g, cycle_counter(ret), maxlen, minlen);
- return ret;
- }
+ // TODO: I may need to templatize the path type - it would add a little extra
+ // flexibility, but I'm not certain its a great idea.
template <typename Graph, typename Visitor>
inline void
- visit_triangles(const Graph& g, Visitor vis)
- { visit_cycles(g, vis, 3, 3); }
-
- template <typename Graph>
- inline size_t
- count_triangles(const Graph& g)
+ visit_cycles(const Graph& g,
+ Visitor vis,
+ std::size_t maxlen = std::numeric_limits<std::size_t>::max(),
+ std::size_t minlen = 2)
{
- size_t ret = 0;
- visit_triangles(g, cycle_counter(ret));
- return ret;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+
+ VertexIterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ detail::visit_cycles_at_vertex(g, *i, vis, maxlen, minlen);
+ }
}
}
Modified: sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp 2007-07-18 07:37:13 EDT (Wed, 18 Jul 2007)
@@ -20,21 +20,60 @@
using namespace std;
using namespace boost;
-using namespace __cxxabiv1;
-struct cycle_printer : public cycle_visitor
+template <typename OStream>
+struct cycle_printer
+ : public cycle_visitor
{
+ cycle_printer(OStream& os)
+ : m_os(os)
+ { }
+
template <typename Path, typename Graph>
void cycle(const Path& p, const Graph& g)
{
- cout << "path: ";
- for(typename Path::const_iterator i = p.begin(); i != p.end(); ++i) {
- cout << get(vertex_index, g, *i) << " ";
+ m_os << "cycle: ";
+ typename Path::const_iterator i, end = p.end();
+ for(i = p.begin(); i != end; ++i) {
+ m_os << get(vertex_index, g, *i) << " ";
}
- cout << "\n";
- };
+ m_os << "\n";
+ }
+
+ OStream& m_os;
};
+template <typename SizeType>
+struct cycle_counter
+ : public cycle_visitor
+{
+ cycle_counter(SizeType& count)
+ : m_count(count)
+ { }
+
+ template <typename Path, typename Graph>
+ void cycle(const Path& p, const Graph& g)
+ {
+ ++m_count;
+ }
+
+ SizeType& m_count;
+};
+
+template <typename Stream>
+inline cycle_printer<Stream>
+print_cycles(Stream& os)
+{
+ return cycle_printer<Stream>(os);
+}
+
+template <typename SizeType>
+inline cycle_counter<SizeType>
+count_cycles(SizeType& count)
+{
+ return cycle_counter<SizeType>(count);
+}
+
template <typename Graph>
void build_graph(Graph& g)
{
@@ -46,7 +85,6 @@
// add some vertices
for(size_t i = 0; i < N; ++i) {
- // v[i] = add_vertex(g);
v[i] = add_vertex(g);
}
@@ -60,35 +98,31 @@
add_edge(v[4], v[0], g);
};
-void test_1()
+template <typename Graph>
+void test()
{
- typedef directed_graph<> Graph;
-
Graph g;
// build_graph(g);
- make_prism_graph(g, 4, 3, with_bidirected_cycle(), with_bidirected_spokes());
- // make_complete_graph(g, 4);
+ // make_prism_graph(g, 3, 2);
+ make_complete_graph(g, 4);
- visit_cycles(g, cycle_printer());
- std::cout << "number of triangles: " << count_triangles(g) << "\n";
-}
+ size_t count = 0;
+ visit_cycles(g, count_cycles(count));
+ std::cout << "number of cycles: " << count << "\n";
-void test_2()
-{
- typedef undirected_graph<> Graph;
-
- Graph g;
- // build_graph(g);
- make_prism_graph(g, 3, 2);
-
- visit_cycles(g, cycle_printer());
- std::cout << "number of triangles: " << count_triangles(g) << "\n";
+ visit_cycles(g, print_cycles(cout));
}
int
main(int argc, char *argv[])
{
- test_1();
- // test_2();
+ typedef undirected_graph<> Graph;
+ typedef directed_graph<> DiGraph;
+
+ std::cout << "*** undirected ***\n";
+ test<Graph>();
+
+ std::cout << "*** directed ***\n";
+ test<DiGraph>();
}
Modified: sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp 2007-07-18 07:37:13 EDT (Wed, 18 Jul 2007)
@@ -27,7 +27,7 @@
using namespace boost;
static const int N = 3;
-static const int K = 3;
+static const int K = 2;
template <class Graph>
void test_path()
@@ -148,6 +148,9 @@
typedef undirected_graph<> Graph;
typedef directed_graph<> DiGraph;
+ with_clockwise_cycle clock;
+ with_bidirected_spokes spokes;
+
/*
test_complete<Graph>();
test_path<Graph>();
@@ -158,7 +161,7 @@
*/
// test_web<Graph>();
- test_prism<DiGraph>(with_clockwise_cycle(), with_bidirected_spokes());
+ test_prism<DiGraph>(clock, spokes);
/*
test_path<DiGraph>(with_forward_edges());