/* Directed acyclic word graph. */
#ifndef DAWG_H
#define DAWG_H 1
#include "FMIndex.h"
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <algorithm> // for distance
#include <cassert>
#include <utility>
using boost::graph_traits;
/** An FM-index is a representation of a DAWG. */
typedef FMIndex DAWG;
// Graph
namespace boost {
template <>
struct graph_traits<DAWG> {
typedef DAWG::size_type size_type;
// Graph
typedef std::pair<size_type, size_type> vertex_descriptor;
typedef boost::directed_tag directed_category;
struct traversal_category : boost::incidence_graph_tag { };
typedef boost::disallow_parallel_edge_tag edge_parallel_category;
// IncidenceGraph
typedef std::pair<vertex_descriptor, vertex_descriptor>
edge_descriptor;
typedef unsigned degree_size_type;
// VertexListGraph
/** Vertex iterator. */
struct vertex_iterator : public vertex_descriptor {
vertex_iterator() : vertex_descriptor(0, 0) { }
vertex_iterator(size_type l, size_type u)
: vertex_descriptor(l, u) { }
vertex_descriptor operator*() const { return *this; };
};
// IncidenceGraph
/** Out edge iterator. */
class out_edge_iterator
: public std::iterator<std::input_iterator_tag, edge_descriptor>
{
public:
out_edge_iterator() : m_g(NULL), m_u(), m_v(), m_i(0) { }
out_edge_iterator(const DAWG& g, vertex_descriptor u,
degree_size_type i)
: m_g(&g), m_u(u), m_v(), m_i(i)
{
next();
}
edge_descriptor operator*() const
{
return edge_descriptor(m_u, m_v);
}
bool operator==(const out_edge_iterator& it) const
{
return m_g == it.m_g && m_u == it.m_u && m_i == it.m_i;
}
bool operator!=(const out_edge_iterator& it) const
{
return !(*this == it);
}
out_edge_iterator& operator++()
{
assert(m_i < m_g->alphabetSize());
++m_i;
next();
return *this;
}
out_edge_iterator operator++(int)
{
out_edge_iterator it = *this;
++*this;
return it;
}
private:
/** Skip to the next edge that is present. */
void next()
{
for (; m_i < m_g->alphabetSize(); m_i++) {
m_v = vertex_descriptor(
m_g->update(m_u.first, m_i),
m_g->update(m_u.second, m_i));
if (m_v.first < m_v.second)
break;
}
}
const DAWG* m_g;
vertex_descriptor m_u;
vertex_descriptor m_v;
degree_size_type m_i;
}; // out_edge_iterator
}; // graph_traits<DAWG>
} // namespace boost
// IncidenceGraph
static inline
std::pair<
graph_traits<DAWG>::out_edge_iterator,
graph_traits<DAWG>::out_edge_iterator>
out_edges(
graph_traits<DAWG>::vertex_descriptor u,
const DAWG& g)
{
typedef graph_traits<DAWG>::out_edge_iterator Eit;
return std::pair<Eit, Eit>(
Eit(g, u, 0),
Eit(g, u, g.alphabetSize()));
}
static inline
graph_traits<DAWG>::degree_size_type
out_degree(
graph_traits<DAWG>::vertex_descriptor u,
const DAWG& g)
{
typedef graph_traits<DAWG>::out_edge_iterator Eit;
std::pair<Eit, Eit> it = out_edges(u, g);
return std::distance(it.first, it.second);
}
// VertexListGraph
static inline
std::pair<graph_traits<DAWG>::vertex_iterator,
graph_traits<DAWG>::vertex_iterator>
vertices(const DAWG& g)
{
typedef graph_traits<DAWG>::vertex_iterator Vit;
return std::pair<Vit, Vit>(Vit(0, g.size() + 1), Vit());
}
// PropertyGraph
static inline
DAWG::value_type
get(boost::vertex_name_t,
const DAWG& g,
graph_traits<DAWG>::vertex_descriptor u)
{
assert(u.first < u.second);
return u.first == 0 ? '$' : g.symbolAt(u.first);
}
static inline
DAWG::value_type
get(boost::edge_name_t,
const DAWG& g,
graph_traits<DAWG>::edge_descriptor e)
{
graph_traits<DAWG>::vertex_descriptor v = target(e, g);
assert(v.first < v.second);
return g.symbolAt(v.first);
}
#endif