vg::IncrementalSubgraph Class Reference

#include <incremental_subgraph.hpp>

Inheritance diagram for vg::IncrementalSubgraph:

Classes
struct	FCmp
struct	IterFCmp

Public Member Functions
	IncrementalSubgraph (const HandleGraph &graph, const pos_t &starting_position, bool extract_left, int64_t max_distance=numeric_limits< int64_t >::max(), size_t frontier_copy_limit=numeric_limits< size_t >::max(), size_t max_num_nodes=numeric_limits< size_t >::max())
	IncrementalSubgraph ()=default
	Default constructor – not actually functional.
	~IncrementalSubgraph ()
	Default destructor.
bool	is_extendable () const
	Specialized interface.
handle_t	extend ()
	Extract an additional node.
size_t	order_of (const handle_t &handle) const
	The order of a node in a topological order of the extracted graph.
handle_t	handle_at_order (size_t i) const
	The node at a given position in the topological order.
int64_t	min_distance_from_start (const handle_t &handle) const
	The minimum distance from the start position.
int64_t	max_distance_from_start (const handle_t &handle) const
	The maximum distance from the start position.
bool	extracting_left () const
	Are we doing extraction left or right?
bool	has_node (id_t node_id) const
	HandleGraph interface.
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.
id_t	get_id (const handle_t &handle) const
	Get the ID from a handle.
bool	get_is_reverse (const handle_t &handle) const
	Get the orientation of a handle.
handle_t	flip (const handle_t &handle) const
	Invert the orientation of a handle (potentially without getting its ID).
size_t	get_length (const handle_t &handle) const
	Get the length of a node.
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.
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.
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.

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
int64_t	max_distance
	farthest distance we will travel from the start pos
size_t	frontier_copy_limit
	the maximum number of copies of a node we will allow in the frontier at a time
size_t	max_num_nodes
vector< tuple< handle_t, vector< size_t >, vector< size_t >, int64_t, int64_t > >	extracted
	records of (underlying handle, left edges, right edges, min distance, max distance)
set< tuple< int64_t, handle_t, unordered_set< handle_t > *, vector< size_t > * >, FCmp >	frontier
unordered_map< handle_t, unordered_map< handle_t, set< decltype(frontier)::iterator, IterFCmp > > >	frontier_index
unordered_map< handle_t, size_t >	frontier_count
	the number of a given node there is currently in the frontier
const HandleGraph *	graph = nullptr
	the underlying graph

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(),
		size_t	frontier_copy_limit = numeric_limits<size_t>::max(),
		size_t	max_num_nodes = numeric_limits<size_t>::max() )

Initialize the copy number limits how many times a cyce will be traversed before giving up on it (until encountering it again)

IncrementalSubgraph() [2/2]

vg::IncrementalSubgraph::IncrementalSubgraph ( )

default

Default constructor – not actually functional.

~IncrementalSubgraph()

vg::IncrementalSubgraph::~IncrementalSubgraph

(

)

Default destructor.

Member Function Documentation

extend()

handle_t vg::IncrementalSubgraph::extend

(

)

Extract an additional node.

extracting_left()

bool vg::IncrementalSubgraph::extracting_left

(

)

const

Are we doing extraction left or right?

flip()

handle_t vg::IncrementalSubgraph::flip

(

const handle_t &

handle

)

const

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

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

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

get_degree()

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

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.

get_edge_count()

size_t vg::IncrementalSubgraph::get_edge_count

(

)

const

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

get_handle()

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

get_id()

id_t vg::IncrementalSubgraph::get_id

(

const handle_t &

handle

)

const

Get the ID from a handle.

get_is_reverse()

bool vg::IncrementalSubgraph::get_is_reverse

(

const handle_t &

handle

)

const

Get the orientation of a handle.

get_length()

size_t vg::IncrementalSubgraph::get_length

(

const handle_t &

handle

)

const

Get the length of a node.

get_node_count()

size_t vg::IncrementalSubgraph::get_node_count

(

)

const

Return the number of nodes in the graph.

get_sequence()

string vg::IncrementalSubgraph::get_sequence

(

const handle_t &

handle

)

const

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

get_subsequence()

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

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.

get_underlying_handle()

handle_t vg::IncrementalSubgraph::get_underlying_handle

(

const handle_t &

handle

)

const

ExpandingOverlayGraph interface.

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

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

HandleGraph interface.

Method to check if a node exists by ID

is_extendable()

bool vg::IncrementalSubgraph::is_extendable

(

)

const

Specialized interface.

True if there are additional nodes

max_distance_from_start()

int64_t vg::IncrementalSubgraph::max_distance_from_start

(

const handle_t &

handle

)

const

The maximum distance from the start position.

max_node_id()

id_t vg::IncrementalSubgraph::max_node_id

(

)

const

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.

min_distance_from_start()

int64_t vg::IncrementalSubgraph::min_distance_from_start

(

const handle_t &

handle

)

const

The minimum distance from the start position.

min_node_id()

id_t vg::IncrementalSubgraph::min_node_id

(

)

const

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.

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, int64_t> > vg::IncrementalSubgraph::extracted

private

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

frontier

set<tuple<int64_t, handle_t, unordered_set<handle_t>*, vector<size_t>*>, FCmp> vg::IncrementalSubgraph::frontier

private

records of (distance, node, unseen edges going into, seen edges going into). serves as an updateable priority queue for nodes that are adjacent to the extracted nodes the container classes are created on the heap so that we can do a remove-modify-replace update to frontier entries without deep-copying the containers

frontier_copy_limit

size_t vg::IncrementalSubgraph::frontier_copy_limit

private

the maximum number of copies of a node we will allow in the frontier at a time

frontier_count

unordered_map<handle_t, size_t> vg::IncrementalSubgraph::frontier_count

private

the number of a given node there is currently in the frontier

frontier_index

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

private

provides random access into the frontier by handle, in the same order that the handles occur in the frontier. indexed by target node and then by predecessor node

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

max_num_nodes

size_t vg::IncrementalSubgraph::max_num_nodes

private

---

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

• src/incremental_subgraph.hpp
• src/incremental_subgraph.cpp