[Boost-commit] svn:boost r7465

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());