vg
tools for working with variation graphs
|
#include <flow_sort.hpp>
Classes | |
struct | Growth |
struct | WeightedGraph |
Public Member Functions | |
FlowSort (VG &vg) | |
std::unique_ptr< list< NodeTraversal > > | max_flow_sort (const string &ref_name, bool isGrooming=true) |
void | fast_linear_sort (const string &ref_name, bool isGrooming=true) |
void | flow_sort_nodes (list< NodeTraversal > &sorted_nodes, const string &ref_name, bool isGrooming) |
int | get_node_degree (WeightedGraph &wg, id_t node_id) |
void | update_in_out_edges (EdgeMapping &edges_in, EdgeMapping &edges_out, Edge *e) |
void | erase_in_out_edges (EdgeMapping &edges_in, EdgeMapping &edges_out, Edge *e) |
void | reverse_edge (Edge *&e) |
void | reverse_from_start_to_end_edge (Edge *&e) |
id_t | from_simple_reverse (Edge *&e) |
id_t | from_simple_reverse_orientation (Edge *&e) |
id_t | to_simple_reverse (Edge *&e) |
id_t | to_simple_reverse_orientation (Edge *&e) |
vector< set< id_t > > | get_cc_in_wg (EdgeMapping &edges_in, EdgeMapping &edges_out, const set< id_t > &all_nodes, id_t start_ref_node) |
void | groom_components (EdgeMapping &edges_in, EdgeMapping &edges_out, set< id_t > &isolated_nodes, set< id_t > &main_nodes, map< id_t, set< Edge * >> &minus_start, map< id_t, set< Edge * >> &minus_end) |
id_t | get_next_node_recalc_degrees (WeightedGraph &wg, std::vector< std::set< id_t >> °rees, std::set< id_t > &sources, id_t node) |
id_t | find_max_node (std::vector< std::set< id_t >> nodes_degree) |
bool | bfs (set< id_t > &nodes, map< id_t, map< id_t, int >> &edge_weight, id_t s, id_t t, map< id_t, id_t > &parent) |
void | dfs (set< id_t > &nodes, id_t s, set< id_t > &visited, map< id_t, map< id_t, int >> &edge_weight) |
void | find_in_out_web (list< NodeTraversal > &sorted_nodes, Growth &in_out_growth, WeightedGraph &weighted_graph, set< id_t > &unsorted_nodes, id_t start_node, bool in_out, int count) |
void | process_in_out_growth (EdgeMapping &edges_out_nodes, id_t current_id, Growth &in_out_growth, WeightedGraph &weighted_graph, set< id_t > &visited, list< NodeTraversal > &sorted_nodes, bool reverse, set< id_t > &unsorted_nodes, bool in_out, int count) |
void | mark_dfs (EdgeMapping &graph_matrix, id_t s, set< id_t > &new_nodes, set< id_t > &visited, bool reverse, set< id_t > &nodes, set< id_t > &backbone) |
vector< pair< id_t, id_t > > | min_cut (map< id_t, map< id_t, int >> &graph_weight, set< id_t > &nodes, id_t s, id_t t, EdgeMapping &edges_out_nodes, set< Edge * > &in_joins) |
void | remove_edge (EdgeMapping &nodes_to_edges, id_t node, id_t to, bool reverse) |
Static Public Attributes | |
static const size_t | DEFAULT_PATH_WEIGHT = 5 |
Private Attributes | |
VG & | vg |
vg::FlowSort::FlowSort | ( | VG & | vg | ) |
bool vg::FlowSort::bfs | ( | set< id_t > & | nodes, |
map< id_t, map< id_t, int >> & | edge_weight, | ||
id_t | s, | ||
id_t | t, | ||
map< id_t, id_t > & | parent | ||
) |
void vg::FlowSort::dfs | ( | set< id_t > & | nodes, |
id_t | s, | ||
set< id_t > & | visited, | ||
map< id_t, map< id_t, int >> & | edge_weight | ||
) |
void vg::FlowSort::erase_in_out_edges | ( | EdgeMapping & | edges_in, |
EdgeMapping & | edges_out, | ||
Edge * | e | ||
) |
void vg::FlowSort::fast_linear_sort | ( | const string & | ref_name, |
bool | isGrooming = true |
||
) |
void vg::FlowSort::find_in_out_web | ( | list< NodeTraversal > & | sorted_nodes, |
Growth & | in_out_growth, | ||
WeightedGraph & | weighted_graph, | ||
set< id_t > & | unsorted_nodes, | ||
id_t | start_node, | ||
bool | in_out, | ||
int | count | ||
) |
void vg::FlowSort::flow_sort_nodes | ( | list< NodeTraversal > & | sorted_nodes, |
const string & | ref_name, | ||
bool | isGrooming | ||
) |
vector< set< id_t > > vg::FlowSort::get_cc_in_wg | ( | EdgeMapping & | edges_in, |
EdgeMapping & | edges_out, | ||
const set< id_t > & | all_nodes, | ||
id_t | start_ref_node | ||
) |
id_t vg::FlowSort::get_next_node_recalc_degrees | ( | WeightedGraph & | wg, |
std::vector< std::set< id_t >> & | degrees, | ||
std::set< id_t > & | sources, | ||
id_t | node | ||
) |
int vg::FlowSort::get_node_degree | ( | FlowSort::WeightedGraph & | wg, |
id_t | node_id | ||
) |
void vg::FlowSort::groom_components | ( | EdgeMapping & | edges_in, |
EdgeMapping & | edges_out, | ||
set< id_t > & | isolated_nodes, | ||
set< id_t > & | main_nodes, | ||
map< id_t, set< Edge * >> & | minus_start, | ||
map< id_t, set< Edge * >> & | minus_end | ||
) |
void vg::FlowSort::mark_dfs | ( | EdgeMapping & | graph_matrix, |
id_t | s, | ||
set< id_t > & | new_nodes, | ||
set< id_t > & | visited, | ||
bool | reverse, | ||
set< id_t > & | nodes, | ||
set< id_t > & | backbone | ||
) |
std::unique_ptr< list< NodeTraversal > > vg::FlowSort::max_flow_sort | ( | const string & | ref_name, |
bool | isGrooming = true |
||
) |
vector< pair< id_t, id_t > > vg::FlowSort::min_cut | ( | map< id_t, map< id_t, int >> & | graph_weight, |
set< id_t > & | nodes, | ||
id_t | s, | ||
id_t | t, | ||
EdgeMapping & | edges_out_nodes, | ||
set< Edge * > & | in_joins | ||
) |
void vg::FlowSort::process_in_out_growth | ( | EdgeMapping & | edges_out_nodes, |
id_t | current_id, | ||
Growth & | in_out_growth, | ||
WeightedGraph & | weighted_graph, | ||
set< id_t > & | visited, | ||
list< NodeTraversal > & | sorted_nodes, | ||
bool | reverse, | ||
set< id_t > & | unsorted_nodes, | ||
bool | in_out, | ||
int | count | ||
) |
void vg::FlowSort::remove_edge | ( | EdgeMapping & | nodes_to_edges, |
id_t | node, | ||
id_t | to, | ||
bool | reverse | ||
) |
void vg::FlowSort::reverse_edge | ( | Edge *& | e | ) |
void vg::FlowSort::reverse_from_start_to_end_edge | ( | Edge *& | e | ) |
void vg::FlowSort::update_in_out_edges | ( | EdgeMapping & | edges_in, |
EdgeMapping & | edges_out, | ||
Edge * | e | ||
) |
|
static |
|
private |