#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. More...

	~IncrementalSubgraph ()
	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	min_distance_from_start (const handle_t &handle) const
	The minimum distance from the start position. More...

int64_t	max_distance_from_start (const handle_t &handle) const
	The maximum distance from the start position. More...

bool	extracting_left () const
	Are we doing extraction left or right? 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...

size_t	frontier_copy_limit
	the maximum number of copies of a node we will allow in the frontier at a time More...

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) More...

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 More...

const HandleGraph *	graph = 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()`,
		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

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_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

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_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

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, 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

Classes

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ IncrementalSubgraph() [1/2]

◆ IncrementalSubgraph() [2/2]

◆ ~IncrementalSubgraph()

Member Function Documentation

◆ extend()

◆ extracting_left()

◆ flip()

◆ follow_edges_impl()

◆ for_each_handle_impl()

◆ get_base()

◆ get_degree()

◆ get_edge_count()

◆ get_handle()

◆ get_id()

◆ get_is_reverse()

◆ get_length()

◆ get_node_count()

◆ get_sequence()

◆ get_subsequence()

◆ get_underlying_handle()

◆ handle_at_order()

◆ has_node()

◆ is_extendable()

◆ max_distance_from_start()

◆ max_node_id()

◆ min_distance_from_start()

◆ min_node_id()

◆ order_of()

◆ underlying_interval()

Member Data Documentation

◆ extract_left

◆ extracted

◆ frontier

◆ frontier_copy_limit

◆ frontier_count

◆ frontier_index

◆ graph

◆ max_distance

◆ max_num_nodes