#ifndef CONTIGGRAPH_H #define CONTIGGRAPH_H 1 #include "Common/ContigID.h" #include "Graph/Properties.h" #include #include #include using boost::graph_traits; /** A contig graph is a directed graph with the property that * the edge (u,v) implies the existence of the edge (~v,~u). */ template class ContigGraph : public G { public: typedef G base_type; // Graph typedef typename graph_traits::vertex_descriptor vertex_descriptor; typedef typename graph_traits::directed_category directed_category; typedef typename graph_traits::traversal_category traversal_category; typedef typename graph_traits::edge_parallel_category edge_parallel_category; // IncidenceGraph typedef typename graph_traits::edge_descriptor edge_descriptor; typedef typename graph_traits::out_edge_iterator out_edge_iterator; typedef typename graph_traits::degree_size_type degree_size_type; // AdjacencyGraph typedef typename graph_traits::adjacency_iterator adjacency_iterator; // VertexListGraph typedef typename graph_traits::vertex_iterator vertex_iterator; typedef typename graph_traits::vertices_size_type vertices_size_type; // EdgeListGraph typedef typename graph_traits::edge_iterator edge_iterator; typedef typename graph_traits::edges_size_type edges_size_type; // VertexMutablePropertyGraph typedef typename vertex_property::type vertex_property_type; // EdgeMutablePropertyGraph typedef typename edge_property::type edge_property_type; // BidirectionalGraph /** Iterate through the in-edges. */ class in_edge_iterator : public std::iterator { /** Return the complement (~v, ~u) of the edge (u, v). */ static edge_descriptor complement(const edge_descriptor& e) { return std::pair( e.second ^ 1, e.first ^ 1); } public: in_edge_iterator() { } in_edge_iterator(typename graph_traits::out_edge_iterator it) : m_it(it) { } edge_descriptor operator*() const { return complement(*m_it); } bool operator==(const in_edge_iterator& it) const { return m_it == it.m_it; } bool operator!=(const in_edge_iterator& it) const { return m_it != it.m_it; } in_edge_iterator& operator++() { ++m_it; return *this; } in_edge_iterator operator++(int) { in_edge_iterator it = *this; ++*this; return it; } private: out_edge_iterator m_it; }; public: /** Construct an empty contig graph. */ ContigGraph() { } /** Construct a contig graph with n vertices. The underlying * directed graph has two vertices for each contig. */ ContigGraph(vertices_size_type n) : G(2 * n) { } /** Return the in degree of vertex v. */ degree_size_type in_degree(vertex_descriptor v) const { return G::out_degree(get(vertex_complement, *this, v)); } /** Remove all out edges from vertex u. */ void clear_out_edges(vertex_descriptor u) { std::pair adj = G::adjacent_vertices(u); for (adjacency_iterator v = adj.first; v != adj.second; ++v) { vertex_descriptor uc = get(vertex_complement, *this, u); vertex_descriptor vc = get(vertex_complement, *this, *v); if (vc == u) { // When ~v == u, removing (~v,~u), which is (u,~u), // would invalidate our iterator. This edge will be // removed by clear_out_edges. } else G::remove_edge(vc, uc); } G::clear_out_edges(u); } /** Remove all in edges from vertex v. */ void clear_in_edges(vertex_descriptor v) { clear_out_edges(get(vertex_complement, *this, v)); } /** Remove all edges to and from vertex v. */ void clear_vertex(vertex_descriptor v) { clear_out_edges(v); clear_in_edges(v); } /** Add a vertex to this graph. */ vertex_descriptor add_vertex( const vertex_property_type& data = vertex_property_type()) { vertex_descriptor v = G::add_vertex(data); G::add_vertex(data); return v; } /** Remove vertex v from this graph. It is assumed that there * are no edges to or from vertex v. It is best to call * clear_vertex before remove_vertex. */ void remove_vertex(vertex_descriptor v) { G::remove_vertex(v); G::remove_vertex(get(vertex_complement, *this, v)); } /** Add edge (u,v) to this graph. */ std::pair add_edge(vertex_descriptor u, vertex_descriptor v) { vertex_descriptor uc = get(vertex_complement, *this, u); vertex_descriptor vc = get(vertex_complement, *this, v); std::pair e = G::add_edge(u, v); if (u != vc) G::add_edge(vc, uc); return e; } /** Add edge (u,v) to this graph. */ std::pair add_edge(vertex_descriptor u, vertex_descriptor v, const edge_property_type& ep) { vertex_descriptor uc = get(vertex_complement, *this, u); vertex_descriptor vc = get(vertex_complement, *this, v); std::pair e = G::add_edge(u, v, ep); if (u != vc) G::add_edge(vc, uc, ep); return e; } /** Remove the edge (u,v) from this graph. */ void remove_edge(vertex_descriptor u, vertex_descriptor v) { vertex_descriptor uc = get(vertex_complement, *this, u); vertex_descriptor vc = get(vertex_complement, *this, v); G::remove_edge(u, v); if (u != vc) G::remove_edge(vc, uc); } /** Remove the edge e from this graph. */ void remove_edge(edge_descriptor e) { remove_edge(source(e, *this), target(e, *this)); } }; namespace std { template inline void swap(ContigGraph& a, ContigGraph& b) { a.swap(b); } } // IncidenceGraph template std::pair< typename ContigGraph::out_edge_iterator, typename ContigGraph::out_edge_iterator> out_edges( typename ContigGraph::vertex_descriptor u, const ContigGraph& g) { return g.out_edges(u); } template typename ContigGraph::degree_size_type out_degree( typename ContigGraph::vertex_descriptor u, const ContigGraph& g) { return g.out_degree(u); } // BidirectionalGraph template std::pair< typename ContigGraph::in_edge_iterator, typename ContigGraph::in_edge_iterator> in_edges( typename ContigGraph::vertex_descriptor u, const ContigGraph& g) { typedef typename ContigGraph::in_edge_iterator in_edge_iterator; typedef typename ContigGraph::out_edge_iterator out_edge_iterator; std::pair it = out_edges(get(vertex_complement, g, u), g); return std::pair( it.first, it.second); } template typename ContigGraph::degree_size_type in_degree( typename ContigGraph::vertex_descriptor u, const ContigGraph& g) { return g.in_degree(u); } // AdjacencyGraph template std::pair< typename ContigGraph::adjacency_iterator, typename ContigGraph::adjacency_iterator> adjacent_vertices( typename ContigGraph::vertex_descriptor u, const ContigGraph& g) { return g.adjacent_vertices(u); } // VertexListGraph template typename ContigGraph::vertices_size_type num_vertices(const ContigGraph& g) { return g.num_vertices(); } template std::pair::vertex_iterator, typename ContigGraph::vertex_iterator> vertices(const ContigGraph& g) { return g.vertices(); } // EdgeListGraph template typename ContigGraph::edges_size_type num_edges(const ContigGraph& g) { return g.num_edges(); } template std::pair::edge_iterator, typename ContigGraph::edge_iterator> edges(const ContigGraph& g) { return g.edges(); } // AdjacencyMatrix template std::pair::edge_descriptor, bool> edge( typename ContigGraph::vertex_descriptor u, typename ContigGraph::vertex_descriptor v, const ContigGraph& g) { return g.edge(u, v); } // VertexMutableGraph template typename ContigGraph::vertex_descriptor add_vertex(ContigGraph& g) { return g.add_vertex(); } template void remove_vertex( typename ContigGraph::vertex_descriptor u, ContigGraph& g) { g.remove_vertex(u); } // EdgeMutableGraph template void clear_vertex( typename ContigGraph::vertex_descriptor u, ContigGraph& g) { g.clear_vertex(u); } template std::pair::edge_descriptor, bool> add_edge( typename ContigGraph::vertex_descriptor u, typename ContigGraph::vertex_descriptor v, ContigGraph& g) { return g.add_edge(u, v); } template void remove_edge( typename ContigGraph::vertex_descriptor u, typename ContigGraph::vertex_descriptor v, ContigGraph& g) { return g.remove_edge(u, v); } template void remove_edge( typename ContigGraph::edge_descriptor e, ContigGraph& g) { g.remove_edge(e); } // MutableIncidenceGraph template void clear_out_edges( typename ContigGraph::vertex_descriptor u, ContigGraph& g) { g.clear_out_edges(u); } // MutableBidirectionalGraph template void clear_in_edges( typename ContigGraph::vertex_descriptor u, ContigGraph& g) { g.clear_in_edges(u); } // PropertyGraph /** Return true if this vertex has been removed. */ template bool get(vertex_removed_t tag, const ContigGraph& g, typename ContigGraph::vertex_descriptor u) { return get(tag, static_cast(g), u); } template void put(vertex_removed_t tag, ContigGraph& g, typename ContigGraph::vertex_descriptor u, bool flag) { put(tag, static_cast(g), u, flag); put(tag, static_cast(g), get(vertex_complement, g, u), flag); } /** Return the properties of the edge of iterator eit. */ template const typename ContigGraph::edge_property_type& get(edge_bundle_t, const ContigGraph&, typename ContigGraph::out_edge_iterator eit) { return eit.get_property(); } // PropertyGraph template typename vertex_bundle_type::type get(vertex_bundle_t, const ContigGraph& g, typename ContigGraph::vertex_descriptor u) { return g[u]; } template typename edge_bundle_type::type get(edge_bundle_t, const ContigGraph& g, typename ContigGraph::edge_descriptor e) { return g[e]; } // PropertyGraph namespace boost { template struct property_map, vertex_index_t> { typedef typename property_map::type type; typedef type const_type; }; } /** Return the complement of the specified vertex. */ template typename graph_traits::vertex_descriptor get(vertex_complement_t, const ContigGraph&, typename graph_traits::vertex_descriptor u) { return u ^ 1; } /** Return the contig index of the specified vertex. */ template ContigID get(vertex_contig_index_t, const ContigGraph&, typename graph_traits::vertex_descriptor u) { return u.contigIndex(); } /** Return the sense of the specified vertex. */ template bool get(vertex_sense_t, const ContigGraph&, typename graph_traits::vertex_descriptor u) { return u.sense(); } // VertexMutablePropertyGraph template typename ContigGraph::vertex_descriptor add_vertex( const typename vertex_property::type& vp, ContigGraph& g) { return g.add_vertex(vp); } // EdgeMutablePropertyGraph template std::pair::edge_descriptor, bool> add_edge( typename ContigGraph::vertex_descriptor u, typename ContigGraph::vertex_descriptor v, const typename ContigGraph::edge_property_type& ep, ContigGraph& g) { return g.add_edge(u, v, ep); } #endif