[Boost-commit] svn:boost r45616 - in sandbox/sequence_comparison: boost/sequence_comparison libs/sequence_comparison/example libs/sequence_comparison/test

From: stipe_at_[hidden]
Date: 2008-05-21 13:00:35

Author: srajko
Date: 2008-05-21 13:00:34 EDT (Wed, 21 May 2008)
New Revision: 45616
URL: http://svn.boost.org/trac/boost/changeset/45616

Log:
fixed bugs in edge_iterator and elsewhere, added edge_iterator test - edit_distance example now completes run but does not give correct result
Added:
   sandbox/sequence_comparison/libs/sequence_comparison/test/test_edge_iterator.cpp   (contents, props changed)
Text files modified: 
   sandbox/sequence_comparison/boost/sequence_comparison/edit_distance.hpp                |    79 ++++++++++++++++++++++++--------------- 
   sandbox/sequence_comparison/libs/sequence_comparison/example/edit_distance_example.cpp |    11 +++--                                   
   sandbox/sequence_comparison/libs/sequence_comparison/test/Jamfile                      |     4 +                                       
   sandbox/sequence_comparison/libs/sequence_comparison/test/test_edit_distance.cpp       |     2                                         
   4 files changed, 60 insertions(+), 36 deletions(-)

Modified: sandbox/sequence_comparison/boost/sequence_comparison/edit_distance.hpp
==============================================================================
--- sandbox/sequence_comparison/boost/sequence_comparison/edit_distance.hpp	(original)
+++ sandbox/sequence_comparison/boost/sequence_comparison/edit_distance.hpp	2008-05-21 13:00:34 EDT (Wed, 21 May 2008)
@@ -13,17 +13,19 @@
 #include <map>
 #include <utility>
 
+#include <iostream>
+
 namespace boost { namespace sequence_comparison {
 
 namespace graph {
     
     struct vertex_descriptor
-        : public std::pair<int, int>
+        : public std::pair<unsigned, unsigned>
     {
         vertex_descriptor()
         {}
-        vertex_descriptor(int first, int second)
-            : std::pair<int, int>(first, second)
+        vertex_descriptor(unsigned first, unsigned second)
+            : std::pair<unsigned, unsigned>(first, second)
         {}
         bool operator == (const vertex_descriptor &rhs) const
         {   return first == rhs.first && second == rhs.second; }
@@ -31,18 +33,25 @@
         {   return second < rhs.second || (second == rhs.second && first < rhs.first); }
         
         static inline vertex_descriptor null()
-        {   return vertex_descriptor(-1,-1); }
+        {   return vertex_descriptor((unsigned)-1,(unsigned)-1); }
     };
     
+    template<typename OStream>
+    OStream &operator << (OStream &stream, const vertex_descriptor &p)
+    {
+        stream << p.first << ", " << p.second;
+        return stream;
+    }
+    
     struct edge_descriptor
         : private std::pair<vertex_descriptor, unsigned>
     {
         edge_descriptor()
         {}
-        edge_descriptor(vertex_descriptor source, unsigned position)
-            : m_source(source), m_position(position)
+        edge_descriptor(vertex_descriptor source, unsigned direction)
+            : m_source(source), m_direction(direction)
         {
-            BOOST_ASSERT(m_position > 0 && m_position < 4);
+            BOOST_ASSERT(m_direction > 0 && m_direction < 4);
         }
         const vertex_descriptor &source() const
         {
@@ -50,18 +59,18 @@
         }
         vertex_descriptor target() const
         {
-            return vertex_descriptor(m_source.first + (m_position & 1),
-                        m_source.second + ((m_position & 2) >> 1));
+            return vertex_descriptor(m_source.first + (m_direction & 1),
+                        m_source.second + ((m_direction & 2) >> 1));
         }
-        unsigned position() const
-        {   return m_position; }
+        unsigned direction() const
+        {   return m_direction; }
         bool operator == (const edge_descriptor &rhs) const
-        {   return m_source == rhs.m_source && m_position == rhs.m_position; }
+        {   return m_source == rhs.m_source && m_direction == rhs.m_direction; }
         bool operator != (const edge_descriptor &rhs) const
         {   return !(*this == rhs); }
     private:
         vertex_descriptor m_source;
-        unsigned m_position;
+        unsigned m_direction;
     };
     
     class edge_iterator;
@@ -100,14 +109,14 @@
         }
         size_t b_size() const
         {
-            return m_end_b - m_end_b;
+            return m_end_b - m_begin_b;
         }
         unsigned weight(const edge_descriptor &edge) const
         {
-            unsigned position = edge.position();
-            BOOST_ASSERT(position > 0 && position <= 3);
+            unsigned direction = edge.direction();
+            BOOST_ASSERT(direction > 0 && direction <= 3);
             
-            if (position <= 2)
+            if (direction <= 2)
                 return 1;
             else
             {
@@ -145,14 +154,14 @@
     public:
         edge_iterator()
           : m_v(vertex_descriptor::null())
-          , m_position(0)
+          , m_direction(0)
           , m_mask(0)
         {}
 
         template<typename Graph>
         explicit edge_iterator(const vertex_descriptor &v, const Graph &g)
           : m_v(v)
-          , m_position(0)
+          , m_direction(0)
         {
             m_mask =
                 (v.first < g.a_size()) +
@@ -164,7 +173,7 @@
         template<typename Graph>
         explicit edge_iterator(const vertex_descriptor &v, const Graph &g, end)
           : m_v(v)
-          , m_position(4)
+          , m_direction(4)
         {}
 
     private:
@@ -172,27 +181,27 @@
 
         void increment()
         {
-            BOOST_ASSERT(m_position >= 0 && m_position < 4);
+            BOOST_ASSERT(m_direction >= 0 && m_direction < 4);
             do
             {
-                m_position++;
-            } while (m_position < 4 && ((m_position & m_mask) == m_position));
+                m_direction++;
+            } while (m_direction < 4 && ((m_direction & m_mask) != m_direction));
         }
         
         bool equal(edge_iterator const& other) const
         {
-            return this->m_v == other.m_v && this->m_position == other.m_position;
+            return this->m_v == other.m_v && this->m_direction == other.m_direction;
         }
 
         edge_descriptor dereference() const
         {
-            BOOST_ASSERT(m_position > 0 && m_position < 4);
+            BOOST_ASSERT(m_direction > 0 && m_direction < 4);
             
-            return edge_descriptor(m_v, m_position);             
+            return edge_descriptor(m_v, m_direction);             
         }
 
         vertex_descriptor m_v;
-        unsigned m_position;
+        unsigned m_direction;
         unsigned m_mask;
     };
     
@@ -246,7 +255,7 @@
     std::pair<vertex_iterator, vertex_iterator> vertices(Graph &graph)
     {
         return std::make_pair(vertex_iterator(vertex_descriptor(0, 0), graph)
-            , vertex_iterator(vertex_descriptor(0, graph.b_size()+2), graph));
+            , vertex_iterator(vertex_descriptor(0, graph.b_size()+1), graph));
     }
 
     // Returns the vertex descriptor for u of the edge (u,v) represented by e.
@@ -300,6 +309,7 @@
         
         value_type get(const key_type &edge) const
         {
+            std::cout << "getting weight for " << edge.direction() << ": " << m_graph.weight(edge) << std::endl;
             return m_graph.weight(edge);
         }
     private:
@@ -313,18 +323,27 @@
         typedef unsigned reference;
         typedef vertex_descriptor key_type;
         typedef boost::read_write_property_map_tag category;
-                
+        
+        distance_map(const std::string &name)
+            : m_name(name)
+        {}
+        
         value_type get(const key_type &key) const
         {
-            return m_map.find(key)->second;
+            std::map<key_type, value_type>::const_iterator found = m_map.find(key);
+            if (found != m_map.end());
+                return value_type();
+            return found->second;
         }
         
         void put(const key_type &key, value_type value)
         {
+            std::cout << m_name << ": " << key.first << ", " << key.second << " -> " << value << std::endl;
             m_map[key] = value;
         }
     private:
         std::map<key_type, value_type> m_map;
+        std::string m_name;
     };
     
     template<typename Map>

Modified: sandbox/sequence_comparison/libs/sequence_comparison/example/edit_distance_example.cpp
==============================================================================
--- sandbox/sequence_comparison/libs/sequence_comparison/example/edit_distance_example.cpp	(original)
+++ sandbox/sequence_comparison/libs/sequence_comparison/example/edit_distance_example.cpp	2008-05-21 13:00:34 EDT (Wed, 21 May 2008)
@@ -16,16 +16,19 @@
     typedef scg::weight_map<graph_type> weight_map_type;
     typedef scg::distance_map distance_map_type;
     
-    std::string s1 ("ACGT");
+    std::string s1 ("ACGOT");
     std::string s2 ("ACCT");
     graph_type graph(s1.begin(), s1.end(), s2.begin(), s2.end());
-    distance_map_type distance_map;
+    distance_map_type distance_map("Distance");
     
     boost::dag_shortest_paths(graph, graph.upper_left(),
         boost::weight_map(weight_map_type(graph))
         .distance_map(distance_map)
-        .color_map(distance_map_type())
-        .vertex_index_map(distance_map_type()));
+        .color_map(distance_map_type("Color"))
+        .vertex_index_map(distance_map_type("Predecessor")));
+        
+    std::cout << "edit distance: " << get(distance_map, scg::vertex_descriptor(graph.a_size(),graph.b_size())) << std::endl;
+
     return 0;
 };
 

Modified: sandbox/sequence_comparison/libs/sequence_comparison/test/Jamfile
==============================================================================
--- sandbox/sequence_comparison/libs/sequence_comparison/test/Jamfile	(original)
+++ sandbox/sequence_comparison/libs/sequence_comparison/test/Jamfile	2008-05-21 13:00:34 EDT (Wed, 21 May 2008)
@@ -12,4 +12,6 @@
       <define>BOOST_ALL_NO_LIB=1
     ;
 
-run test_edit_distance.cpp ;
+#run test_edit_distance.cpp ;
+run test_edge_iterator.cpp ;
+

Added: sandbox/sequence_comparison/libs/sequence_comparison/test/test_edge_iterator.cpp
==============================================================================
--- (empty file)
+++ sandbox/sequence_comparison/libs/sequence_comparison/test/test_edge_iterator.cpp	2008-05-21 13:00:34 EDT (Wed, 21 May 2008)
@@ -0,0 +1,44 @@
+// Copyright 2008 Chris Goller, Jeff Flinn, Brook Milligan and Stjepan Rajko.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/sequence_comparison/edit_distance.hpp>
+
+#include <boost/graph/dag_shortest_paths.hpp>
+#include <string>
+
+#include <boost/test/included/test_exec_monitor.hpp>
+
+namespace scg = boost::sequence_comparison::graph;
+
+template<typename Graph>
+void test_edge(const scg::edge_descriptor &e, Graph &graph, unsigned si, unsigned sj, unsigned ti, unsigned tj)
+{
+    BOOST_CHECK_EQUAL(source(e, graph), scg::vertex_descriptor(si, sj));
+    BOOST_CHECK_EQUAL(target(e, graph), scg::vertex_descriptor(ti, tj));
+}
+
+int test_main(int, char* [])
+{    
+    typedef scg::edit_distance<std::string::const_iterator,std::string::const_iterator> graph_type;
+    typedef scg::weight_map<graph_type> weight_map_type;
+    typedef scg::distance_map distance_map_type;
+    
+    std::string s1 ("ACGT");
+    std::string s2 ("ACCT");
+    graph_type graph(s1.begin(), s1.end(), s2.begin(), s2.end());
+    
+    BOOST_CHECK_EQUAL(graph.a_size(),4);
+    BOOST_CHECK_EQUAL(graph.b_size(),4);
+
+    std::pair<scg::edge_iterator, scg::edge_iterator> edges = out_edges(scg::vertex_descriptor(0,0), graph);
+    scg::edge_iterator it = edges.first;
+    test_edge(*it++, graph, 0, 0, 1, 0);
+    test_edge(*it++, graph, 0, 0, 0, 1);
+    test_edge(*it++, graph, 0, 0, 1, 1);
+    BOOST_CHECK((it == scg::edge_iterator(scg::vertex_descriptor(0,0), graph, scg::edge_iterator::end())));
+    
+    return 0;
+};
+

Modified: sandbox/sequence_comparison/libs/sequence_comparison/test/test_edit_distance.cpp
==============================================================================
--- sandbox/sequence_comparison/libs/sequence_comparison/test/test_edit_distance.cpp	(original)
+++ sandbox/sequence_comparison/libs/sequence_comparison/test/test_edit_distance.cpp	2008-05-21 13:00:34 EDT (Wed, 21 May 2008)
@@ -22,7 +22,7 @@
     std::string s2 ("ACCT");
     graph_type graph(s1.begin(), s1.end(), s2.begin(), s2.end());
     distance_map_type distance_map;
-    
+        
     boost::dag_shortest_paths(graph, graph.upper_left(),
         boost::weight_map(weight_map_type(graph))
         .distance_map(distance_map)