vg
tools for working with variation graphs
Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
vg::DagifiedGraph Class Reference

#include <dagified_graph.hpp>

Inheritance diagram for vg::DagifiedGraph:
handlegraph::ExpandingOverlayGraph handlegraph::HandleGraph

Public Member Functions

 DagifiedGraph (const HandleGraph *graph, size_t min_preserved_path_length, size_t max_num_duplications=std::numeric_limits< size_t >::max())
 
 DagifiedGraph ()=default
 Default constructor – not actually functional. More...
 
 ~DagifiedGraph ()=default
 Default destructor. More...
 
bool has_node (id_t node_id) const
 HandleGraph interface. More...
 
handle_t get_handle (const id_t &node_id, bool is_reverse=false) const
 Look up the handle for the node with the given ID in the given orientation. More...
 
id_t get_id (const handle_t &handle) const
 Get the ID from a handle. More...
 
bool get_is_reverse (const handle_t &handle) const
 Get the orientation of a handle. More...
 
handle_t flip (const handle_t &handle) const
 Invert the orientation of a handle (potentially without getting its ID) More...
 
size_t get_length (const handle_t &handle) const
 Get the length of a node. More...
 
string get_sequence (const handle_t &handle) const
 
bool follow_edges_impl (const handle_t &handle, bool go_left, const function< bool(const handle_t &)> &iteratee) const
 
bool for_each_handle_impl (const function< bool(const handle_t &)> &iteratee, bool parallel=false) const
 
size_t get_node_count () const
 Return the number of nodes in the graph. More...
 
id_t min_node_id () const
 
id_t max_node_id () const
 
handle_t get_underlying_handle (const handle_t &handle) const
 ExpandingOverlayGraph interface. More...
 
- Public Member Functions inherited from handlegraph::ExpandingOverlayGraph
virtual ~ExpandingOverlayGraph ()=default
 
- Public Member Functions inherited from handlegraph::HandleGraph
virtual ~HandleGraph ()=default
 
template<typename Iteratee >
bool follow_edges (const handle_t &handle, bool go_left, const Iteratee &iteratee) const
 
template<typename Iteratee >
bool for_each_handle (const Iteratee &iteratee, bool parallel=false) const
 
virtual size_t get_degree (const handle_t &handle, bool go_left) const
 
virtual bool has_edge (const handle_t &left, const handle_t &right) const
 
bool has_edge (const edge_t &edge) const
 Convenient wrapper of has_edge for edge_t argument. More...
 
virtual size_t get_edge_count () const
 
virtual size_t get_total_length () const
 
virtual char get_base (const handle_t &handle, size_t index) const
 
virtual std::string get_subsequence (const handle_t &handle, size_t index, size_t size) const
 
handle_t forward (const handle_t &handle) const
 Get the locally forward version of a handle. More...
 
edge_t edge_handle (const handle_t &left, const handle_t &right) const
 
handle_t traverse_edge_handle (const edge_t &edge, const handle_t &left) const
 
template<typename Iteratee >
bool for_each_edge (const Iteratee &iteratee, bool parallel=false) const
 

Protected Member Functions

uint64_t scc_copy_of_handle (const handle_t &handle) const
 
uint64_t scc_copy_of_node_id (const id_t &node_id) const
 
size_t layout_order_of_handle (const handle_t &handle) const
 Helper function that returns the layout order of a handle from the underlying graph. More...
 
id_t get_underlying_id (const id_t &node_id) const
 
handle_t nth_copy_of_handle (const handle_t &handle, const uint64_t &n) const
 Helper function, returns the n-th copy in the dagified graph of a handle in the underlying graph. More...
 
- Protected Member Functions inherited from handlegraph::HandleGraph
virtual bool follow_edges_impl (const handle_t &handle, bool go_left, const std::function< bool(const handle_t &)> &iteratee) const =0
 
virtual bool for_each_handle_impl (const std::function< bool(const handle_t &)> &iteratee, bool parallel=false) const =0
 

Protected Attributes

const HandleGraphgraph = nullptr
 The underlying graph we're dagifiying. More...
 
unordered_map< handle_t, size_t > layout_order
 
vector< uint64_t > scc_of_handle
 
vector< uint64_t > scc_copy_count
 
uint64_t min_handle = std::numeric_limits<uint64_t>::max()
 The minimum value of a handle in the underlying graph, interpreted as an integer. More...
 
uint64_t handle_val_range = 0
 The width of the range of values that handles in the underlying graph take. More...
 
size_t node_count = 0
 The number of nodes including duplicated nodes, computed during construction. More...
 
id_t max_id = std::numeric_limits<uint64_t>::min()
 The maximum ID of the graph, computed during construction. More...
 

Detailed Description

A HandleGraph implementation that wraps some other handle graph and converts it into a DAG, preserving all paths up a a minimum length.

Constructor & Destructor Documentation

◆ DagifiedGraph() [1/2]

vg::DagifiedGraph::DagifiedGraph ( const HandleGraph graph,
size_t  min_preserved_path_length,
size_t  max_num_duplications = std::numeric_limits<size_t>::max() 
)

Expand a single-stranded graph into a DAG, preserving all walks up to the minimum length. If max duplications is provided, limits the number of times any node is copied.

◆ DagifiedGraph() [2/2]

vg::DagifiedGraph::DagifiedGraph ( )
default

Default constructor – not actually functional.

◆ ~DagifiedGraph()

vg::DagifiedGraph::~DagifiedGraph ( )
default

Default destructor.

Member Function Documentation

◆ flip()

handle_t vg::DagifiedGraph::flip ( const handle_t handle) const
virtual

Invert the orientation of a handle (potentially without getting its ID)

Implements handlegraph::HandleGraph.

◆ follow_edges_impl()

bool vg::DagifiedGraph::follow_edges_impl ( const handle_t handle,
bool  go_left,
const function< bool(const handle_t &)> &  iteratee 
) const

Loop over all the handles to next/previous (right/left) nodes. Passes them to a callback which returns false to stop iterating and true to continue. Returns true if we finished and false if we stopped early.

◆ for_each_handle_impl()

bool vg::DagifiedGraph::for_each_handle_impl ( const function< bool(const handle_t &)> &  iteratee,
bool  parallel = false 
) const

Loop over all the nodes in the graph in their local forward orientations, in their internal stored order. Stop if the iteratee returns false. Can be told to run in parallel, in which case stopping after a false return value is on a best-effort basis and iteration order is not defined.

◆ get_handle()

handle_t vg::DagifiedGraph::get_handle ( const id_t node_id,
bool  is_reverse = false 
) const
virtual

Look up the handle for the node with the given ID in the given orientation.

Implements handlegraph::HandleGraph.

◆ get_id()

id_t vg::DagifiedGraph::get_id ( const handle_t handle) const
virtual

Get the ID from a handle.

Implements handlegraph::HandleGraph.

◆ get_is_reverse()

bool vg::DagifiedGraph::get_is_reverse ( const handle_t handle) const
virtual

Get the orientation of a handle.

Implements handlegraph::HandleGraph.

◆ get_length()

size_t vg::DagifiedGraph::get_length ( const handle_t handle) const
virtual

Get the length of a node.

Implements handlegraph::HandleGraph.

◆ get_node_count()

size_t vg::DagifiedGraph::get_node_count ( ) const
virtual

Return the number of nodes in the graph.

Implements handlegraph::HandleGraph.

◆ get_sequence()

string vg::DagifiedGraph::get_sequence ( const handle_t handle) const
virtual

Get the sequence of a node, presented in the handle's local forward orientation.

Implements handlegraph::HandleGraph.

◆ get_underlying_handle()

handle_t vg::DagifiedGraph::get_underlying_handle ( const handle_t handle) const
virtual

ExpandingOverlayGraph interface.

Returns the handle in the underlying graph that corresponds to a handle in the overlay

Implements handlegraph::ExpandingOverlayGraph.

◆ get_underlying_id()

id_t vg::DagifiedGraph::get_underlying_id ( const id_t node_id) const
protected

Helper function to identify the node ID in the original graph that corresponds to a node in the dagified graph

◆ has_node()

bool vg::DagifiedGraph::has_node ( id_t  node_id) const
virtual

HandleGraph interface.

Implements handlegraph::HandleGraph.

◆ layout_order_of_handle()

size_t vg::DagifiedGraph::layout_order_of_handle ( const handle_t handle) const
protected

Helper function that returns the layout order of a handle from the underlying graph.

◆ max_node_id()

id_t vg::DagifiedGraph::max_node_id ( ) const
virtual

Return the largest ID in the graph, or some larger number if the largest ID is unavailable. Return value is unspecified if the graph is empty.

Implements handlegraph::HandleGraph.

◆ min_node_id()

id_t vg::DagifiedGraph::min_node_id ( ) const
virtual

Return the smallest ID in the graph, or some smaller number if the smallest ID is unavailable. Return value is unspecified if the graph is empty.

Implements handlegraph::HandleGraph.

◆ nth_copy_of_handle()

handle_t vg::DagifiedGraph::nth_copy_of_handle ( const handle_t handle,
const uint64_t &  n 
) const
protected

Helper function, returns the n-th copy in the dagified graph of a handle in the underlying graph.

◆ scc_copy_of_handle()

uint64_t vg::DagifiedGraph::scc_copy_of_handle ( const handle_t handle) const
protected

Helper function to identify which ordinal copy of a strongly connected component in the underlying graph the handle belongs to

◆ scc_copy_of_node_id()

uint64_t vg::DagifiedGraph::scc_copy_of_node_id ( const id_t node_id) const
protected

Helper function to identify which ordinal copy of a strongly connected component in the underlying graph the node ID belongs to

Member Data Documentation

◆ graph

const HandleGraph* vg::DagifiedGraph::graph = nullptr
protected

The underlying graph we're dagifiying.

◆ handle_val_range

uint64_t vg::DagifiedGraph::handle_val_range = 0
protected

The width of the range of values that handles in the underlying graph take.

◆ layout_order

unordered_map<handle_t, size_t> vg::DagifiedGraph::layout_order
protected

Map from a canonical orientation of underlying handles (not necessarily forward!) to the ordinal position of the node in a low-FAS layout

◆ max_id

id_t vg::DagifiedGraph::max_id = std::numeric_limits<uint64_t>::min()
protected

The maximum ID of the graph, computed during construction.

◆ min_handle

uint64_t vg::DagifiedGraph::min_handle = std::numeric_limits<uint64_t>::max()
protected

The minimum value of a handle in the underlying graph, interpreted as an integer.

◆ node_count

size_t vg::DagifiedGraph::node_count = 0
protected

The number of nodes including duplicated nodes, computed during construction.

◆ scc_copy_count

vector<uint64_t> vg::DagifiedGraph::scc_copy_count
protected

The number of times each strongly connected component is duplicated in the dagified graph

◆ scc_of_handle

vector<uint64_t> vg::DagifiedGraph::scc_of_handle
protected

The ID of the strongly connected component that the handle at each layout position belongs to


The documentation for this class was generated from the following files: