From: stipe_at_[hidden]
Date: 2008-05-09 02:47:27
Author: srajko
Date: 2008-05-09 02:47:23 EDT (Fri, 09 May 2008)
New Revision: 45240
URL: http://svn.boost.org/trac/boost/changeset/45240
Log:
initial edit_distance commit
Added:
sandbox/sequence_comparison/boost/sequence_comparison/edit_distance.hpp (contents, props changed)
sandbox/sequence_comparison/libs/sequence_comparison/example/edit_distance_example.cpp (contents, props changed)
sandbox/sequence_comparison/libs/sequence_comparison/test/test_edit_distance.cpp (contents, props changed)
Text files modified:
sandbox/sequence_comparison/libs/sequence_comparison/example/Jamfile | 2 +-
sandbox/sequence_comparison/libs/sequence_comparison/test/Jamfile | 3 +--
2 files changed, 2 insertions(+), 3 deletions(-)
Added: sandbox/sequence_comparison/boost/sequence_comparison/edit_distance.hpp
==============================================================================
--- (empty file)
+++ sandbox/sequence_comparison/boost/sequence_comparison/edit_distance.hpp 2008-05-09 02:47:23 EDT (Fri, 09 May 2008)
@@ -0,0 +1,347 @@
+// 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)
+
+#ifndef BOOST_SEQUENCE_COMPARISON_EDIT_DISTANCE_HPP
+#define BOOST_SEQUENCE_COMPARISON_EDIT_DISTANCE_HPP
+
+#include <boost/assert.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/iterator/iterator_facade.hpp>
+#include <map>
+#include <utility>
+
+namespace boost { namespace sequence_comparison {
+
+namespace graph {
+
+ struct vertex_descriptor
+ : public std::pair<int, int>
+ {
+ vertex_descriptor()
+ {}
+ vertex_descriptor(int first, int second)
+ : std::pair<int, int>(first, second)
+ {}
+ bool operator == (const vertex_descriptor &rhs) const
+ { return first == rhs.first && second == rhs.second; }
+ bool operator < (const vertex_descriptor &rhs) const
+ { return second < rhs.second || (second == rhs.second && first < rhs.first); }
+
+ static inline vertex_descriptor null()
+ { return vertex_descriptor(-1,-1); }
+ };
+
+ struct edge_descriptor
+ : private std::pair<vertex_descriptor, unsigned>
+ {
+ edge_descriptor()
+ {}
+ edge_descriptor(vertex_descriptor source, unsigned position)
+ : m_source(source), m_position(position)
+ {
+ BOOST_ASSERT(m_position > 0 && m_position < 4);
+ }
+ const vertex_descriptor &source() const
+ {
+ return m_source;
+ }
+ vertex_descriptor target() const
+ {
+ return vertex_descriptor(m_source.first + (m_position & 1),
+ m_source.second + ((m_position & 2) >> 1));
+ }
+ unsigned position() const
+ { return m_position; }
+ bool operator == (const edge_descriptor &rhs) const
+ { return m_source == rhs.m_source && m_position == rhs.m_position; }
+ bool operator != (const edge_descriptor &rhs) const
+ { return !(*this == rhs); }
+ private:
+ vertex_descriptor m_source;
+ unsigned m_position;
+ };
+
+ class edge_iterator;
+ class vertex_iterator;
+
+ template<typename RandomAccessIteratorA, typename RandomAccessIteratorB>
+ class edit_distance
+ {
+ public:
+ typedef graph::vertex_descriptor vertex_descriptor;
+ typedef graph::edge_descriptor edge_descriptor;
+ typedef void adjacency_iterator;
+ typedef graph::edge_iterator out_edge_iterator;
+ typedef void in_edge_iterator;
+ typedef graph::vertex_iterator vertex_iterator;
+ typedef void edge_iterator;
+
+ typedef boost::directed_tag directed_category;
+ typedef boost::disallow_parallel_edge_tag edge_parallel_category;
+ typedef boost::incidence_graph_tag traversal_category;
+
+ typedef size_t vertices_size_type;
+ typedef void edges_size_type;
+ typedef unsigned degree_size_type;
+
+ static inline vertex_descriptor null_vertex()
+ { return vertex_descriptor::null(); }
+
+ edit_distance(RandomAccessIteratorA begin_a, RandomAccessIteratorA end_a,
+ RandomAccessIteratorB begin_b, RandomAccessIteratorB end_b)
+ : m_begin_a(begin_a), m_end_a(end_a), m_begin_b(begin_b), m_end_b(end_b)
+ {}
+ size_t a_size() const
+ {
+ return m_end_a - m_begin_a;
+ }
+ size_t b_size() const
+ {
+ return m_end_b - m_end_b;
+ }
+ unsigned weight(const edge_descriptor &edge) const
+ {
+ unsigned position = edge.position();
+ BOOST_ASSERT(position > 0 && position <= 3);
+
+ if (position <= 2)
+ return 1;
+ else
+ {
+ std::pair<int, int> coords = edge.source();
+ return m_begin_a[coords.first] != m_begin_b[coords.second];
+ }
+ }
+ vertex_descriptor upper_left() const
+ {
+ return vertex_descriptor(0,0);
+ }
+ vertex_descriptor lower_right() const
+ {
+ return vertex_descriptor(a_size(), b_size());
+ }
+ private:
+ RandomAccessIteratorA m_begin_a, m_end_a;
+ RandomAccessIteratorA m_begin_b, m_end_b;
+ };
+
+ template<typename Graph>
+ size_t num_vertices(const Graph &graph)
+ {
+ return (graph.a_size() + 1) * (graph.b_size()+1);
+ }
+
+ class edge_iterator
+ : public boost::iterator_facade<
+ edge_iterator
+ , edge_descriptor
+ , boost::forward_traversal_tag
+ , edge_descriptor
+ >
+ {
+ public:
+ edge_iterator()
+ : m_v(vertex_descriptor::null())
+ , m_position(0)
+ , m_mask(0)
+ {}
+
+ template<typename Graph>
+ explicit edge_iterator(const vertex_descriptor &v, const Graph &g)
+ : m_v(v)
+ , m_position(0)
+ {
+ m_mask =
+ (v.first < g.a_size()) +
+ ((v.second < g.b_size()) << 1);
+ increment();
+ }
+
+ struct end{};
+ template<typename Graph>
+ explicit edge_iterator(const vertex_descriptor &v, const Graph &g, end)
+ : m_v(v)
+ , m_position(4)
+ {}
+
+ private:
+ friend class boost::iterator_core_access;
+
+ void increment()
+ {
+ BOOST_ASSERT(m_position >= 0 && m_position < 4);
+ do
+ {
+ m_position++;
+ } while (m_position < 4 && ((m_position & m_mask) == m_position));
+ }
+
+ bool equal(edge_iterator const& other) const
+ {
+ return this->m_v == other.m_v && this->m_position == other.m_position;
+ }
+
+ edge_descriptor dereference() const
+ {
+ BOOST_ASSERT(m_position > 0 && m_position < 4);
+
+ return edge_descriptor(m_v, m_position);
+ }
+
+ vertex_descriptor m_v;
+ unsigned m_position;
+ unsigned m_mask;
+ };
+
+ class vertex_iterator
+ : public boost::iterator_facade<
+ vertex_iterator
+ , vertex_descriptor
+ , boost::forward_traversal_tag
+ , const vertex_descriptor &
+ >
+ {
+ public:
+ vertex_iterator()
+ : m_v(vertex_descriptor::null())
+ , m_row_max(0)
+ {}
+
+ template<typename Graph>
+ explicit vertex_iterator(const vertex_descriptor &v, const Graph &g)
+ : m_v(v)
+ , m_row_max(g.a_size())
+ {}
+
+ private:
+ friend class boost::iterator_core_access;
+
+ void increment()
+ {
+ if(++m_v.first > m_row_max)
+ {
+ m_v.first = 0;
+ m_v.second++;
+ }
+ }
+
+ bool equal(vertex_iterator const& other) const
+ {
+ return this->m_v == other.m_v;
+ }
+
+ const vertex_descriptor &dereference() const
+ {
+ return m_v;
+ }
+
+ vertex_descriptor m_v;
+ size_t m_row_max;
+ };
+
+ template<typename Graph>
+ 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));
+ }
+
+ // Returns the vertex descriptor for u of the edge (u,v) represented by e.
+ // Return type: vertex_descriptor
+ template<typename Graph>
+ vertex_descriptor source(const edge_descriptor &e, const Graph &g)
+ {
+ return e.source();
+ }
+
+ // Returns the vertex descriptor for v of the edge (u,v) represented by e.
+ // Return type: vertex_descriptor
+ template<typename Graph>
+ vertex_descriptor target(const edge_descriptor &e, const Graph &g)
+ {
+ return e.target();
+ }
+
+ // Returns an iterator-range providing access to the out-edges of vertex u in graph g.
+ // The source vertex of an edge obtained via an out edge iterator is guaranteed
+ // (for both directed and undirected graphs) to be the vertex u used in the call to
+ // out_edges(u, g) and the target vertex must the a vertex adjacent to u.
+ // Return type: std::pair<out_edge_iterator, out_edge_iterator>
+ template<typename Graph>
+ std::pair<edge_iterator, edge_iterator> out_edges(const vertex_descriptor &u, const Graph &g)
+ {
+ return std::make_pair(edge_iterator(u, g), edge_iterator(u, g, edge_iterator::end()));
+ }
+
+ template<typename Graph>
+ unsigned out_degree(const vertex_descriptor &u, const Graph &g)
+ {
+ bool not_right_edge = u.first < g.a_size();
+ bool not_bottom_edge = u.second < g.b_size();
+ return not_right_edge + not_bottom_edge + (not_right_edge && not_bottom_edge);
+ }
+
+ template<typename Graph>
+ class weight_map
+ {
+ public:
+ typedef unsigned value_type;
+ typedef unsigned reference;
+// typedef unsigned reference_type;
+ typedef edge_descriptor key_type;
+ typedef boost::readable_property_map_tag category;
+
+ weight_map(const Graph &g)
+ : m_graph(g)
+ {}
+
+ value_type get(const key_type &edge) const
+ {
+ return m_graph.weight(edge);
+ }
+ private:
+ const Graph &m_graph;
+ };
+
+ class distance_map
+ {
+ public:
+ typedef unsigned value_type;
+ typedef unsigned reference;
+ typedef vertex_descriptor key_type;
+ typedef boost::read_write_property_map_tag category;
+
+ value_type get(const key_type &key) const
+ {
+ return m_map.find(key)->second;
+ }
+
+ void put(const key_type &key, value_type value)
+ {
+ m_map[key] = value;
+ }
+ private:
+ std::map<key_type, value_type> m_map;
+ };
+
+ template<typename Map>
+ unsigned get(const Map &map, const typename Map::key_type &key)
+ {
+ return map.get(key);
+ }
+
+ template<typename Map>
+ void put(Map &map, const typename Map::key_type &key, const typename Map::value_type &value)
+ {
+ map.put(key, value);
+ }
+}
+
+} // namespace sequence_comparison
+}
+
+#endif
+
Modified: sandbox/sequence_comparison/libs/sequence_comparison/example/Jamfile
==============================================================================
--- sandbox/sequence_comparison/libs/sequence_comparison/example/Jamfile (original)
+++ sandbox/sequence_comparison/libs/sequence_comparison/example/Jamfile 2008-05-09 02:47:23 EDT (Fri, 09 May 2008)
@@ -10,4 +10,4 @@
<define>BOOST_ALL_NO_LIB=1
;
-exe example : example.cpp ;
+exe edit_distance_example : edit_distance_example.cpp ;
Added: sandbox/sequence_comparison/libs/sequence_comparison/example/edit_distance_example.cpp
==============================================================================
--- (empty file)
+++ sandbox/sequence_comparison/libs/sequence_comparison/example/edit_distance_example.cpp 2008-05-09 02:47:23 EDT (Fri, 09 May 2008)
@@ -0,0 +1,31 @@
+// 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>
+
+int main(int, char* [])
+{
+ namespace scg = boost::sequence_comparison::graph;
+
+ 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());
+ distance_map_type distance_map;
+
+ 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()));
+ 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-09 02:47:23 EDT (Fri, 09 May 2008)
@@ -12,5 +12,4 @@
<define>BOOST_ALL_NO_LIB=1
;
-run test_nothing.cpp ;
-run test_nothing_n.cpp ;
+run test_edit_distance.cpp ;
Added: sandbox/sequence_comparison/libs/sequence_comparison/test/test_edit_distance.cpp
==============================================================================
--- (empty file)
+++ sandbox/sequence_comparison/libs/sequence_comparison/test/test_edit_distance.cpp 2008-05-09 02:47:23 EDT (Fri, 09 May 2008)
@@ -0,0 +1,33 @@
+// 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>
+
+int test_main(int, char* [])
+{
+ namespace scg = boost::sequence_comparison::graph;
+
+ 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());
+ distance_map_type distance_map;
+
+ 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()));
+ return 0;
+};
+