vg::IntegratedSnarlFinder::MergedAdjacencyGraph Class Reference

Public Member Functions
	MergedAdjacencyGraph (const RankedHandleGraph *graph)
	Make a MergedAdjacencyGraph representing the graph of adjacency components of the given RankedHandleGraph. More...
	MergedAdjacencyGraph (const MergedAdjacencyGraph &other)
	Copy a MergedAdjacencyGraph by re-doing all the merges. Uses its own internal vectorization. More...
void	merge (handle_t into_a, handle_t into_b)
	Given handles reading into two components, a and b, merge them into a single component. More...
handle_t	find (handle_t into) const
	Find the handle heading the component that the given handle is in. More...
void	for_each_head (const function< void(handle_t)> &iteratee) const
	For each head, call the iteratee. More...
void	for_each_other_member (handle_t head, const function< void(handle_t)> &iteratee) const
void	for_each_member (handle_t head, const function< void(handle_t)> &iteratee) const
void	for_each_membership (const function< void(handle_t, handle_t)> &iteratee) const
pair< vector< pair< size_t, handle_t > >, unordered_map< handle_t, handle_t > >	cycles_in_cactus () const
vector< handle_t >	find_cycle_path_in_cactus (const unordered_map< handle_t, handle_t > &next_along_cycle, handle_t start_cactus_head, handle_t end_cactus_head) const
pair< vector< pair< size_t, vector< handle_t > > >, unordered_map< handle_t, handle_t > >	longest_paths_in_forest (const vector< pair< size_t, handle_t >> &longest_simple_cycles) const
void	to_dot (ostream &out) const
	Describe the graph in dot format to the given stream;. More...

Protected Member Functions
size_t	uf_rank (handle_t into) const
handle_t	uf_handle (size_t rank) const

Protected Attributes
const RankedHandleGraph *	graph
structures::UnionFind	union_find

Constructor & Destructor Documentation

MergedAdjacencyGraph() [1/2]

vg::IntegratedSnarlFinder::MergedAdjacencyGraph::MergedAdjacencyGraph

(

const RankedHandleGraph *

graph

)

Make a MergedAdjacencyGraph representing the graph of adjacency components of the given RankedHandleGraph.

MergedAdjacencyGraph() [2/2]

vg::IntegratedSnarlFinder::MergedAdjacencyGraph::MergedAdjacencyGraph

(

const MergedAdjacencyGraph &

other

)

Copy a MergedAdjacencyGraph by re-doing all the merges. Uses its own internal vectorization.

Member Function Documentation

cycles_in_cactus()

pair< vector< pair< size_t, handle_t > >, unordered_map< handle_t, handle_t > > vg::IntegratedSnarlFinder::MergedAdjacencyGraph::cycles_in_cactus

(

)

const

In a graph where all 3-edge-connected components have had their nodes merged, find all the cycles. Cycles are guaranteed to overlap at at most one node, so no special handling of overlapping regions is done.

Returns a list of cycle edge length (in bp) and an edge on each cycle (for the longest cycle in each connected component), and a map from each edge on the cycle to the next edge, going around each cycle in one direction (for all cycles).

Ignores self loops.

find()

handle_t vg::IntegratedSnarlFinder::MergedAdjacencyGraph::find

(

handle_t

into

)

const

Find the handle heading the component that the given handle is in.

find_cycle_path_in_cactus()

vector< handle_t > vg::IntegratedSnarlFinder::MergedAdjacencyGraph::find_cycle_path_in_cactus	(	const unordered_map< handle_t, handle_t > &	next_along_cycle,
		handle_t	start_cactus_head,
		handle_t	end_cactus_head
	)		const

Find a path of cycles connecting two components in a Cactus graph. Cycles are represented by the handle that brings that cyle into the component where it intersects the previous cycle. Because the graph is a Cactus graph, cycles are a tree and intersect at at most one node. Uses the given map of cycles, stored in one orientation only, to traverse cycles.

for_each_head()

void vg::IntegratedSnarlFinder::MergedAdjacencyGraph::for_each_head

(

const function< void(handle_t)> &

iteratee

)

const

For each head, call the iteratee.

for_each_member()

void vg::IntegratedSnarlFinder::MergedAdjacencyGraph::for_each_member	(	handle_t	head,
		const function< void(handle_t)> &	iteratee
	)		const

For each item, including the head, in the component headed by the given handle, calls the iteratee with the that other item. Does not call the iteratee for single-item components.

for_each_membership()

void vg::IntegratedSnarlFinder::MergedAdjacencyGraph::for_each_membership

(

const function< void(handle_t, handle_t)> &

iteratee

)

const

For each item other than the head in each component, calls the iteratee with the head and the other item. Does not call the iteratee for single-item components.

for_each_other_member()

void vg::IntegratedSnarlFinder::MergedAdjacencyGraph::for_each_other_member	(	handle_t	head,
		const function< void(handle_t)> &	iteratee
	)		const

For each item other than the head in the component headed by the given handle, calls the iteratee with the that other item. Does not call the iteratee for single-item components.

longest_paths_in_forest()

pair< vector< pair< size_t, vector< handle_t > > >, unordered_map< handle_t, handle_t > > vg::IntegratedSnarlFinder::MergedAdjacencyGraph::longest_paths_in_forest

(

const vector< pair< size_t, handle_t >> &

longest_simple_cycles

)

const

Return the path length (total edge length in bp) and edges for the longest path in each tree in a forest. Ignores self loops on tree nodes.

Also return the map from the head of each component to the edge into the child that is first along the longest path to a leaf. For components not themselves on the longest leaf-leaf path in their tree, these will always be dangling off/rooted by the longest leaf-leaf path or longest simple cycle merged away, whichever is longer.

Needs access to the longest simple cycles that were merged out, if any. If a path in the forest doesn't match or beat the length of the cycle that lives in its tree, it is omitted.

merge()

void vg::IntegratedSnarlFinder::MergedAdjacencyGraph::merge	(	handle_t	into_a,
		handle_t	into_b
	)

Given handles reading into two components, a and b, merge them into a single component.

to_dot()

void vg::IntegratedSnarlFinder::MergedAdjacencyGraph::to_dot

(

ostream &

out

)

const

Describe the graph in dot format to the given stream;.

uf_handle()

handle_t vg::IntegratedSnarlFinder::MergedAdjacencyGraph::uf_handle ( size_t  rank ) const

protected

Get the handle with the given rank in union-find space. Our ranks are 0-based.

uf_rank()

size_t vg::IntegratedSnarlFinder::MergedAdjacencyGraph::uf_rank ( handle_t  into ) const

protected

Get the rank corresponding to the given handle, in the union-find. Our ranks are 0-based.

Member Data Documentation

graph

const RankedHandleGraph* vg::IntegratedSnarlFinder::MergedAdjacencyGraph::graph

protected

Hold onto the backing RankedHandleGraph. Union find index is handle rank - 1 (to make it 0-based).

union_find

structures::UnionFind vg::IntegratedSnarlFinder::MergedAdjacencyGraph::union_find

mutableprotected

Keep a union-find over the ranks of the merged oriented handles that make up each component. Runs with include_children=true so we can find all the members of each group.

Needs to be mutable because union-find find operations do internal tree massaging and aren't const. TODO: this makes read operations not thread safe!

---

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

• src/integrated_snarl_finder.cpp