#include <traversal_finder.hpp>

Inheritance diagram for vg::RepresentativeTraversalFinder:

Public Member Functions
	RepresentativeTraversalFinder (const PathHandleGraph &graph, SnarlManager &snarl_manager, size_t max_depth, size_t max_width, size_t max_bubble_paths, size_t min_node_support=1, size_t min_edge_support=1, function< PathIndex *(const Snarl &)> get_index=[](const Snarl &s) { return nullptr;}, function< Support(id_t)> get_node_support=nullptr, function< Support(edge_t)> get_edge_support=nullptr)

virtual	~RepresentativeTraversalFinder ()=default

virtual vector< SnarlTraversal >	find_traversals (const Snarl &site)

Public Member Functions inherited from vg::TraversalFinder
virtual	~TraversalFinder ()=default

virtual vector< Traversal >	find_traversals (const handle_t &snarl_start, const handle_t &snarl_end)

Public Attributes
bool	verbose = false
	Should we emit verbose debugging info? More...

bool	eat_trivial_children = false
	Should trivial child snarls have their traversals glommed into ours? More...

size_t	other_orientation_timeout = 10

Protected Member Functions
Path	find_backbone (const Snarl &site)

pair< Support, vector< Visit > >	find_bubble (id_t node, const edge_t edge, const Snarl snarl, PathIndex &index, const Snarl &site)

Support	min_support_in_path (const list< Visit > &path)

set< tuple< size_t, bool, structures::ImmutableList< Visit > > >	bfs_left (Visit visit, PathIndex &index, bool stop_if_visited=false, const Snarl *in_snarl=nullptr, size_t both_orientations_distance=0)

set< tuple< size_t, bool, structures::ImmutableList< Visit > > >	bfs_right (Visit visit, PathIndex &index, bool stop_if_visited=false, const Snarl *in_snarl=nullptr, size_t both_orientations_distance=0)

size_t	bp_length (const structures::ImmutableList< Visit > &path)

Protected Attributes
const PathHandleGraph &	graph
	The annotated, augmented graph we're finding traversals in. More...

SnarlManager &	snarl_manager
	The SnarlManager managiung the snarls we use. More...

function< PathIndex *(const Snarl &)>	get_index

size_t	max_depth
	What DFS depth should we search to? More...

size_t	max_width
	How many DFS searches should we let there be on the stack at a time? More...

size_t	max_bubble_paths
	How many search intermediates can we allow? More...

size_t	min_node_support
	Minimum support for a node to consider travnersal through it. More...

size_t	min_edge_support
	Minimum support for a edge to consider travnersal through it. More...

bool	has_supports = false

function< Support(id_t)>	get_node_support

function< Support(edge_t)>	get_edge_support

Detailed Description

This TraversalFinder is derived from the old vg call code, and emits at least one traversal representing every node, and one traversal representing every edge.

Constructor & Destructor Documentation

◆ RepresentativeTraversalFinder()

vg::RepresentativeTraversalFinder::RepresentativeTraversalFinder	(	const PathHandleGraph &	graph,
		SnarlManager &	snarl_manager,
		size_t	max_depth,
		size_t	max_width,
		size_t	max_bubble_paths,
		size_t	min_node_support = `1`,
		size_t	min_edge_support = `1`,
		function< PathIndex *(const Snarl &)>	get_index = `[](const Snarl& s) { return nullptr; }`,
		function< Support(id_t)>	get_node_support = `nullptr`,
		function< Support(edge_t)>	get_edge_support = `nullptr`
	)

Make a new RepresentativeTraversalFinder to find traversals. Uses the given augmented graph as the graph with coverage annotation, and reasons about child snarls with the given SnarlManager. Explores up to max_depth in the BFS search when trying to find its way across snarls, and considers up to max_width search states at a time. When combining search results on either side of a graph element to be represented, thinks about max_bubble_paths combinations.

Uses the given get_index function to try and find a PathIndex for a reference path traversing a child snarl.

◆ ~RepresentativeTraversalFinder()

virtual vg::RepresentativeTraversalFinder::~RepresentativeTraversalFinder ( )

virtualdefault

Member Function Documentation

◆ bfs_left()

set< tuple< size_t, bool, structures::ImmutableList< Visit > > > vg::RepresentativeTraversalFinder::bfs_left	(	Visit	visit,
		PathIndex &	index,
		bool	stop_if_visited = `false`,
		const Snarl *	in_snarl = `nullptr`,
		size_t	both_orientations_distance = `0`
	)

protected

Do a breadth-first search left from the given node traversal, and return lengths, target-path-relative orientations, and paths starting at the given node and ending on the given indexed path. Refuses to visit nodes with no support, if support data is available in the augmented graph.

If in_snarl is not null, restricts the found paths to stay within the given snarl.

If both_orientations_distance is not zero, keeps searching up to that many steps after finding the target path to see if it can find a node on the target path in the opposite orientation. This is useful for inversions.

◆ bfs_right()

set< tuple< size_t, bool, structures::ImmutableList< Visit > > > vg::RepresentativeTraversalFinder::bfs_right	(	Visit	visit,
		PathIndex &	index,
		bool	stop_if_visited = `false`,
		const Snarl *	in_snarl = `nullptr`,
		size_t	both_orientations_distance = `0`
	)

protected

Do a breadth-first search right from the given node traversal, and return lengths, target-path-relative orientations, and paths starting at the given node and ending on the given indexed path. Refuses to visit nodes with no support, if support data is available in the augmented graph.

API is similar to bfs_left().

◆ bp_length()

size_t vg::RepresentativeTraversalFinder::bp_length ( const structures::ImmutableList< Visit > & path )

protected

Get the length of a path through nodes, in base pairs.

◆ find_backbone()

Path vg::RepresentativeTraversalFinder::find_backbone ( const Snarl & site )

protected

Find a Path that runs from the start of the given snarl to the end, which we can use to backend our traversals into when a snarl is off the primary path.

◆ find_bubble()

pair< Support, vector< Visit > > vg::RepresentativeTraversalFinder::find_bubble	(	id_t	node,
		const edge_t *	edge,
		const Snarl *	snarl,
		PathIndex &	index,
		const Snarl &	site
	)

protected

Given an edge or node in the augmented graph, look out from the edge or node or snarl in both directions to find a shortest bubble relative to the path, with a consistent orientation. The bubble may not visit the same node twice.

Exactly one of edge and node and snarl must be not null.

Takes a max depth for the searches producing the paths on each side.

Return the ordered and oriented nodes in the bubble, with the outer nodes being oriented forward along the path for which an index is provided, and with the first node coming before the last node in the reference. Also return the minimum support found on any edge or node in the bubble (including the reference node endpoints and their edges which aren't stored in the path).

◆ find_traversals()

vector< SnarlTraversal > vg::RepresentativeTraversalFinder::find_traversals ( const Snarl & site )

virtual

Find traversals to cover the nodes and edges of the snarl. Always emits the primary path traversal first, if applicable.

Implements vg::TraversalFinder.

◆ min_support_in_path()

Support vg::RepresentativeTraversalFinder::min_support_in_path ( const list< Visit > & path )

protected

Get the minimum support of all nodes and edges in path, in the path's forward orientation.

Member Data Documentation

◆ eat_trivial_children

bool vg::RepresentativeTraversalFinder::eat_trivial_children = false

Should trivial child snarls have their traversals glommed into ours?

◆ get_edge_support

function<Support(edge_t)> vg::RepresentativeTraversalFinder::get_edge_support

protected

◆ get_index

function<PathIndex*(const Snarl&)> vg::RepresentativeTraversalFinder::get_index

protected

We keep around a function that can be used to get an index for the appropriate path to use to scaffold a given site, or null if no appropriate index exists.

◆ get_node_support

function<Support(id_t)> vg::RepresentativeTraversalFinder::get_node_support

protected

◆ graph

const PathHandleGraph& vg::RepresentativeTraversalFinder::graph

protected

The annotated, augmented graph we're finding traversals in.

◆ has_supports

bool vg::RepresentativeTraversalFinder::has_supports = false

protected

Get support

◆ max_bubble_paths

size_t vg::RepresentativeTraversalFinder::max_bubble_paths

protected

How many search intermediates can we allow?

◆ max_depth

size_t vg::RepresentativeTraversalFinder::max_depth

protected

What DFS depth should we search to?

◆ max_width

size_t vg::RepresentativeTraversalFinder::max_width

protected

How many DFS searches should we let there be on the stack at a time?

◆ min_edge_support

size_t vg::RepresentativeTraversalFinder::min_edge_support

protected

Minimum support for a edge to consider travnersal through it.

◆ min_node_support

size_t vg::RepresentativeTraversalFinder::min_node_support

protected

Minimum support for a node to consider travnersal through it.

◆ other_orientation_timeout

size_t vg::RepresentativeTraversalFinder::other_orientation_timeout = 10

What timeout/step limit should we use for finding other orientations of the reference path after we find one?

◆ snarl_manager

SnarlManager& vg::RepresentativeTraversalFinder::snarl_manager

protected

The SnarlManager managiung the snarls we use.

◆ verbose

bool vg::RepresentativeTraversalFinder::verbose = false

Should we emit verbose debugging info?

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

src/traversal_finder.hpp
src/traversal_finder.cpp

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RepresentativeTraversalFinder()

◆ ~RepresentativeTraversalFinder()

Member Function Documentation

◆ bfs_left()

◆ bfs_right()

◆ bp_length()

◆ find_backbone()

◆ find_bubble()

◆ find_traversals()

◆ min_support_in_path()

Member Data Documentation

◆ eat_trivial_children

◆ get_edge_support

◆ get_index

◆ get_node_support

◆ graph

◆ has_supports

◆ max_bubble_paths

◆ max_depth

◆ max_width

◆ min_edge_support

◆ min_node_support

◆ other_orientation_timeout

◆ snarl_manager

◆ verbose