vgteam / libhandlegraph Goto Github PK

Subpath information is useful when working with subgraphs. It will also help with rGFA compatibility (SN/SO fields).

The following ideas emerged from the last meeting:

• A subpath is a path.
• It contains information linking it to the name and positional offset of its source path
• It represents a contiguous range in its source path
• All paths in a graph (regardless of whether or not they are subpaths) must have unique non-empty names. There's no naming structure enforced beyond this, though implementations will probably adopt conventions for subpath naming under the hood.

The subpath interface would be added to PathHandleGraph. It could look something like

/// is a path a subpath
virtual bool is_subpath(path_handle_t path_handle) const = 0;

/// get the name of the source path
virtual string get_source_path_name(path_handle_t path_handle) const = 0;

/// get the offset in the source path
virtual off_t get_source_path_offset(path_handle_t path_handle) const = 0;

I'm not sure if, implementation-wise, it's better to combine the above? In theory, they could be a single method like

/// get subpath information, not a subpath if returned name is empty
virtual pair<string, off_t> get_source_path_position(path_handle_t path_handle) const = 0;

Similar story for querying. We can provide default implementations of these using the above methods:

/// get subpaths for a path
vector<path_handle_t> get_subpaths(const string& source_path_name) const;

/// get_subpaths for a range in a path (start/end 0-based inclusive).  if last flag is true, only paths
/// fully contained in the range are returned
vector<path_handle_t> get_subpaths_for_range(const string& source_path_name, off_t start, off_t end, bool fully_contained = false)

I think implementing this should be pretty straightforward, but making sure that existing algorithms that modify paths use it properly may take some doing.

@ekg @jeizenga @adamnovak thoughts?

I'd like to match divide_handle with an inverse function that combines handles back together.

This would be the signature:

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

Any thoughts?

I'm unable to get past this strange error:

/home/erik/odgi/build/handlegraph-prefix/src/handlegraph/src/include/handlegraph/mutable_path_deletable_handle_graph.hpp:17:85: error: expected class-name befo
re ‘,’ token                                                                                                                                                   
 class MutablePathDeletableHandleGraph : virtual public MutablePathMutableHandleGraph, virtual public DeletableHandleGraph {

All I've done is update the git revision of libhandlegraph that I'm pointing to.

How am I using this wrong, and what's changed in the interface since the last working revision? 0468858

That seems wrong to me, since is a strictly less expressive interface.

I got this error from the compiler, which went away when I switched to Deletable

src/unittest/cluster.cpp:231:13: error: no matching function for call to 'random_graph'
            random_graph(1000, 20, 100, &graph);
            ^~~~~~~~~~~~
/Users/Jordan/Documents/GitHub/vg/src/unittest/random_graph.hpp:11:6: note: candidate function not viable: no known conversion from 'vg::VG *' to 'vg::MutablePathMutableHandleGraph *' (aka 'handlegraph::MutablePathMutableHandleGraph *') for 4th argument
void random_graph(int64_t seq_size, int64_t variant_len, int64_t variant_count,
     ^
1 error generated.
make: *** [obj/unittest/cluster.o] Error 1

In order to use the RankedHandleGraph interface on a PathHandleGraph, we need to either derive a new class, a RankedPathHandleGraph, or use a dynamic cast.

These are kind of common functions, and should have standard implementations that are basically trivial in all of our graph models. Maybe we would be better to just put them into the base HandleGraph class?

We're missing a use of the BoolReturningWrapper there, I think.

Ensuring that edges aren't duplicated can require linear-time operations (in the number of edges). For graphs with some nodes that have very high degree, this quickly becomes a problem.

I propose that we relax the requirement that edges are unique, and instead offer an API call to remove the duplicate edges. This would make it easier to drive bulk loads and rebuilds of graphs where we know that the edge set is unique.

In some of the libbdsg implementations of the API, we don't have a simple mechanism to prevent duplication. Adding one that would be efficient would take a lot of memory.

@jeizenga mentioned this before. I think we should consider supporting it.

This specification is broken for the case where we replace the last step in the path. What is the past-the-last step handle in this case? We should change it to be begin to end inclusive, and this would resolve the problem. I'll implement it that way on my end.

    /**                                                                                                                                                        
     * Delete a segment of a path and rewrite it as some other sequence of steps. Returns a pair                                                               
     * of step_handle_t's that indicate the range of the new segment in the path. The segment to                                                               
     * delete should be designated by the first and the past-the-last step handle.  If the step                                                                
     * that is returned by path_begin is deleted, path_begin will now return the first step from                                                               
     * the new segment or, in the case that the new segment is empty, segment_end.                                                                             
     */
    virtual std::pair<step_handle_t, step_handle_t> rewrite_segment(const step_handle_t& segment_begin,
                                                                    const step_handle_t& segment_end,
                                                                    const std::vector<handle_t>& new_segment) = 0;

It looks like #12 and #13 said that rewrite_segment should remove the handle passed as end, and the doc comment seems to suggest so as well. However, in practice, at least for HashGraph and (I think) vg::VG, the end is treated as a past-end. Here's HashGraph not removing the end step:

https://github.com/vgteam/libbdsg/blob/7b913da50dc70bf2b4b301e1226a6586e27892bc/src/hash_graph.cpp#L524-L542

In order to allow for pure insertion operations, the end has to be treated as a past-end, so maybe that's why it is being done this way.

We should make sure all the implementations use a past-end, and update the documentation. Alternately, if what's documented right now is what we really want, I think we need to modify at least HashGraph and vg::VG, and maybe other implementations.

Circular paths are not supported in the current path_handle_graph interface, please add support for circular paths.

I'm attempting to use libodgi and libhandlegraph together, and getting errors like this:

/usr/bin/ld: odgi-prefix/lib/libodgi.a(odgi.cpp.o):(.data.rel.ro._ZTCN4odgi7graph_tE208_N11handlegraph20DeletableHandleGraphE[_ZTVN4odgi7graph_tE]+0x1e8): undefined reference to `handlegraph::MutableHandleGraph::increment_node_ids(long)'
/usr/bin/ld: odgi-prefix/lib/libodgi.a(odgi.cpp.o):(.data.rel.ro._ZTCN4odgi7graph_tE208_N11handlegraph18MutableHandleGraphE[_ZTVN4odgi7graph_tE]+0x190): undefined reference to `handlegraph::MutableHandleGraph::increment_node_ids(long)'
/usr/bin/ld: odgi-prefix/lib/libodgi.a(odgi.cpp.o):(.data.rel.ro._ZTCN4odgi7graph_tE0_N11handlegraph29MutablePathMutableHandleGraphE[_ZTVN4odgi7graph_tE]+0x4e8): undefined reference to `handlegraph::MutableHandleGraph::increment_node_ids(long)'
/usr/bin/ld: odgi-prefix/lib/libodgi.a(odgi.cpp.o):(.data.rel.ro._ZTCN4odgi7graph_tE0_N11handlegraph31MutablePathDeletableHandleGraphE[_ZTVN4odgi7graph_tE]+0x518): undefined reference to `handlegraph::MutableHandleGraph::increment_node_ids(long)'

It looks like there is a kind of confusion about nid_t and long, and this virtual function isn't being instantiated correctly.

This can be resolved by adding a specialization of the function for long.

@glennhickey @ekg @adamnovak

So the general consensus seems to be that the interface for paths could be better. I'm opening this issue so we can have a discussion about what we want that to look like.

Personally, one thing that I don't like is that you have to manually check whether the path is empty before you iterate along it. Also, we don't have a "past-the-last" type iterator, which makes the loops a little clunky in C++. Basically, I'd like a more compact "for each" loop.

Also, our mutable path interface is currently append only. Should we expand that to support prepending and insertion in the middle? What about deletion?

We also still have #2 about the lack of support for circular paths outstanding. We should deal with as well, while we're discussing updating the interface. In particular, I think we need to think about the semantics of iterating to the "next" node on a path when the path loops around, and also to provide a means to iterate over every node one time and every edge one time.

Hi,

Reading the handlegraph API, I see there is away to get the position of step handles along the path handles.
Is there a way to calculate the position of the step handle relative to the node handle of this step?
I only see that it is possible to retrieve the node handle of step handles, but no their position?

My thanks

The vg Sampler samples from the sequence using a 1-based offset:

https://github.com/vgteam/vg/blob/e558c3cc27984415ba3de7c3d941827c39f17376/src/sampler.cpp#L59-L62

However, this isn't documented in the VectorizableHandleGraph interface, so it is likely that implementers will produce and expect 0-based offsets.

It looks like the VectorizableOverlay from libbdsg produces 0-based offsets, but expects 1-based offsets, which is just wild:

https://github.com/vgteam/libbdsg/blob/e073c2aee77e73ec41310bf3191af322fe8faa7e/src/vectorizable_overlays.cpp#L88-L96

We should choose all 0-based or all 1-based (probably all 0-based), document it, and change all the clients and implementations.

VectorizableHandleGraph::edge_index should state that the edge_t has to be from for_each_edgeor edge_handle (i.e. in canonical order and orientation).

It would be useful if we had a standard way to assign and obtain non-numeric node names. This would be an optional trait, like the serialization or vectorization interface.

It's not clear to me how it would interact with construction from GFA. I guess in that case we would load the names and establish a set of internal IDs.

@Robin-Rounthwaite is working on a graph normalization method in VG, and it's run up against some limitations on the HandleGraph API. Specifically, he want to modify the topology of sections of graph while maintaining embedded paths. Currently, our path modification API is append only, so edits to the middle are more or less prohibited. I think we need to extend the API a bit, but we have some options for API design.

To my mind, there are two real possibilities here:

1. Allow removal and addition of single steps to the middle of the path. I like that this is a simple, low-level API that matches the level of access to the graph that we've been providing in the rest of the codebase. However, it has the downside that swapping a segment of path from one part of the graph to another may require invalid intermediate states where adjacencies in the path don't correspond to edges in the graph.

2. Create a bulk swapping method for a segment of path. This feels like a higher level API than the rest of libhandlegraph provides, but it would allow the graph normalization algorithm to avoid any invalid intermediate states.

Any thoughts? @adamnovak @glennhickey @ekg

The current handlegraph api, uses the internal iterator approach (e.g. for_each_edge etc.) This is very inconvenient when trying to use this code from python. The only way to move data from inside the iteratee to the outside is by running the iteration in a different thread than the major python code and pass out the required information using a shared blocking queue. As you can imagine this is a pain to program.

The python approach, like modern java is to use generators/streams instead. This works well in these languages because memory ownership is well defined. For C++ I imagine this approach was taken to make it easier to keep track of who owns what memory. Unfortunately, the push approach inherent in this solution is a pain to use from languages which like to use a pull model.

Could we have standard C++ iterators for each iteratee method?

Hi,

I am trying to use the dijkstra algorithm defined in libhandlegraph but getting a linker error.

undefined reference to `handlegraph::algorithms::dijkstra(handlegraph::HandleGraph const*, handlegraph::handle_t, std::function<bool (handlegraph::handle_t const&, unsigned long)>, bool)'

There are not other errors and warnings.
I compiled and installed both libbdsg and libhandlegraph on Ubuntu.

I inspected the libhandlegraph dynamic and static libraries for this symbol and it is indeed there.

cgroza@ubuntu:/$ nm ./usr/local/lib/libhandlegraph.so | grep dijkstra
0000000000024a10 t _GLOBAL__sub_I_dijkstra.cpp
0000000000059050 T _ZN11handlegraph10algorithms8dijkstraEPKNS_11HandleGraphENS_8handle_tESt8functionIFbRKS4_mEEbbb
0000000000023287 t _ZN11handlegraph10algorithms8dijkstraEPKNS_11HandleGraphENS_8handle_tESt8functionIFbRKS4_mEEbbb.cold
0000000000058470 T _ZN11handlegraph10algorithms8dijkstraEPKNS_11HandleGraphERKSt13unordered_setINS_8handle_tESt4hashIS5_ESt8equal_toIS5_ESaIS5_EESt8functionIFbRKS5_mEEbbb
0000000000023182 t _ZN11handlegraph10algorithms8dijkstraEPKNS_11HandleGraphERKSt13unordered_setINS_8handle_tESt4hashIS5_ESt8equal_toIS5_ESaIS5_EESt8functionIFbRKS5_mEEbbb.cold
0000000000056f30 t _ZNSt17_Function_handlerIFbRKN11handlegraph8handle_tEEZNS0_20BoolReturningWrapperIZNS0_10algorithms8dijkstraEPKNS0_11HandleGraphERKSt13unordered_setIS1_St4hashIS1_ESt8equal_toIS1_ESaIS1_EESt8functionIFbS3_mEEbbbEUlS3_E_Lb0EE4wrapERKSM_EUlDpOT_E_E10_M_managerERSt9_Any_dataRKSV_St18_Manager_operation
0000000000056fb0 t _ZNSt17_Function_handlerIFbRKN11handlegraph8handle_tEEZNS0_20BoolReturningWrapperIZNS0_10algorithms8dijkstraEPKNS0_11HandleGraphERKSt13unordered_setIS1_St4hashIS1_ESt8equal_toIS1_ESaIS1_EESt8functionIFbS3_mEEbbbEUlS3_E_Lb0EE4wrapERKSM_EUlDpOT_E_E9_M_invokeERKSt9_Any_dataS3_
0000000000080830 d _ZTIZN11handlegraph20BoolReturningWrapperIZNS_10algorithms8dijkstraEPKNS_11HandleGraphERKSt13unordered_setINS_8handle_tESt4hashIS6_ESt8equal_toIS6_ESaIS6_EESt8functionIFbRKS6_mEEbbbEUlSH_E_Lb0EE4wrapERKSK_EUlDpOT_E_
000000000006bf60 r _ZTSZN11handlegraph20BoolReturningWrapperIZNS_10algorithms8dijkstraEPKNS_11HandleGraphERKSt13unordered_setINS_8handle_tESt4hashIS6_ESt8equal_toIS6_ESaIS6_EESt8functionIFbRKS6_mEEbbbEUlSH_E_Lb0EE4wrapERKSK_EUlDpOT_E_

Here is the Makefile and the source code:

Makefile:

nearestpaths: nearestpaths.cpp
	g++ -std=c++2b  nearestpaths.cpp -lbdsg -lsdsl -lgomp -lhandlegraph -o nearestpaths

all: nearestpaths

Source code:

#include <handlegraph/algorithms/dijkstra.hpp>
#include <handlegraph/handle_graph.hpp>
#include <bdsg/packed_graph.hpp>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

const size_t max_distance = 100;

int main(int argc, char **argv) {
  std::vector<std::string> paths;

  std::ifstream paths_file("test/chr21_subset.paths");

  std::string p;
  while(!paths_file.eof()) {
    std::getline(paths_file, p);
    paths.push_back(p);
  }

  bdsg::PackedGraph graph;
  graph.deserialize("test/chr21_subset.pack");

  for (auto &s : paths) {
    std::cout << s << std::endl;
    if (!graph.has_path(s)) {
      std::cout << "No path " << s << std::endl;
      continue;
    }
    bdsg::path_handle_t path = graph.get_path_handle(s);
    bdsg::handle_t start_node = graph.get_handle_of_step(graph.path_begin(path));
    handlegraph::algorithms::dijkstra(
        &graph, start_node, [&](const handlegraph::handle_t h, size_t d) {
          std::cout << "Reached " << d << std::endl;
          if(d > max_distance)
            return false;
          return true;
        });
  }

  return 0;
}

Any pointers on why g++ does not find the symbols?

My thanks.

An important operation is to remove nodes from the graph. For instance, we might want to remove low-coverage nodes.

This can cause us to remove nodes in the middle of paths, breaking them. We have no way to represent this, and so I think most of our implementations will just remove the entire path.

@adamnovak had the idea of an "extent", where we know how much sequence was lost, but we don't represent the sequence. This is a great idea, but we have no way to serialize it in GFA. So, let's clarify exactly the semantics we want, present it to the GFA spec group, and implement this in all of the path handle graph libraries.

@glennhickey needs a way to edit a MutableHandleGraph, and then translate read alignments from the old graph to the new graph (and back again?). This is necessary for variant calling in vg.

We also need to be able to serialize translation information, so we can create an updated graph, and then move it and the translation from the old graph to another machine.

To support this use case, we need an API for translating between graphs. Since we want to use it to translate between old and new versions of the same MutableHandleGraph, it can't (at least at the input side) be handle based, because handles to the old graph are invalidated on mutation.

We need to work out what this API should look like. Part of that is working out what the types to be translated should be; we don't want to build in a dependency on vg's Protobuf here.

Here's a first draft from me:

• Have a type using region_t = vector<tuple<nid_t, bool, size_t, size_t>> to track a series of node, orientation, start, end intervals. They do not necessarily abut in the graph, but if they abut on the same node they must be coalesced. This serves as both the input and output type for translation.

• Define some translation semantics. When something being translated lies on a node that has no counterpart in the destination graph, it translates to an interval on node 0 forward from 0 to n, depending on its length. If part of an input region is on node 0, it stays on node 0 in the translation output. So translating back and forth between graphs which don't fully contain each other is necessarily lossy.

• Have an interface GraphToGraphTranslation:

  • region_t translate_forward(const region_t& from) const
  • And BidirectionalGraphToGraphTranslation:
    • region_t translate_backward(const region_t& to) const

I don't think we want an actual implementation of a translation in this repo. It should probably go in vg or in sglib. For that matter, if handle_t doesn't appear in the API anywhere, I'm not sure it makes sense for the interface to live in libhandlegraph at all.

An easy way to construct a translation might be a MutableHandleGraph overlay that logs mutation operations and constructs the translation that they define. But for serializing and loading translations, we'd need a way to re-load the translation later, and it might be more convenient if that didn't require having the graph available at load time.

Possible improvements:

• Define region_t as a template, and have region_t<handle_t> and region_t<pair<nid_t, bool>>. Then we can have translations between real handlegraphs (useful for some of vg's overlays, where the backing graph sticks around unmodified), as well as between ID-defined graph spaces, by implementing GraphToGraphTranslation<handle_t, handle_t> or GraphToGraphTranslation<pair<nid_t, bool>, pair<nid_t, bool>>. You could even have translations that take handles on one end and ID, bool pairs on the other (which might be the right interface for translating to/from an old version of an augmented graph). This would help justify having this as part of libhandlegraph and not vg.

• Define translation serialization/load as part of the interface. Do it in a way such that it makes sense to have a serializable graph with a serializable translation.

Me, @jeizenga, @glennhickey, and @ekg all need to discuss this.

As far as I can tell, step_handle_t doesn't track an orientation. There's no flip for it; it always is in the orientation of the path it is part of.

But then when you loop through the steps on a handle, you'll get all the steps that visit the handle's node in both direction, but each step you get will be in the path's forward orientation. So if you want to do something like see what paths leave a handle to the left, you need to do a bunch of orientation tracking and call get_next_step or get_previous_step depending on how the path went through the handle you started with.

And if the path went through your starting handle backward, get_handle_of_step will return the reverse of the handle you started with.

None of these caveats seem to be documented in the PathHandleGraph interface. At the very least we should point them out.

I kind of want to give orientations to step handles, so that you can have a handle to the reverse orientation of a path where next is previous and visa versa, and a way to get and flip that orientation flag. That would make navigating along paths much harder to mess up when you find them from handles, but it would also ask more of our implementations.

I've been thinking of adding an OrderedHandleGraph type. However, that would double the size of our class hierarchy again, based on whether ordering is supported.

What I want to do is have a HandleGraph<Feature1, Feature2, Feature3, ...> syntax. So I could write:

void do_the_thing(const HandleGraph<Ordered>& ordered_graph);

void do_another_thing(HandleGraph<Paths, Ordered, Mutable>& g1, HandleGraph<Mutable, Ordered>& g2);

class SomeImplementation : public HandleGraph<Mutable, Deletable, Paths, Ordered> {
};

Problems to be overcome:

• Ordering: HandleGraph<Mutable, Ordered> is a different type than HandleGraph<Ordered, Mutable>, and they can't both inherit from each other. We might be able to solve this by using int flags as template parameters: HandleGraph<feature::MUTABLE | feature::ORDERED>. We could also maybe solve this with Fancy Metaprogramming and a template<typename... Ts> using HandleGraph<Ts...> = SortStuff<Ts...>::type and have it give you a canonical type.

• Subsets: HandleGraph<Mutable, Ordered, Paths> has to inherit from HandleGraph<Mutable, Paths>, HandleGraph<Ordered, Paths>, and HandleGraph<Mutable, Ordered>, even if we ignore template argument ordering. Really we're still making our class hierarchy explode, we're just making the compiler do it for us.

This is probably a dumb question, but what's the best way to check if a handle is empty? This comes up, for example, when replacing code of the type

Node* node = nullptr;
// do some stuff
if (node != nullptr) {
   // more stuff
}

Obviously, I can do the same thing with a handle_t*, but that's pretty ugly. I'd rather use handle_t directly. Is there a way to do this?

Thank you for developing such a set of efficient tools, now I encountered some small troubles when making, the specific error information is as follows
root@ubuntu:/home/yaozhen/libhandlegraph/build# make [ 2%] Building CXX object CMakeFiles/handlegraph_objs.dir/src/path_metadata.cpp .o In file included from /usr/include/c++/5/bits/hashtable.h:35:0, from /usr/include/c++/5/unordered_set:47, from /home/yaozhen/libhandlegraph/src/include/handlegraph/path_ metadata.hpp:13, from /home/yaozhen/libhandlegraph/src/path_metadata.cpp:5: /usr/include/c++/5/bits/hashtable_policy.h: In instantiation of ‘struct std::__d etail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegraph::PathSen se> >’: /usr/include/c++/5/type_traits:137:12: required from ‘struct std::__and_<std:: __is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept _hash<handlegraph::PathSense, std::hash<handlegraph::PathSense> > >’ /usr/include/c++/5/type_traits:148:38: required from ‘struct std::__not_<std:: __and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::_ _is_noexcept_hash<handlegraph::PathSense, std::hash<handlegraph::PathSense> > > >’ /usr/include/c++/5/bits/unordered_set.h:95:63: required from ‘class std::unord ered_set<handlegraph::PathSense>’ /home/yaozhen/libhandlegraph/src/include/handlegraph/path_metadata.hpp:279:41: required from here /usr/include/c++/5/bits/hashtable_policy.h:85:34: error: no match for call to ‘( const std::hash<handlegraph::PathSense>) (const handlegraph::PathSense&)’ noexcept(declval<const _Hash&>()(declval<const _Key&>()))> ^ In file included from /usr/include/c++/5/bits/move.h:57:0, from /usr/include/c++/5/bits/stl_pair.h:59, from /usr/include/c++/5/utility:70, from /home/yaozhen/libhandlegraph/src/include/handlegraph/types .hpp:9, from /home/yaozhen/libhandlegraph/src/include/handlegraph/handl e_graph.hpp:8, from /home/yaozhen/libhandlegraph/src/include/handlegraph/path_ metadata.hpp:8, from /home/yaozhen/libhandlegraph/src/path_metadata.cpp:5: /usr/include/c++/5/type_traits: In instantiation of ‘struct std::__not_<std::__a nd_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is _noexcept_hash<handlegraph::PathSense, std::hash<handlegraph::PathSense> > > >’: /usr/include/c++/5/bits/unordered_set.h:95:63: required from ‘class std::unord ered_set<handlegraph::PathSense>’ /home/yaozhen/libhandlegraph/src/include/handlegraph/path_metadata.hpp:279:41: required from here /usr/include/c++/5/type_traits:148:38: error: ‘value’ is not a member of ‘std::_ _and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__ is_noexcept_hash<handlegraph::PathSense, std::hash<handlegraph::PathSense> > >’ : public integral_constant<bool, !_Pp::value> ^ In file included from /usr/include/c++/5/unordered_set:48:0, from /home/yaozhen/libhandlegraph/src/include/handlegraph/path_ metadata.hpp:13, from /home/yaozhen/libhandlegraph/src/path_metadata.cpp:5: /usr/include/c++/5/bits/unordered_set.h: In instantiation of ‘class std::unorder ed_set<handlegraph::PathSense>’: /home/yaozhen/libhandlegraph/src/include/handlegraph/path_metadata.hpp:279:41: required from here /usr/include/c++/5/bits/unordered_set.h:95:63: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegra ph::PathSense> > > >’ typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable; ^ /usr/include/c++/5/bits/unordered_set.h:102:45: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::key_type key_type; ^ /usr/include/c++/5/bits/unordered_set.h:103:47: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::value_type value_type; ^ /usr/include/c++/5/bits/unordered_set.h:104:43: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::hasher hasher; ^ /usr/include/c++/5/bits/unordered_set.h:105:46: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::key_equal key_equal; ^ /usr/include/c++/5/bits/unordered_set.h:106:51: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::allocator_type allocator_type; ^ /usr/include/c++/5/bits/unordered_set.h:111:45: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::pointer pointer; ^ /usr/include/c++/5/bits/unordered_set.h:112:50: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::const_pointer const_pointer; ^ /usr/include/c++/5/bits/unordered_set.h:113:47: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::reference reference; ^ /usr/include/c++/5/bits/unordered_set.h:114:52: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::const_reference const_reference; ^ /usr/include/c++/5/bits/unordered_set.h:115:46: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::iterator iterator; ^ /usr/include/c++/5/bits/unordered_set.h:116:51: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::const_iterator const_iterator; ^ /usr/include/c++/5/bits/unordered_set.h:117:51: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::local_iterator local_iterator; ^ /usr/include/c++/5/bits/unordered_set.h:118:57: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::const_local_iterator const_local_iterator; ^ /usr/include/c++/5/bits/unordered_set.h:119:47: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::size_type size_type; ^ /usr/include/c++/5/bits/unordered_set.h:120:52: error: ‘value’ is not a member o f ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegr aph::PathSense> > > >’ typedef typename _Hashtable::difference_type difference_type; ^ /usr/include/c++/5/bits/unordered_set.h:274:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegra ph::PathSense> > > >’ operator=(initializer_list<value_type> __l) ^ /usr/include/c++/5/bits/unordered_set.h:368:2: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegra ph::PathSense> > > >’ emplace(_Args&&... __args) ^ /usr/include/c++/5/bits/unordered_set.h:412:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegra ph::PathSense> > > >’ insert(const value_type& __x) ^ /usr/include/c++/5/bits/unordered_set.h:416:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegra ph::PathSense> > > >’ insert(value_type&& __x) ^ /usr/include/c++/5/bits/unordered_set.h:471:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegra ph::PathSense> > > >’ insert(initializer_list<value_type> __l) ^ /usr/include/c++/5/bits/unordered_set.h:616:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegra ph::PathSense> > > >’ equal_range(const key_type& __x) ^ /usr/include/c++/5/bits/unordered_set.h:620:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<handlegraph::PathSense> >, std::__detail::__is_noexcept_hash<handlegraph::PathSense, std::hash<handlegra ph::PathSense> > > >’ equal_range(const key_type& __x) const ^ /home/yaozhen/libhandlegraph/src/path_metadata.cpp: In lambda function: /home/yaozhen/libhandlegraph/src/path_metadata.cpp:338:32: error: ‘const class s td::unordered_set<handlegraph::PathSense>’ has no member named ‘count’ if (senses && !senses->count(get_sense(handle))) { ^ CMakeFiles/handlegraph_objs.dir/build.make:134: recipe for target 'CMakeFiles/ha ndlegraph_objs.dir/src/path_metadata.cpp.o' failed make[2]: *** [CMakeFiles/handlegraph_objs.dir/src/path_metadata.cpp.o] Error 1 CMakeFiles/Makefile2:141: recipe for target 'CMakeFiles/handlegraph_objs.dir/all ' failed make[1]: *** [CMakeFiles/handlegraph_objs.dir/all] Error 2 Makefile:127: recipe for target 'all' failed make: *** [all] Error 2
My system is Ubuntu 16.04
g++ and gcc version is 5.4.0

Should we expose a way to get the position of a node start in a (possibly virtual) vector of concatenated node sequences?

Maybe we should not use this model anymore, but it's been a significant part of some uses of the xg index in the past.

I'd like to add an handlegraph interface to get at the GBWTmetadata, like sample and haplotype. This would be useful for reading gbz/gbwt, but also for going back and forth between other formats. It would look something like

virtual std::string get_sample_name(const path_handle_t& path_handle) = 0;

virtual int64_t get_haplotype(const path_handle_t& path_handle) = 0;

/// I think this could be an alias to get_path_name
virtual std::string get_contig_name(const path_handle_t& path_handle) = 0;

/// I'd also like to add subpath information while we're at it
virtual std::pair<int64_t, int64_t> get_path_offsets(const path_handle_t& path_handle) = 0;

For GBWT, this information can all be extracted from the metadata. For any other type of graph, we could just use the naming convention from PGGB

I think we could ensure pretty decent backwards compatibility. A path named "chr1" would return "chr1" as the name/contig, 0 as the haplotype, an empty string (or default value) for sample, and -1,-1 a the range.

I think it'd be easiest to add this to the existing path handle graph interface, but it could always be a new interface as well. If this were implemented, it becomes trivial to convert back and forth from gbz and other formats, and avoids a lot of the hacky nonsense like I put in deconstruct to support both haplotype from metadata as well as from naming conventions.

Also hope this will allow graphs and tools to stay interoperable even in light of the whole gfa w-line fiasco!

Curious to hear your thoughts @jltsiren @ekg @adamnovak @jeizenga