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

#include <incremental_subgraph.hpp>

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

Public Member Functions

 IncrementalSubgraph (const HandleGraph &graph, const pos_t &starting_position, bool extract_left, int64_t max_distance=numeric_limits< int64_t >::max())
 
 IncrementalSubgraph ()=default
 Default constructor – not actually functional. More...
 
 ~IncrementalSubgraph ()=default
 Default destructor. More...
 
bool is_extendable () const
 Specialized interface. More...
 
handle_t extend ()
 Extract an additional node. More...
 
size_t order_of (const handle_t &handle) const
 The order of a node in a topological order of the extracted graph. More...
 
handle_t handle_at_order (size_t i) const
 The node at a given position in the topological order. More...
 
int64_t distance_from_start (const handle_t &handle) const
 The minimum distance from the start position. 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
 
size_t get_degree (const handle_t &handle, bool go_left) const
 Optional HandleGraph interface. More...
 
size_t get_edge_count () const
 
char get_base (const handle_t &handle, size_t index) const
 
string get_subsequence (const handle_t &handle, size_t index, size_t size) 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 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_total_length () 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
 

Private Member Functions

pair< size_t, size_t > underlying_interval (size_t i) const
 

Private Attributes

bool extract_left
 direction we're extracting from the start pos More...
 
int64_t max_distance
 farthest distance we will travel from the start pos More...
 
vector< tuple< handle_t, vector< size_t >, vector< size_t >, int64_t > > extracted
 records of (underlying handle, left edges, right edges, distance) More...
 
unordered_map< handle_t, size_t > extracted_index
 index of latest addition of a handle in the extracted vector More...
 
set< tuple< size_t, int64_t, handle_t > > frontier
 
unordered_map< handle_t, decltype(frontier)::iterator > frontier_index
 provides random access into the frontier by handle More...
 
const HandleGraphgraph = nullptr
 The underlying graph. More...
 

Additional Inherited Members

- 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
 

Detailed Description

A subgraph that is extracted, made single-stranded, and DAG-fied online on an as-needed basis from the parent graph. It is restricted to subgraphs that extend from a single position in the graph in one direction.

Constructor & Destructor Documentation

◆ IncrementalSubgraph() [1/2]

vg::IncrementalSubgraph::IncrementalSubgraph ( const HandleGraph graph,
const pos_t starting_position,
bool  extract_left,
int64_t  max_distance = numeric_limits<int64_t>::max() 
)

Initialize as the reverse version of another graph, optionally also complementing

◆ IncrementalSubgraph() [2/2]

vg::IncrementalSubgraph::IncrementalSubgraph ( )
default

Default constructor – not actually functional.

◆ ~IncrementalSubgraph()

vg::IncrementalSubgraph::~IncrementalSubgraph ( )
default

Default destructor.

Member Function Documentation

◆ distance_from_start()

int64_t vg::IncrementalSubgraph::distance_from_start ( const handle_t handle) const

The minimum distance from the start position.

◆ extend()

handle_t vg::IncrementalSubgraph::extend ( )

Extract an additional node.

◆ flip()

handle_t vg::IncrementalSubgraph::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::IncrementalSubgraph::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::IncrementalSubgraph::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_base()

char vg::IncrementalSubgraph::get_base ( const handle_t handle,
size_t  index 
) const
virtual

Returns one base of a handle's sequence, in the orientation of the handle.

Reimplemented from handlegraph::HandleGraph.

◆ get_degree()

size_t vg::IncrementalSubgraph::get_degree ( const handle_t handle,
bool  go_left 
) const
virtual

Optional HandleGraph interface.

Get the number of edges on the right (go_left = false) or left (go_left = true) side of the given handle. The default implementation is O(n) in the number of edges returned, but graph implementations that track this information more efficiently can override this method.

Reimplemented from handlegraph::HandleGraph.

◆ get_edge_count()

size_t vg::IncrementalSubgraph::get_edge_count ( ) const
virtual

Return the total number of edges in the graph. If not overridden, counts them all in linear time.

Reimplemented from handlegraph::HandleGraph.

◆ get_handle()

handle_t vg::IncrementalSubgraph::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::IncrementalSubgraph::get_id ( const handle_t handle) const
virtual

Get the ID from a handle.

Implements handlegraph::HandleGraph.

◆ get_is_reverse()

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

Get the orientation of a handle.

Implements handlegraph::HandleGraph.

◆ get_length()

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

Get the length of a node.

Implements handlegraph::HandleGraph.

◆ get_node_count()

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

Return the number of nodes in the graph.

Implements handlegraph::HandleGraph.

◆ get_sequence()

string vg::IncrementalSubgraph::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_subsequence()

string vg::IncrementalSubgraph::get_subsequence ( const handle_t handle,
size_t  index,
size_t  size 
) const
virtual

Returns a substring of a handle's sequence, in the orientation of the handle. If the indicated substring would extend beyond the end of the handle's sequence, the return value is truncated to the sequence's end. By default O(n) in the size of the handle's sequence, but can be overriden.

Reimplemented from handlegraph::HandleGraph.

◆ get_underlying_handle()

handle_t vg::IncrementalSubgraph::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.

◆ handle_at_order()

handle_t vg::IncrementalSubgraph::handle_at_order ( size_t  i) const

The node at a given position in the topological order.

◆ has_node()

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

HandleGraph interface.

Method to check if a node exists by ID

Implements handlegraph::HandleGraph.

◆ is_extendable()

bool vg::IncrementalSubgraph::is_extendable ( ) const

Specialized interface.

True if there are additional nodes

◆ max_node_id()

id_t vg::IncrementalSubgraph::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::IncrementalSubgraph::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.

◆ order_of()

size_t vg::IncrementalSubgraph::order_of ( const handle_t handle) const

The order of a node in a topological order of the extracted graph.

◆ underlying_interval()

pair<size_t, size_t> vg::IncrementalSubgraph::underlying_interval ( size_t  i) const
private

Member Data Documentation

◆ extract_left

bool vg::IncrementalSubgraph::extract_left
private

direction we're extracting from the start pos

◆ extracted

vector<tuple<handle_t, vector<size_t>, vector<size_t>, int64_t> > vg::IncrementalSubgraph::extracted
private

records of (underlying handle, left edges, right edges, distance)

◆ extracted_index

unordered_map<handle_t, size_t> vg::IncrementalSubgraph::extracted_index
private

index of latest addition of a handle in the extracted vector

◆ frontier

set<tuple<size_t, int64_t, handle_t> > vg::IncrementalSubgraph::frontier
private

records of (incoming edges seen, distance, node). serves as an updateable priority queue for nodes that are adjacent to the extracted nodes

◆ frontier_index

unordered_map<handle_t, decltype(frontier)::iterator> vg::IncrementalSubgraph::frontier_index
private

provides random access into the frontier by handle

◆ graph

const HandleGraph* vg::IncrementalSubgraph::graph = nullptr
private

The underlying graph.

◆ max_distance

int64_t vg::IncrementalSubgraph::max_distance
private

farthest distance we will travel from the start pos


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