#include <snarls.hpp>

Classes
struct	SnarlRecord

Public Member Functions
template<typename SnarlIterator >
	SnarlManager (SnarlIterator begin, SnarlIterator end)

	SnarlManager (istream &in)
	Construct a SnarlManager for the snarls contained in an input stream. More...

	SnarlManager (const function< void(const function< void(Snarl &)> &)> &for_each_snarl)
	Construct a SnarlManager from a function that calls a callback with each Snarl in turn. More...

	SnarlManager ()=default

	~SnarlManager ()=default
	Destructor. More...

	SnarlManager (const SnarlManager &other)=delete
	Cannot be copied because of all the internal pointer indexes. More...

SnarlManager &	operator= (const SnarlManager &other)=delete

	SnarlManager (SnarlManager &&other)=default
	Can be moved. More...

SnarlManager &	operator= (SnarlManager &&other)=default

void	serialize (ostream &out) const

const Snarl *	add_snarl (const Snarl &new_snarl)

void	flip (const Snarl *snarl)
	Reverses the orientation of a managed snarl. More...

void	flip (const Chain *snarl)

void	finish ()

const vector< const Snarl * > &	children_of (const Snarl *snarl) const

const Snarl *	parent_of (const Snarl *snarl) const
	Returns a pointer to the parent of a Snarl or nullptr if there is none. More...

const Snarl *	into_which_snarl (int64_t id, bool reverse) const

const Snarl *	into_which_snarl (const Visit &visit) const

const Chain *	chain_of (const Snarl *snarl) const

bool	chain_orientation_of (const Snarl *snarl) const

size_t	chain_rank_of (const Snarl *snarl) const

bool	in_nontrivial_chain (const Snarl *here) const

const deque< Chain > &	chains_of (const Snarl *snarl) const

NetGraph	net_graph_of (const Snarl snarl, const HandleGraph graph, bool use_internal_connectivity=true) const

bool	is_leaf (const Snarl *snarl) const
	Returns true if snarl has no children and false otherwise. More...

bool	is_root (const Snarl *snarl) const
	Returns true if snarl has no parent and false otherwise. More...

bool	is_trivial (const Snarl *snarl, const HandleGraph &graph) const

bool	all_children_trivial (const Snarl *snarl, const HandleGraph &graph) const
	Returns true if the snarl lacks any nontrivial children. More...

const vector< const Snarl * > &	top_level_snarls () const
	Returns a reference to a vector with the roots of the Snarl trees. More...

pair< unordered_set< id_t >, unordered_set< edge_t > >	shallow_contents (const Snarl *snarl, const HandleGraph &graph, bool include_boundary_nodes) const

pair< unordered_set< id_t >, unordered_set< edge_t > >	deep_contents (const Snarl *snarl, const HandleGraph &graph, bool include_boundary_nodes) const

vector< Visit >	visits_left (const Visit &visit, const HandleGraph &graph, const Snarl *in_snarl) const

vector< Visit >	visits_right (const Visit &visit, const HandleGraph &graph, const Snarl *in_snarl) const

unordered_map< pair< int64_t, bool >, const Snarl * >	snarl_boundary_index () const

unordered_map< pair< int64_t, bool >, const Snarl * >	snarl_start_index () const
	Returns a map from all Snarl start boundaries to the Snarl they point into. More...

unordered_map< pair< int64_t, bool >, const Snarl * >	snarl_end_index () const

void	for_each_top_level_snarl (const function< void(const Snarl *)> &lambda) const
	Execute a function on all top level sites. More...

void	for_each_snarl_preorder (const function< void(const Snarl *)> &lambda) const
	Execute a function on all sites in a preorder traversal. More...

void	for_each_top_level_snarl_parallel (const function< void(const Snarl *)> &lambda) const
	Execute a function on all top level sites in parallel. More...

void	for_each_snarl_parallel (const function< void(const Snarl *)> &lambda) const
	Execute a function on all sites in parallel. More...

void	for_each_top_level_chain (const function< void(const Chain *)> &lambda) const
	Execute a function on all top level chains. More...

void	for_each_top_level_chain_parallel (const function< void(const Chain *)> &lambda) const
	Execute a function on all top level chains in parallel. More...

void	for_each_chain (const function< void(const Chain *)> &lambda) const
	Ececute a function on all chains. More...

void	for_each_chain_parallel (const function< void(const Chain *)> &lambda) const
	Ececute a function on all chains in parallel. More...

void	for_each_snarl_unindexed (const function< void(const Snarl *)> &lambda) const
	Iterate over snarls as they are stored in deque<SnarlRecords> More...

const Snarl *	manage (const Snarl &not_owned) const

const Snarl *	discrete_uniform_sample (minstd_rand0 &random_engine) const

int	num_snarls () const
	Count snarls in deque<SnarlRecords>, a master list of snarls in graph. More...

size_t	snarl_number (const Snarl *snarl) const
	Get the snarl number from the SnarlRecord* member with given snarl. More...

const Snarl *	translate_snarl_num (size_t snarl_num)

Private Member Functions
const SnarlRecord *	record (const Snarl *snarl) const
	Get the const SnarlRecord for a const managed snarl. More...

SnarlRecord *	record (Snarl *snarl)
	Get the SnarlRecord for a managed snarl. More...

const Snarl *	unrecord (const SnarlRecord *record) const
	Get the const Snarl owned by a const SnarlRecord. More...

Snarl *	unrecord (SnarlRecord *record)
	Get the Snarl owned by a SnarlRecord. More...

void	build_indexes ()
	Builds tree indexes after Snarls have been added to the snarls vector. More...

deque< Chain >	compute_chains (const vector< const Snarl * > &input_snarls)

void	regularize ()

Visit	next_snarl (const Visit &here) const

Visit	prev_snarl (const Visit &here) const

const Snarl *	snarl_sharing_start (const Snarl *here) const

const Snarl *	snarl_sharing_end (const Snarl *here) const

Private Attributes
deque< SnarlRecord >	snarls

vector< const Snarl * >	roots
	Roots of snarl trees. More...

deque< Chain >	root_chains
	Chains of root-level snarls. Uses a deque so Chain* pointers don't get invalidated. More...

unordered_map< pair< int64_t, bool >, const Snarl * >	snarl_into
	Map of node traversals to the snarls they point into. More...

Detailed Description

A structure to keep track of the tree relationships between Snarls and perform utility algorithms on them

Constructor & Destructor Documentation

◆ SnarlManager() [1/6]

template<typename SnarlIterator >

vg::SnarlManager::SnarlManager	(	SnarlIterator	begin,
		SnarlIterator	end
	)

Construct a SnarlManager for the snarls returned by an iterator Also covers iterators of chains of snarls.

◆ SnarlManager() [2/6]

vg::SnarlManager::SnarlManager ( istream & in )

Construct a SnarlManager for the snarls contained in an input stream.

◆ SnarlManager() [3/6]

vg::SnarlManager::SnarlManager ( const function< void(const function< void(Snarl &)> &)> & for_each_snarl )

Construct a SnarlManager from a function that calls a callback with each Snarl in turn.

◆ SnarlManager() [4/6]

vg::SnarlManager::SnarlManager ( )

default

Default constructor for an empty SnarlManager. Must call finish() once all snarls have been added with add_snarl().

◆ ~SnarlManager()

vg::SnarlManager::~SnarlManager ( )

default

Destructor.

◆ SnarlManager() [5/6]

vg::SnarlManager::SnarlManager ( const SnarlManager & other )

delete

Cannot be copied because of all the internal pointer indexes.

◆ SnarlManager() [6/6]

vg::SnarlManager::SnarlManager ( SnarlManager && other )

default

Can be moved.

Member Function Documentation

◆ add_snarl()

const Snarl * vg::SnarlManager::add_snarl ( const Snarl & new_snarl )

Add the given snarl to the SnarlManager. After all snarls have been added, finish() must be called to compute chains and indexes. We don't let precomputed chains be added, because we want chain orientations relative to snarls to be deterministic given an order of snarls. Returns a pointer to the managed snarl copy. Only this function may add in new Snarls.

◆ all_children_trivial()

bool vg::SnarlManager::all_children_trivial	(	const Snarl *	snarl,
		const HandleGraph &	graph
	)		const

Returns true if the snarl lacks any nontrivial children.

◆ build_indexes()

void vg::SnarlManager::build_indexes ( )

private

Builds tree indexes after Snarls have been added to the snarls vector.

◆ chain_of()

const Chain * vg::SnarlManager::chain_of ( const Snarl * snarl ) const

Get the Chain that the given snarl participates in. Instead of asking this class to walk the chain for you, use ChainIterators on this chain. This is always non-null.

◆ chain_orientation_of()

bool vg::SnarlManager::chain_orientation_of ( const Snarl * snarl ) const

If the given Snarl is backward in its chain, return true. Otherwise, return false.

◆ chain_rank_of()

size_t vg::SnarlManager::chain_rank_of ( const Snarl * snarl ) const

Get the rank that the given snarl appears in in its chain. If two snarls are in forward orientation in the chain, then leaving the end of the lower rank snarl will eventually reach the start of the higher rank snarl. If either or both snarls is backward, you leave/arrive at the other bounding node instead.

Sorting snarls by rank will let you visit them in chain order without walking the whole chain.

◆ chains_of()

const deque< Chain > & vg::SnarlManager::chains_of ( const Snarl * snarl ) const

Get all the snarls in all the chains under the given parent snarl. If the parent snarl is null, gives the top-level chains that connect and contain the top-level root snarls. Unary snarls and snarls in trivial chains will be presented as their own chains. Snarls are not necessarily oriented appropriately given their ordering in the chain. Useful for making a net graph.

◆ children_of()

const vector< const Snarl * > & vg::SnarlManager::children_of ( const Snarl * snarl ) const

Returns a vector of pointers to the children of a Snarl. If given null, returns the top-level root snarls.

◆ compute_chains()

deque< Chain > vg::SnarlManager::compute_chains ( const vector< const Snarl * > & input_snarls )

private

Actually compute chains for a set of already indexed snarls, which is important when chains were not provided. Returns the chains.

◆ deep_contents()

pair< unordered_set< id_t >, unordered_set< edge_t > > vg::SnarlManager::deep_contents	(	const Snarl *	snarl,
		const HandleGraph &	graph,
		bool	include_boundary_nodes
	)		const

Returns the Nodes and Edges contained in this Snarl, including those in child Snarls (optionally includes Snarl's own boundary Nodes)

◆ discrete_uniform_sample()

const Snarl * vg::SnarlManager::discrete_uniform_sample ( minstd_rand0 & random_engine ) const

Sample snarls discrete uniformly Returns a nullptr if no snarls are found

◆ finish()

void vg::SnarlManager::finish ( )

Note that we have finished calling add_snarl. Compute the snarl parent/child indexes and chains.

◆ flip() [1/2]

void vg::SnarlManager::flip ( const Chain * snarl )

Reverses the order and orientation of a managed chain, leaving all the component snarls in their original orientations.

◆ flip() [2/2]

void vg::SnarlManager::flip ( const Snarl * snarl )

Reverses the orientation of a managed snarl.

◆ for_each_chain()

void vg::SnarlManager::for_each_chain ( const function< void(const Chain *)> & lambda ) const

Ececute a function on all chains.

◆ for_each_chain_parallel()

void vg::SnarlManager::for_each_chain_parallel ( const function< void(const Chain *)> & lambda ) const

Ececute a function on all chains in parallel.

◆ for_each_snarl_parallel()

void vg::SnarlManager::for_each_snarl_parallel ( const function< void(const Snarl *)> & lambda ) const

Execute a function on all sites in parallel.

◆ for_each_snarl_preorder()

void vg::SnarlManager::for_each_snarl_preorder ( const function< void(const Snarl *)> & lambda ) const

Execute a function on all sites in a preorder traversal.

◆ for_each_snarl_unindexed()

void vg::SnarlManager::for_each_snarl_unindexed ( const function< void(const Snarl *)> & lambda ) const

Iterate over snarls as they are stored in deque<SnarlRecords>

◆ for_each_top_level_chain()

void vg::SnarlManager::for_each_top_level_chain ( const function< void(const Chain *)> & lambda ) const

Execute a function on all top level chains.

◆ for_each_top_level_chain_parallel()

void vg::SnarlManager::for_each_top_level_chain_parallel ( const function< void(const Chain *)> & lambda ) const

Execute a function on all top level chains in parallel.

◆ for_each_top_level_snarl()

void vg::SnarlManager::for_each_top_level_snarl ( const function< void(const Snarl *)> & lambda ) const

Execute a function on all top level sites.

◆ for_each_top_level_snarl_parallel()

void vg::SnarlManager::for_each_top_level_snarl_parallel ( const function< void(const Snarl *)> & lambda ) const

Execute a function on all top level sites in parallel.

◆ in_nontrivial_chain()

bool vg::SnarlManager::in_nontrivial_chain ( const Snarl * here ) const

Return true if a Snarl is part of a nontrivial chain of more than one snarl. Note that chain_of() still works for snarls in trivial chains.

◆ into_which_snarl() [1/2]

const Snarl * vg::SnarlManager::into_which_snarl ( const Visit & visit ) const

Returns the Snarl that a Visit points into. If the Visit contains a Snarl rather than a node ID, returns a pointer the managed version of that snarl.

◆ into_which_snarl() [2/2]

const Snarl * vg::SnarlManager::into_which_snarl	(	int64_t	id,
		bool	reverse
	)		const

Returns the Snarl that a traversal points into at either the start or end, or nullptr if the traversal does not point into any Snarl. Note that Snarls store the end Visit pointing out of rather than into the Snarl, so they must be reversed to query it.

◆ is_leaf()

bool vg::SnarlManager::is_leaf ( const Snarl * snarl ) const

Returns true if snarl has no children and false otherwise.

◆ is_root()

bool vg::SnarlManager::is_root ( const Snarl * snarl ) const

Returns true if snarl has no parent and false otherwise.

◆ is_trivial()

bool vg::SnarlManager::is_trivial	(	const Snarl *	snarl,
		const HandleGraph &	graph
	)		const

Returns true if the snarl is trivial (an ultrabubble with just the start and end nodes) and false otherwise. TODO: Implement without needing the vg graph, by adding a flag to trivial snarls.

◆ manage()

const Snarl * vg::SnarlManager::manage ( const Snarl & not_owned ) const

Given a Snarl that we don't own (like from a Visit), find the pointer to the managed copy of that Snarl.

◆ net_graph_of()

NetGraph vg::SnarlManager::net_graph_of	(	const Snarl *	snarl,
		const HandleGraph *	graph,
		bool	use_internal_connectivity = `true`
	)		const

Get the net graph of the given Snarl's contents, using the given backing HandleGraph. If use_internal_connectivity is false, each chain and unary child snarl is treated as an ordinary node which is assumed to be only traversable from one side to the other. Otherwise, traversing the graph works like it would if you actually went through the internal graphs fo child snarls.

◆ next_snarl()

Visit vg::SnarlManager::next_snarl ( const Visit & here ) const

private

Get a Visit to the snarl coming after the given Visit to a snarl, or a Visit with no Snarl no next snarl exists. Accounts for snarls' orientations.

◆ num_snarls()

int vg::SnarlManager::num_snarls ( ) const

Count snarls in deque<SnarlRecords>, a master list of snarls in graph.

◆ operator=() [1/2]

SnarlManager& vg::SnarlManager::operator= ( const SnarlManager & other )

delete

◆ operator=() [2/2]

SnarlManager& vg::SnarlManager::operator= ( SnarlManager && other )

default

◆ parent_of()

const Snarl * vg::SnarlManager::parent_of ( const Snarl * snarl ) const

Returns a pointer to the parent of a Snarl or nullptr if there is none.

◆ prev_snarl()

Visit vg::SnarlManager::prev_snarl ( const Visit & here ) const

private

Get a Visit to the snarl coming before the given Visit to a snarl, or a Visit with no Snarl no previous snarl exists. Accounts for snarls' orientations.

◆ record() [1/2]

const SnarlRecord* vg::SnarlManager::record ( const Snarl * snarl ) const

inlineprivate

Get the const SnarlRecord for a const managed snarl.

◆ record() [2/2]

SnarlRecord* vg::SnarlManager::record ( Snarl * snarl )

inlineprivate

Get the SnarlRecord for a managed snarl.

◆ regularize()

void vg::SnarlManager::regularize ( )

private

Modify the snarls and chains to enforce a couple of invariants:

The start node IDs of the snarls in a chain shall be unique.

(This is needed by the distance indexing code, which identifies child snarls by their start nodes. TODO: That distance indexing code needs to also work out unary snarls abitting the ends of chains, which may be allowed eventually.)

Snarls will be oriented forward in their chains.
Snarls will be oriented in a chain to maximize the number of snarls that start with lower node IDs than they end with.

Depends on the indexes from build_indexes() having been built.

◆ serialize()

void vg::SnarlManager::serialize ( ostream & out ) const

◆ shallow_contents()

pair< unordered_set< id_t >, unordered_set< edge_t > > vg::SnarlManager::shallow_contents	(	const Snarl *	snarl,
		const HandleGraph &	graph,
		bool	include_boundary_nodes
	)		const

Returns the Nodes and Edges contained in this Snarl but not in any child Snarls (always includes the Nodes that form the boundaries of child Snarls, optionally includes this Snarl's own boundary Nodes)

◆ snarl_boundary_index()

unordered_map< pair< int64_t, bool >, const Snarl * > vg::SnarlManager::snarl_boundary_index ( ) const

Returns a map from all Snarl boundaries to the Snarl they point into. Note that this means that end boundaries will be reversed.

◆ snarl_end_index()

unordered_map< pair< int64_t, bool >, const Snarl * > vg::SnarlManager::snarl_end_index ( ) const

Returns a map from all Snarl end boundaries to the Snarl they point into. Note that this means that end boundaries will be reversed.

◆ snarl_number()

size_t vg::SnarlManager::snarl_number ( const Snarl * snarl ) const

inline

Get the snarl number from the SnarlRecord* member with given snarl.

◆ snarl_sharing_end()

const Snarl * vg::SnarlManager::snarl_sharing_end ( const Snarl * here ) const

private

Get the Snarl, if any, that shares this Snarl's end node as either its start or its end. Does not count this snarl, even if this snarl is unary. Basic operation used to traverse a chain. Caller must account for snarls' orientations within a chain.

◆ snarl_sharing_start()

const Snarl * vg::SnarlManager::snarl_sharing_start ( const Snarl * here ) const

private

Get the Snarl, if any, that shares this Snarl's start node as either its start or its end. Does not count this snarl, even if this snarl is unary. Basic operation used to traverse a chain. Caller must account for snarls' orientations within a chain.

◆ snarl_start_index()

unordered_map< pair< int64_t, bool >, const Snarl * > vg::SnarlManager::snarl_start_index ( ) const

Returns a map from all Snarl start boundaries to the Snarl they point into.

◆ top_level_snarls()

const vector< const Snarl * > & vg::SnarlManager::top_level_snarls ( ) const

Returns a reference to a vector with the roots of the Snarl trees.

◆ translate_snarl_num()

const Snarl* vg::SnarlManager::translate_snarl_num ( size_t snarl_num )

inline

◆ unrecord() [1/2]

const Snarl* vg::SnarlManager::unrecord ( const SnarlRecord * record ) const

inlineprivate

Get the const Snarl owned by a const SnarlRecord.

◆ unrecord() [2/2]

Snarl* vg::SnarlManager::unrecord ( SnarlRecord * record )

inlineprivate

Get the Snarl owned by a SnarlRecord.

◆ visits_left()

vector< Visit > vg::SnarlManager::visits_left	(	const Visit &	visit,
		const HandleGraph &	graph,
		const Snarl *	in_snarl
	)		const

Look left from the given visit in the given graph and gets all the attached Visits to nodes or snarls.

◆ visits_right()

vector< Visit > vg::SnarlManager::visits_right	(	const Visit &	visit,
		const HandleGraph &	graph,
		const Snarl *	in_snarl
	)		const

Look left from the given visit in the given graph and gets all the attached Visits to nodes or snarls.

Member Data Documentation

◆ root_chains

deque<Chain> vg::SnarlManager::root_chains

private

Chains of root-level snarls. Uses a deque so Chain* pointers don't get invalidated.

◆ roots

vector<const Snarl*> vg::SnarlManager::roots

private

Roots of snarl trees.

◆ snarl_into

unordered_map<pair<int64_t, bool>, const Snarl*> vg::SnarlManager::snarl_into

private

Map of node traversals to the snarls they point into.

◆ snarls

deque<SnarlRecord> vg::SnarlManager::snarls

private

Master list of the snarls in the graph. Use a deque so pointers never get invalidated but we still have some locality.

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

src/snarls.hpp
src/snarls.cpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SnarlManager() [1/6]

◆ SnarlManager() [2/6]

◆ SnarlManager() [3/6]

◆ SnarlManager() [4/6]

◆ ~SnarlManager()

◆ SnarlManager() [5/6]

◆ SnarlManager() [6/6]

Member Function Documentation

◆ add_snarl()

◆ all_children_trivial()

◆ build_indexes()

◆ chain_of()

◆ chain_orientation_of()

◆ chain_rank_of()

◆ chains_of()

◆ children_of()

◆ compute_chains()

◆ deep_contents()

◆ discrete_uniform_sample()

◆ finish()

◆ flip() [1/2]

◆ flip() [2/2]

◆ for_each_chain()

◆ for_each_chain_parallel()

◆ for_each_snarl_parallel()

◆ for_each_snarl_preorder()

◆ for_each_snarl_unindexed()

◆ for_each_top_level_chain()

◆ for_each_top_level_chain_parallel()

◆ for_each_top_level_snarl()

◆ for_each_top_level_snarl_parallel()

◆ in_nontrivial_chain()

◆ into_which_snarl() [1/2]

◆ into_which_snarl() [2/2]

◆ is_leaf()

◆ is_root()

◆ is_trivial()

◆ manage()

◆ net_graph_of()

◆ next_snarl()

◆ num_snarls()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ parent_of()

◆ prev_snarl()

◆ record() [1/2]

◆ record() [2/2]

◆ regularize()

◆ serialize()

◆ shallow_contents()

◆ snarl_boundary_index()

◆ snarl_end_index()

◆ snarl_number()

◆ snarl_sharing_end()

◆ snarl_sharing_start()

◆ snarl_start_index()

◆ top_level_snarls()

◆ translate_snarl_num()

◆ unrecord() [1/2]

◆ unrecord() [2/2]

◆ visits_left()

◆ visits_right()

Member Data Documentation

◆ root_chains

◆ roots

◆ snarl_into

◆ snarls