vg
tools for working with variation graphs
Classes | Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes | List of all members
bdsg::ODGI Class Reference

#include <odgi.hpp>

Inheritance diagram for bdsg::ODGI:
handlegraph::MutablePathDeletableHandleGraph handlegraph::SerializableHandleGraph handlegraph::MutablePathMutableHandleGraph handlegraph::DeletableHandleGraph handlegraph::MutablePathHandleGraph handlegraph::MutableHandleGraph handlegraph::MutableHandleGraph handlegraph::PathHandleGraph handlegraph::HandleGraph handlegraph::HandleGraph handlegraph::HandleGraph

Classes

struct  edge_helper
 
struct  path_metadata_t
 

Public Member Functions

 ODGI (void)
 
 ~ODGI (void)
 
uint32_t get_magic_number () const
 Return a high-entropy number to indicate which handle graph implementation this is. More...
 
bool has_node (nid_t node_id) const
 Method to check if a node exists by ID. More...
 
handle_t get_handle (const nid_t &node_id, bool is_reverse=false) const
 Look up the handle for the node with the given ID in the given orientation. More...
 
nid_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...
 
std::string get_sequence (const handle_t &handle) const
 Get the sequence of a node, presented in the handle's local forward orientation. More...
 
size_t get_node_count (void) const
 
nid_t min_node_id (void) const
 
nid_t max_node_id (void) const
 
void set_id_increment (const nid_t &min_id)
 set the id increment, used when the graph starts at a high id to reduce loading costs More...
 
void increment_node_ids (nid_t increment)
 Add the given value to all node IDs. More...
 
void reassign_node_ids (const std::function< nid_t(const nid_t &)> &get_new_id)
 Reassign all node IDs as specified by the old->new mapping function. More...
 
size_t get_degree (const handle_t &handle, bool go_left) 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
 
bool has_path (const std::string &path_name) const
 Determine if a path name exists and is legal to get a path handle for. More...
 
path_handle_t get_path_handle (const std::string &path_name) const
 
std::string get_path_name (const path_handle_t &path_handle) const
 Look up the name of a path from a handle to it. More...
 
size_t get_step_count (const path_handle_t &path_handle) const
 Returns the number of node steps in the path. More...
 
size_t get_path_count (void) const
 Returns the number of paths stored in the graph. More...
 
std::vector< step_handle_tsteps_of_handle (const handle_t &handle, bool match_orientation=false) const
 
size_t get_step_count (const handle_t &handle) const
 Returns the number of node steps on the handle. More...
 
handle_t get_handle_of_step (const step_handle_t &step_handle) const
 Get a node handle (node ID and orientation) from a handle to an step on a path. More...
 
step_handle_t path_begin (const path_handle_t &path_handle) const
 
step_handle_t path_end (const path_handle_t &path_handle) const
 Get a handle to a fictitious handle one past the end of the path. More...
 
step_handle_t path_back (const path_handle_t &path_handle) const
 Get a handle to the last step, which is arbitrary in the case of a circular path. More...
 
step_handle_t path_front_end (const path_handle_t &path_handle) const
 Get a handle to a fictitious handle one past the start of the path. More...
 
bool is_path_front_end (const step_handle_t &step_handle) const
 Returns true if the step handle is a front end magic handle. More...
 
bool is_path_end (const step_handle_t &step_handle) const
 Returns true if the step handle is an end magic handle. More...
 
bool has_next_step (const step_handle_t &step_handle) const
 Returns true if the step has a next step on the path, else false. More...
 
bool has_previous_step (const step_handle_t &step_handle) const
 Returns true if the step has a previous step on the path, else false. More...
 
step_handle_t get_next_step (const step_handle_t &step_handle) const
 Returns a handle to the next step on the path. More...
 
step_handle_t get_previous_step (const step_handle_t &step_handle) const
 Returns a handle to the previous step on the path. More...
 
path_handle_t get_path_handle_of_step (const step_handle_t &step_handle) const
 Returns a handle to the path that a step is on. More...
 
bool is_empty (const path_handle_t &path_handle) const
 Returns true if the given path is empty, and false otherwise. More...
 
void for_each_step_in_path (const path_handle_t &path, const std::function< void(const step_handle_t &)> &iteratee) const
 Loop over all the steps along a path, from first through last. More...
 
bool get_is_circular (const path_handle_t &path_handle) const
 Returns true if the path is circular. More...
 
void set_circularity (const path_handle_t &path_handle, bool circular)
 Set if the path is circular or not. More...
 
handle_t create_handle (const std::string &sequence)
 Create a new node with the given sequence and return the handle. More...
 
handle_t create_handle (const std::string &sequence, const nid_t &id)
 Create a new node with the given id and sequence, then return the handle. More...
 
handle_t create_hidden_handle (const std::string &sequence)
 
void destroy_handle (const handle_t &handle)
 
void create_edge (const handle_t &left, const handle_t &right)
 
bool has_edge (const handle_t &left, const handle_t &right) const
 Check if an edge exists. More...
 
void create_edge (const edge_t &edge)
 Convenient wrapper for create_edge. More...
 
void destroy_edge (const handle_t &left, const handle_t &right)
 
void destroy_edge (const edge_t &edge)
 Convenient wrapper for destroy_edge. More...
 
void clear (void)
 Remove all nodes, edges, and paths. More...
 
void clear_paths (void)
 Remove all stored paths. More...
 
void swap_handles (const handle_t &a, const handle_t &b)
 
void apply_ordering (const std::vector< handle_t > &order, bool compact_ids=false)
 
void optimize (bool allow_id_reassignment=true)
 Organize the graph for better performance and memory use. More...
 
void apply_path_ordering (const std::vector< path_handle_t > &order)
 Reorder the graph's paths as given. More...
 
handle_t apply_orientation (const handle_t &handle)
 
std::vector< handle_tdivide_handle (const handle_t &handle, const std::vector< size_t > &offsets)
 
std::pair< handle_t, handle_tdivide_handle (const handle_t &handle, size_t offset)
 Specialization of divide_handle for a single division point. More...
 
handle_t combine_handles (const std::vector< handle_t > &handles)
 
void destroy_path (const path_handle_t &path)
 
path_handle_t create_path_handle (const std::string &name, bool is_circular=false)
 
step_handle_t prepend_step (const path_handle_t &path, const handle_t &to_append)
 
step_handle_t append_step (const path_handle_t &path, const handle_t &to_append)
 
step_handle_t insert_step (const step_handle_t &before, const step_handle_t &after, const handle_t &to_insert)
 
step_handle_t set_step (const step_handle_t &step_handle, const handle_t &handle)
 Set the step to the given handle, possibly re-linking and cleaning up if needed. More...
 
std::pair< step_handle_t, step_handle_trewrite_segment (const step_handle_t &segment_begin, const step_handle_t &segment_end, const std::vector< handle_t > &new_segment)
 Replace the path range with the new segment. More...
 
void display (void) const
 A helper function to visualize the state of the graph. More...
 
void to_gfa (std::ostream &out) const
 Convert to GFA (for debugging) More...
 
void to_gfa (const string &filename) const
 Convert to GFA and send to the given filename, or "-" for standard output (the default). More...
 
string to_gfa () const
 Convert to GFA and return as a string. More...
 
long long int serialize_and_measure (std::ostream &out) const
 
void load (std::istream &in)
 Load. More...
 
- Public Member Functions inherited from handlegraph::MutablePathDeletableHandleGraph
virtual ~MutablePathDeletableHandleGraph ()=default
 
- Public Member Functions inherited from handlegraph::MutablePathMutableHandleGraph
virtual ~MutablePathMutableHandleGraph ()=default
 
- Public Member Functions inherited from handlegraph::MutablePathHandleGraph
virtual ~MutablePathHandleGraph ()=default
 
- Public Member Functions inherited from handlegraph::PathHandleGraph
virtual ~PathHandleGraph ()=default
 
template<typename Iteratee >
bool for_each_path_handle (const Iteratee &iteratee) const
 
template<typename Iteratee >
bool for_each_step_on_handle (const handle_t &handle, const Iteratee &iteratee) const
 
PathForEachSocket scan_path (const path_handle_t &path) const
 
template<typename Iteratee >
bool for_each_step_in_path (const path_handle_t &path, const Iteratee &iteratee) const
 
- 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
 
bool has_edge (const edge_t &edge) const
 Convenient wrapper of has_edge for edge_t argument. More...
 
virtual size_t get_edge_count () const
 
virtual size_t get_total_length () const
 
virtual char get_base (const handle_t &handle, size_t index) const
 
virtual std::string get_subsequence (const handle_t &handle, size_t index, size_t size) 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
 
- Public Member Functions inherited from handlegraph::MutableHandleGraph
virtual ~MutableHandleGraph ()=default
 
void create_edge (const edge_t &edge)
 Convenient wrapper for create_edge. More...
 
std::pair< handle_t, handle_tdivide_handle (const handle_t &handle, size_t offset)
 Specialization of divide_handle for a single division point. More...
 
- Public Member Functions inherited from handlegraph::DeletableHandleGraph
virtual ~DeletableHandleGraph ()=default
 
void destroy_edge (const edge_t &edge)
 Convenient wrapper for destroy_edge. More...
 
- Public Member Functions inherited from handlegraph::SerializableHandleGraph
virtual ~SerializableHandleGraph ()=default
 
void serialize (std::ostream &out) const
 
void serialize (const std::string &filename) const
 
void deserialize (std::istream &in)
 
void deserialize (const std::string &filename)
 

Protected Member Functions

bool follow_edges_impl (const handle_t &handle, bool go_left, const std::function< bool(const handle_t &)> &iteratee) const
 
bool for_each_handle_impl (const std::function< bool(const handle_t &)> &iteratee, bool parallel=false) const
 
bool for_each_path_handle_impl (const std::function< bool(const path_handle_t &)> &iteratee) const
 Execute a function on each path in the graph. More...
 
bool for_each_step_on_handle_impl (const handle_t &handle, const std::function< bool(const step_handle_t &)> &iteratee) const
 Enumerate the path steps on a given handle (strand agnostic) More...
 
bool has_linear_next_step (const step_handle_t &step_handle) const
 Returns true if the step has a next step on the path that doesn't wrap around, else false. More...
 
bool has_linear_previous_step (const step_handle_t &step_handle) const
 Returns true if the step has a previous step on the path that doesn't wrap around, else false. More...
 

Private Member Functions

void serialize_members (std::ostream &out) const
 Serialization that implements the inherited "serialze" method. More...
 
void deserialize_members (std::istream &in)
 Deserialization that implements the inherited "deserialze" method. More...
 
void canonicalize_edge (handle_t &left, handle_t &right) const
 
uint64_t edge_delta_to_id (uint64_t left, uint64_t delta) const
 Helper to convert between edge storage and actual id. More...
 
uint64_t edge_to_delta (const handle_t &left, const handle_t &right) const
 Helper to convert between ids and stored edge. More...
 
void destroy_path_handle_records (uint64_t i)
 Helper to simplify removal of path handle records. More...
 
step_handle_t create_step (const path_handle_t &path, const handle_t &handle)
 Helper to create the internal records for the step. More...
 
void destroy_step (const step_handle_t &step_handle, bool clean_up_empty_path=true)
 Helper to destroy the internal records for the step. More...
 
void link_steps (const step_handle_t &from, const step_handle_t &to)
 Helper to stitch up partially built paths. More...
 
void decrement_rank (const step_handle_t &step_handle)
 Decrement the step rank references for this step. More...
 
void set_handle_of_step (step_handle_t &step_handle, const handle_t &handle) const
 Modify the given step handle to point to the given handle. More...
 
path_metadata_tfind_metadata (const path_handle_t &path)
 Find the path metadata for a path. More...
 
const path_metadata_tfind_metadata (const path_handle_t &path) const
 Find the metadata for a path, read-only. More...
 
size_t path_to_rank (const path_handle_t &path) const
 Get the 0-based rank encoded by a path handle. More...
 
path_handle_t rank_to_path (size_t rank) const
 Get the path handle encoding the given 0-based rank. More...
 
handle_t add_to_number (const handle_t &handle, int64_t offset) const
 
void set_handle_sequence (const handle_t &handle, const std::string &seq)
 Compact away the deleted nodes info. More...
 
uint64_t id_to_rank (const nid_t &node_id) const
 get the backing node rank for a given node id More...
 
nid_t rank_to_id (const uint64_t &rank) const
 get the node id for the node with the given backing rank More...
 

Private Attributes

std::vector< node_t > node_v
 These are the backing data structures that we use to fulfill the above functions. More...
 
suc_bv deleted_node_bv
 Mark deleted nodes here for translating graph ids into internal ranks. More...
 
uint64_t _deleted_node_count = 0
 
uint64_t _max_node_rank = 0
 
uint64_t _min_node_rank = std::numeric_limits<decltype(_min_node_rank)>::max()
 
nid_t _id_increment = 1
 
hash_set< nid_tgraph_id_hidden_set
 
std::vector< path_metadata_tpath_metadata_v
 maps between path identifier and the start, end, and length of the path More...
 
string_hash_map< std::string, path_handle_tpath_name_map
 Links path names to handles. More...
 
uint64_t _node_count = 0
 A helper to record the number of live nodes. More...
 
uint64_t _edge_count = 0
 A helper to record the number of live edges. More...
 
uint64_t _path_count = 0
 A helper to record the number of live paths. More...
 
uint64_t _path_rank_next = 0
 A helper to record the next path rank to use (path deletions are hard because of our path FM-index) More...
 

Detailed Description

ODGI (Optimized Dynamic Graph Index) is a good all-around HandleGraph implementation. It represents nodes as C++ objects stored in a vector, but aggressively bit-packs and delta-compresses edge and path step information within each node. Using separate node objects can reduce the need for defragmentation as in PackedGraph, but some deletion operations are still lazy.

ODGI is a good implementation to choose if you don't need your graph to be as small as PackedGraph or as fast to access as HashGraph.

Constructor & Destructor Documentation

◆ ODGI()

bdsg::ODGI::ODGI ( void  )
inline

◆ ~ODGI()

bdsg::ODGI::~ODGI ( void  )
inline

Member Function Documentation

◆ add_to_number()

handle_t bdsg::ODGI::add_to_number ( const handle_t handle,
int64_t  offset 
) const
private

Add the offset to the number packed in the given handle, and return a new modified handle.

◆ append_step()

step_handle_t bdsg::ODGI::append_step ( const path_handle_t path,
const handle_t to_append 
)
virtual

Append a visit to a node to the given path. Returns a handle to the new final step on the path which is appended. Handles to prior steps on the path, and to other paths, must remain valid.

Implements handlegraph::MutablePathHandleGraph.

◆ apply_ordering()

void bdsg::ODGI::apply_ordering ( const std::vector< handle_t > &  order_in,
bool  compact_ids = false 
)
virtual

Reorder the graph's internal structure to match that given. Optionally compact the id space of the graph to match the ordering, from 1->|ordering|.

Implements handlegraph::MutableHandleGraph.

◆ apply_orientation()

handle_t bdsg::ODGI::apply_orientation ( const handle_t handle)
virtual

Alter the node that the given handle corresponds to so the orientation indicated by the handle becomes the node's local forward orientation. Rewrites all edges pointing to the node and the node's sequence to reflect this. Invalidates all handles to the node (including the one passed). Returns a new, valid handle to the node in its new forward orientation. Note that it is possible for the node's ID to change. Updates all stored paths. May change the ordering of the underlying graph.

Implements handlegraph::MutableHandleGraph.

◆ apply_path_ordering()

void bdsg::ODGI::apply_path_ordering ( const std::vector< path_handle_t > &  order)

Reorder the graph's paths as given.

◆ canonicalize_edge()

void bdsg::ODGI::canonicalize_edge ( handle_t left,
handle_t right 
) const
inlineprivate

◆ clear()

void bdsg::ODGI::clear ( void  )
virtual

Remove all nodes, edges, and paths.

Implements handlegraph::DeletableHandleGraph.

◆ clear_paths()

void bdsg::ODGI::clear_paths ( void  )

Remove all stored paths.

◆ combine_handles()

handle_t bdsg::ODGI::combine_handles ( const std::vector< handle_t > &  handles)

◆ create_edge() [1/2]

void bdsg::ODGI::create_edge ( const edge_t edge)
inline

Convenient wrapper for create_edge.

◆ create_edge() [2/2]

void bdsg::ODGI::create_edge ( const handle_t left_h,
const handle_t right_h 
)
virtual

Create an edge connecting the given handles in the given order and orientations. Ignores existing edges.

Implements handlegraph::MutableHandleGraph.

◆ create_handle() [1/2]

handle_t bdsg::ODGI::create_handle ( const std::string &  sequence)
virtual

Create a new node with the given sequence and return the handle.

Create a new node with the given sequence and return the handle. The sequence may not be empty.

Implements handlegraph::MutableHandleGraph.

◆ create_handle() [2/2]

handle_t bdsg::ODGI::create_handle ( const std::string &  sequence,
const nid_t id 
)
virtual

Create a new node with the given id and sequence, then return the handle.

Create a new node with the given id and sequence, then return the handle. The sequence may not be empty. The ID must be strictly greater than 0.

Implements handlegraph::MutableHandleGraph.

◆ create_hidden_handle()

handle_t bdsg::ODGI::create_hidden_handle ( const std::string &  sequence)

Create a node that is immediately "hidden" (i.e. to be used for parts of paths that traversed deleted portions of the graph). has_node for the ID of a hidden handle will return false. Also, no edges may be added to it.

◆ create_path_handle()

path_handle_t bdsg::ODGI::create_path_handle ( const std::string &  name,
bool  is_circular = false 
)
virtual

Create a path with the given name. The caller must ensure that no path with the given name exists already, or the behavior is undefined. Returns a handle to the created empty path. Handles to other paths must remain valid.

Implements handlegraph::MutablePathHandleGraph.

◆ create_step()

step_handle_t bdsg::ODGI::create_step ( const path_handle_t path,
const handle_t handle 
)
private

Helper to create the internal records for the step.

◆ decrement_rank()

void bdsg::ODGI::decrement_rank ( const step_handle_t step_handle)
private

Decrement the step rank references for this step.

helper to handle the case where we remove an step from a given path on a node that has other steps from the same path, thus invalidating the ranks used to refer to it

◆ deserialize_members()

void bdsg::ODGI::deserialize_members ( std::istream &  in)
privatevirtual

Deserialization that implements the inherited "deserialze" method.

Implements handlegraph::SerializableHandleGraph.

◆ destroy_edge() [1/2]

void bdsg::ODGI::destroy_edge ( const edge_t edge)
inline

Convenient wrapper for destroy_edge.

◆ destroy_edge() [2/2]

void bdsg::ODGI::destroy_edge ( const handle_t left_h,
const handle_t right_h 
)
virtual

Remove the edge connecting the given handles in the given order and orientations. Ignores nonexistent edges. Does not update any stored paths.

Implements handlegraph::DeletableHandleGraph.

◆ destroy_handle()

void bdsg::ODGI::destroy_handle ( const handle_t handle)
virtual

Remove the node belonging to the given handle and all of its edges. If any paths visit it, it becomes a "hidden" node accessible only via the paths. Invalidates the destroyed handle. May be called during serial for_each_handle iteration ONLY on the node being iterated. May NOT be called during parallel for_each_handle iteration. May NOT be called on the node from which edges are being followed during follow_edges.

Remove the node belonging to the given handle and all of its edges. If any paths visit it, it becomes a "hidden" node accessible only via the paths.

Implements handlegraph::DeletableHandleGraph.

◆ destroy_path()

void bdsg::ODGI::destroy_path ( const path_handle_t path)
virtual

This is the interface for a handle graph with embedded paths where the paths can be modified. Note that if the graph can also be modified, the implementation will also need to inherit from MutableHandleGraph, via the combination MutablePathMutableHandleGraph interface. TODO: This is a very limited interface at the moment. It will probably need to be extended. Destroy the given path. Invalidates handles to the path and its node steps.

Destroy the given path. Invalidates handles to the path and its node steps.

Implements handlegraph::MutablePathHandleGraph.

◆ destroy_path_handle_records()

void bdsg::ODGI::destroy_path_handle_records ( uint64_t  i)
private

Helper to simplify removal of path handle records.

◆ destroy_step()

void bdsg::ODGI::destroy_step ( const step_handle_t step_handle,
bool  clean_up_empty_path = true 
)
private

Helper to destroy the internal records for the step.

◆ display()

void bdsg::ODGI::display ( void  ) const

A helper function to visualize the state of the graph.

Ordered across the nodes in graph_id_iv, stores the path ids (1-based) at each segment in seq_wt, delimited by 0, one for each path step (node traversal).

Stores path names in their internal order, delimited by '$'

Marks the beginning of each path name

◆ divide_handle() [1/2]

std::vector< handle_t > bdsg::ODGI::divide_handle ( const handle_t handle,
const std::vector< size_t > &  offsets 
)
virtual

Split a handle's underlying node at the given offsets in the handle's orientation. Returns all of the handles to the parts. Other handles to the node being split may be invalidated. The split pieces stay in the same local forward orientation as the original node, but the returned handles come in the order and orientation appropriate for the handle passed in. Updates stored paths.

Implements handlegraph::MutableHandleGraph.

◆ divide_handle() [2/2]

std::pair<handle_t, handle_t> bdsg::ODGI::divide_handle ( const handle_t handle,
size_t  offset 
)
inline

Specialization of divide_handle for a single division point.

◆ edge_delta_to_id()

uint64_t bdsg::ODGI::edge_delta_to_id ( uint64_t  left,
uint64_t  delta 
) const
private

Helper to convert between edge storage and actual id.

◆ edge_handle()

edge_t bdsg::ODGI::edge_handle ( const handle_t left,
const handle_t right 
) const

A pair of handles can be used as an edge. When so used, the handles have a canonical order and orientation.

◆ edge_to_delta()

uint64_t bdsg::ODGI::edge_to_delta ( const handle_t left,
const handle_t right 
) const
private

Helper to convert between ids and stored edge.

◆ find_metadata() [1/2]

ODGI::path_metadata_t & bdsg::ODGI::find_metadata ( const path_handle_t path)
private

Find the path metadata for a path.

◆ find_metadata() [2/2]

const ODGI::path_metadata_t & bdsg::ODGI::find_metadata ( const path_handle_t path) const
private

Find the metadata for a path, read-only.

◆ flip()

handle_t bdsg::ODGI::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 bdsg::ODGI::follow_edges_impl ( const handle_t handle,
bool  go_left,
const std::function< bool(const handle_t &)> &  iteratee 
) const
protectedvirtual

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.

Implements handlegraph::HandleGraph.

◆ for_each_handle_impl()

bool bdsg::ODGI::for_each_handle_impl ( const std::function< bool(const handle_t &)> &  iteratee,
bool  parallel = false 
) const
protectedvirtual

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.

Implements handlegraph::HandleGraph.

◆ for_each_path_handle_impl()

bool bdsg::ODGI::for_each_path_handle_impl ( const std::function< bool(const path_handle_t &)> &  iteratee) const
protectedvirtual

Execute a function on each path in the graph.

Implements handlegraph::PathHandleGraph.

◆ for_each_step_in_path()

void bdsg::ODGI::for_each_step_in_path ( const path_handle_t path,
const std::function< void(const step_handle_t &)> &  iteratee 
) const

Loop over all the steps along a path, from first through last.

This is the interface for a handle graph that supports modification.

◆ for_each_step_on_handle_impl()

bool bdsg::ODGI::for_each_step_on_handle_impl ( const handle_t handle,
const std::function< bool(const step_handle_t &)> &  iteratee 
) const
protectedvirtual

Enumerate the path steps on a given handle (strand agnostic)

Implements handlegraph::PathHandleGraph.

◆ forward()

handle_t bdsg::ODGI::forward ( const handle_t handle) const

Get the locally forward version of a handle.

◆ get_degree()

size_t bdsg::ODGI::get_degree ( const handle_t handle,
bool  go_left 
) const
virtual

Get a handle from a Visit Protobuf object. Must be using'd to avoid shadowing. 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.

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_handle()

handle_t bdsg::ODGI::get_handle ( const nid_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_handle_of_step()

handle_t bdsg::ODGI::get_handle_of_step ( const step_handle_t step_handle) const
virtual

Get a node handle (node ID and orientation) from a handle to an step on a path.

Implements handlegraph::PathHandleGraph.

◆ get_id()

nid_t bdsg::ODGI::get_id ( const handle_t handle) const
virtual

Get the ID from a handle.

Implements handlegraph::HandleGraph.

◆ get_is_circular()

bool bdsg::ODGI::get_is_circular ( const path_handle_t path_handle) const
virtual

Returns true if the path is circular.

is the path circular

Implements handlegraph::PathHandleGraph.

◆ get_is_reverse()

bool bdsg::ODGI::get_is_reverse ( const handle_t handle) const
virtual

Get the orientation of a handle.

Implements handlegraph::HandleGraph.

◆ get_length()

size_t bdsg::ODGI::get_length ( const handle_t handle) const
virtual

Get the length of a node.

Implements handlegraph::HandleGraph.

◆ get_magic_number()

uint32_t bdsg::ODGI::get_magic_number ( ) const
virtual

Return a high-entropy number to indicate which handle graph implementation this is.

Implements handlegraph::SerializableHandleGraph.

◆ get_next_step()

step_handle_t bdsg::ODGI::get_next_step ( const step_handle_t step_handle) const
virtual

Returns a handle to the next step on the path.

Returns a handle to the next step on the path Returns the forward end iterator if none exists

Implements handlegraph::PathHandleGraph.

◆ get_node_count()

size_t bdsg::ODGI::get_node_count ( void  ) const
virtual

Return the number of nodes in the graph TODO: can't be node_count because XG has a field named node_count.

Return the number of nodes in the graph. Doesn't count deleted or hidden nodes. TODO: can't be node_count because XG has a field named node_count.

Implements handlegraph::HandleGraph.

◆ get_path_count()

size_t bdsg::ODGI::get_path_count ( void  ) const
virtual

Returns the number of paths stored in the graph.

Implements handlegraph::PathHandleGraph.

◆ get_path_handle()

path_handle_t bdsg::ODGI::get_path_handle ( const std::string &  path_name) const
virtual

Look up the path handle for the given path name. The path with that name must exist.

Implements handlegraph::PathHandleGraph.

◆ get_path_handle_of_step()

path_handle_t bdsg::ODGI::get_path_handle_of_step ( const step_handle_t step_handle) const
virtual

Returns a handle to the path that a step is on.

Implements handlegraph::PathHandleGraph.

◆ get_path_name()

std::string bdsg::ODGI::get_path_name ( const path_handle_t path_handle) const
virtual

Look up the name of a path from a handle to it.

Implements handlegraph::PathHandleGraph.

◆ get_previous_step()

step_handle_t bdsg::ODGI::get_previous_step ( const step_handle_t step_handle) const
virtual

Returns a handle to the previous step on the path.

Implements handlegraph::PathHandleGraph.

◆ get_sequence()

std::string bdsg::ODGI::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_step_count() [1/2]

size_t bdsg::ODGI::get_step_count ( const handle_t handle) const

Returns the number of node steps on the handle.

◆ get_step_count() [2/2]

size_t bdsg::ODGI::get_step_count ( const path_handle_t path_handle) const
virtual

Returns the number of node steps in the path.

Implements handlegraph::PathHandleGraph.

◆ has_edge()

bool bdsg::ODGI::has_edge ( const handle_t left,
const handle_t right 
) const
virtual

Check if an edge exists.

Reimplemented from handlegraph::HandleGraph.

◆ has_linear_next_step()

bool bdsg::ODGI::has_linear_next_step ( const step_handle_t step_handle) const
protected

Returns true if the step has a next step on the path that doesn't wrap around, else false.

◆ has_linear_previous_step()

bool bdsg::ODGI::has_linear_previous_step ( const step_handle_t step_handle) const
protected

Returns true if the step has a previous step on the path that doesn't wrap around, else false.

◆ has_next_step()

bool bdsg::ODGI::has_next_step ( const step_handle_t step_handle) const
virtual

Returns true if the step has a next step on the path, else false.

Implements handlegraph::PathHandleGraph.

◆ has_node()

bool bdsg::ODGI::has_node ( nid_t  node_id) const
virtual

Method to check if a node exists by ID.

Implements handlegraph::HandleGraph.

◆ has_path()

bool bdsg::ODGI::has_path ( const std::string &  path_name) const
virtual

Determine if a path name exists and is legal to get a path handle for.

This is the interface for a handle graph that stores embedded paths.

Implements handlegraph::PathHandleGraph.

◆ has_previous_step()

bool bdsg::ODGI::has_previous_step ( const step_handle_t step_handle) const
virtual

Returns true if the step has a previous step on the path, else false.

Implements handlegraph::PathHandleGraph.

◆ id_to_rank()

uint64_t bdsg::ODGI::id_to_rank ( const nid_t node_id) const
private

get the backing node rank for a given node id

◆ increment_node_ids()

void bdsg::ODGI::increment_node_ids ( nid_t  increment)
virtual

Add the given value to all node IDs.

Reimplemented from handlegraph::MutableHandleGraph.

◆ insert_step()

step_handle_t bdsg::ODGI::insert_step ( const step_handle_t before,
const step_handle_t after,
const handle_t to_insert 
)

Insert a visit to a node to the given path between the given steps. Returns a handle to the new step on the path which is appended. Handles to prior steps on the path, and to other paths, must remain valid.

◆ is_empty()

bool bdsg::ODGI::is_empty ( const path_handle_t path_handle) const
virtual

Returns true if the given path is empty, and false otherwise.

Reimplemented from handlegraph::PathHandleGraph.

◆ is_path_end()

bool bdsg::ODGI::is_path_end ( const step_handle_t step_handle) const

Returns true if the step handle is an end magic handle.

◆ is_path_front_end()

bool bdsg::ODGI::is_path_front_end ( const step_handle_t step_handle) const

Returns true if the step handle is a front end magic handle.

◆ link_steps()

void bdsg::ODGI::link_steps ( const step_handle_t from,
const step_handle_t to 
)
private

Helper to stitch up partially built paths.

◆ load()

void bdsg::ODGI::load ( std::istream &  in)

Load.

◆ max_node_id()

nid_t bdsg::ODGI::max_node_id ( void  ) 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_node_id()

nid_t bdsg::ODGI::min_node_id ( void  ) 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.

◆ optimize()

void bdsg::ODGI::optimize ( bool  allow_id_reassignment = true)
virtual

Organize the graph for better performance and memory use.

Implements handlegraph::MutableHandleGraph.

◆ path_back()

step_handle_t bdsg::ODGI::path_back ( const path_handle_t path_handle) const
virtual

Get a handle to the last step, which is arbitrary in the case of a circular path.

Get a handle to the last step in a path The path MUST be nonempty.

Implements handlegraph::PathHandleGraph.

◆ path_begin()

step_handle_t bdsg::ODGI::path_begin ( const path_handle_t path_handle) const
virtual

Get a handle to the first step in a path. The path MUST be nonempty.

Implements handlegraph::PathHandleGraph.

◆ path_end()

step_handle_t bdsg::ODGI::path_end ( const path_handle_t path_handle) const
virtual

Get a handle to a fictitious handle one past the end of the path.

Get the forward end iterator.

Implements handlegraph::PathHandleGraph.

◆ path_front_end()

step_handle_t bdsg::ODGI::path_front_end ( const path_handle_t path_handle) const
virtual

Get a handle to a fictitious handle one past the start of the path.

Get the reverse end iterator.

Implements handlegraph::PathHandleGraph.

◆ path_to_rank()

size_t bdsg::ODGI::path_to_rank ( const path_handle_t path) const
private

Get the 0-based rank encoded by a path handle.

◆ prepend_step()

step_handle_t bdsg::ODGI::prepend_step ( const path_handle_t path,
const handle_t to_append 
)
virtual

Append a visit to a node to the given path. Returns a handle to the new final step on the path which is appended. Handles to prior steps on the path, and to other paths, must remain valid.

Implements handlegraph::MutablePathHandleGraph.

◆ rank_to_id()

nid_t bdsg::ODGI::rank_to_id ( const uint64_t &  rank) const
private

get the node id for the node with the given backing rank

◆ rank_to_path()

path_handle_t bdsg::ODGI::rank_to_path ( size_t  rank) const
private

Get the path handle encoding the given 0-based rank.

Get the path handle encodign the given 0-based rank.

◆ reassign_node_ids()

void bdsg::ODGI::reassign_node_ids ( const std::function< nid_t(const nid_t &)> &  get_new_id)
virtual

Reassign all node IDs as specified by the old->new mapping function.

Implements handlegraph::MutableHandleGraph.

◆ rewrite_segment()

std::pair< step_handle_t, step_handle_t > bdsg::ODGI::rewrite_segment ( const step_handle_t segment_begin,
const step_handle_t segment_end,
const std::vector< handle_t > &  new_segment 
)
virtual

Replace the path range with the new segment.

Implements handlegraph::MutablePathHandleGraph.

◆ serialize_and_measure()

long long int bdsg::ODGI::serialize_and_measure ( std::ostream &  out) const

Serialize. Return the number of bytes written. We use a long long int here to keep varying types like uint64_t away from the Python bindings.

◆ serialize_members()

void bdsg::ODGI::serialize_members ( std::ostream &  out) const
privatevirtual

Serialization that implements the inherited "serialze" method.

Implements handlegraph::SerializableHandleGraph.

◆ set_circularity()

void bdsg::ODGI::set_circularity ( const path_handle_t path_handle,
bool  circular 
)
virtual

Set if the path is circular or not.

set the circular flag for the path

Implements handlegraph::MutablePathHandleGraph.

◆ set_handle_of_step()

void bdsg::ODGI::set_handle_of_step ( step_handle_t step_handle,
const handle_t handle 
) const
private

Modify the given step handle to point to the given handle.

◆ set_handle_sequence()

void bdsg::ODGI::set_handle_sequence ( const handle_t handle,
const std::string &  seq 
)
private

Compact away the deleted nodes info.

Set the handle sequence

◆ set_id_increment()

void bdsg::ODGI::set_id_increment ( const nid_t min_id)
virtual

set the id increment, used when the graph starts at a high id to reduce loading costs

Set a minimum id to increment the id space by, used as a hint during construction. May have no effect on a backing implementation.

Implements handlegraph::MutableHandleGraph.

◆ set_step()

step_handle_t bdsg::ODGI::set_step ( const step_handle_t step_handle,
const handle_t handle 
)

Set the step to the given handle, possibly re-linking and cleaning up if needed.

reassign the given step to the new handle

◆ steps_of_handle()

std::vector< step_handle_t > bdsg::ODGI::steps_of_handle ( const handle_t handle,
bool  match_orientation = false 
) const
virtual

Returns a vector of all steps of a node on paths. Optionally restricts to steps that match the handle in orientation.

Reimplemented from handlegraph::PathHandleGraph.

◆ swap_handles()

void bdsg::ODGI::swap_handles ( const handle_t a,
const handle_t b 
)

Swap the nodes corresponding to the given handles, in the ordering used by for_each_handle when looping over the graph. Other handles to the nodes being swapped must not be invalidated. If a swap is made while for_each_handle is running, it affects the order of the handles traversed during the current traversal (so swapping an already seen handle to a later handle's position will make the seen handle be visited again and the later handle not be visited at all).

◆ to_gfa() [1/3]

string bdsg::ODGI::to_gfa ( ) const

Convert to GFA and return as a string.

◆ to_gfa() [2/3]

void bdsg::ODGI::to_gfa ( const string &  filename) const

Convert to GFA and send to the given filename, or "-" for standard output (the default).

◆ to_gfa() [3/3]

void bdsg::ODGI::to_gfa ( std::ostream &  out) const

Convert to GFA (for debugging)

◆ traverse_edge_handle()

handle_t bdsg::ODGI::traverse_edge_handle ( const edge_t edge,
const handle_t left 
) const

View the given edge handle from either inward end handle and produce the outward handle you would arrive at.

Member Data Documentation

◆ _deleted_node_count

uint64_t bdsg::ODGI::_deleted_node_count = 0
private

◆ _edge_count

uint64_t bdsg::ODGI::_edge_count = 0
private

A helper to record the number of live edges.

◆ _id_increment

nid_t bdsg::ODGI::_id_increment = 1
private

ID of the lowest-rank (rank 0) node. Must be at least 1, or else the rank 0 node can't exist.

◆ _max_node_rank

uint64_t bdsg::ODGI::_max_node_rank = 0
private

Max rank (distance above _id_increment) of a node in the graph. 0 if the graph is empty.

◆ _min_node_rank

uint64_t bdsg::ODGI::_min_node_rank = std::numeric_limits<decltype(_min_node_rank)>::max()
private

Min rank (distance above _id_increment) of a node in the graph. Maximum possible value if the graph is empty, for easy min().

◆ _node_count

uint64_t bdsg::ODGI::_node_count = 0
private

A helper to record the number of live nodes.

◆ _path_count

uint64_t bdsg::ODGI::_path_count = 0
private

A helper to record the number of live paths.

◆ _path_rank_next

uint64_t bdsg::ODGI::_path_rank_next = 0
private

A helper to record the next path rank to use (path deletions are hard because of our path FM-index)

◆ deleted_node_bv

suc_bv bdsg::ODGI::deleted_node_bv
private

Mark deleted nodes here for translating graph ids into internal ranks.

◆ graph_id_hidden_set

hash_set<nid_t> bdsg::ODGI::graph_id_hidden_set
private

Records nodes that are hidden, but used to compactly store path sequence that has been removed from the node space. Hidden nodes are not counted towards the node count of the graph, and has_node will return false for their IDs (although new nodes cannot be created with the same IDs). Hidden nodes are destroyed as soon as the last path leaves them, so they may be invalidated by (or in the middle of!) path operations like rewrite_segment.

◆ node_v

std::vector<node_t> bdsg::ODGI::node_v
private

These are the backing data structures that we use to fulfill the above functions.

Records the handle to node_id mapping Use the special value "0" to indicate deleted nodes so that handle references in the id_map and elsewhere are not immediately destroyed

◆ path_metadata_v

std::vector<path_metadata_t> bdsg::ODGI::path_metadata_v
private

maps between path identifier and the start, end, and length of the path

◆ path_name_map

string_hash_map<std::string, path_handle_t> bdsg::ODGI::path_name_map
private

Links path names to handles.


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