Python bindings ?

[Piezoid]

Is there someone working on this ?

The only reference I found is on the GATB Global Architecture page :

Wrappers for other languages will be available in the future

I needed some basic scripting capabilities for exploring GATB's graphs so I wrote a simple Cython wrapper around gatb::core::debruijn::impl::Graph. Here is a demo. Code will be available soon.

Suggestions or questions are welcomed.

[rchikhi]

very nice!! noone else was working on it, yet we were often mentioning the possibility during our meetings. Thanks for creating this wrapper. Please commit it to gatb-core along with the demo.

[Piezoid]

I did this for the needs of my internship, mentored by Pierre Peterlongo. The wrapper covers a minimal part of Graph, supporting only few read-only operations. My usage showed that this is enough for graph inspection and prototyping extension algorithms.

Whith time, the interface gets more dogfooding and I'll probably release it next week. @pgdurand wants to talk about it before. I've not yet decided if I should release in a standalone repository or within gatb-core. I use this cmake module for compiling the Cython module. Some remarks about integration in gatb-core :

• The python module could be automatically enabled when both libpython and Cython are found.
• A python module is a shared object, so -fPIC is needed. That's the only mandatory change on the build process. We might want to revive the "gatbcore-dynamic" and build both static and dynamic relocatable objects when the python module is built.
• Another options is to make a separate compilation of the gatb-core source subset needed by the wrapper :
  • This would allow to enable -fvisibility=hidden or even -flto to reduce the code size. I managed to build a 3.3MB module with gcc and both of the aforementioned options. Yet, checking the list of emitted symbols showed that the compiler couldn't prune the code paths for graph creation.
  • Graph provides polymorphism through variant dispatching, but this could also be handled by Python's duck typing. For example we could build a .so python module for each LargeInt size and use a factory written in python for choosing and loading the right module. Exposing template classes in python (like Traversals) require either something like this or a dispatcher in c++ (virtual base class or variants).
  • Things would be simpler if gatb-core were a template only library.

Anyway, the scope of the python module should be redefined for other uses. Here a short list of what might be wanted :

• [x] Graph loading,
• [x] Graph inspection, node by node, or by simple paths,
• [ ] Other Graph functionality: node state, abundance, etc (done, but not tested),
• [ ] Datastructures (like MPHF maps, better than Python's dict/set when the key is a kmer),
• [ ] Graph creation,
• [ ] Interface for extension algorithms,
• [ ] UnitigGraph,
• [ ] ... ?

I won't have the time to implement those, but the scope of the interface might define how the wrapper is integrated in the project and it's build process.

[Piezoid]

I've just published the wrapper : here is the repository.

[rchikhi]

do you mean header-only library?

[Piezoid]

Yes. I must say, I don't quite like the fact that it's not possible to opt-out the visitor based interface in GraphTemplate. I would like to visit the GraphDataVariant once and run my (specialized template) algorithms from there. Instead the graph API "pattern match" the variant for each nucleotide traversed. Callgrind show that's about 1/3 of the cycles are spent visiting variants and copying GraphVectors.

To my understanding boost::variants are tagged union types. Consequently, sizeof(Integer) is the size of the largest kmer + a tag. The API could hand LargeInt<MAX_SIZE> to the user for the same effect.

Maybe I'm missing something ? The GraphTemplate<Node<Integer>,...> is said to be legacy API. But what are the alternatives ? It seems I can't find any gatb project using it. Projects like MindTheGap use span-specialized templates but still use the GraphTemplate<Node<Integer>,...> interface.

The Graph.cpp contains lots of duplicated code. It could leverage more of kmer::model iterators such that the code would be small enough to be header-only. This would enable RVO/Copy-elision for most cases.

GraphVector could be replaced with an iterator interface. Specialized iterators/cursors could be made for some applications : for example, when drawing simple paths, the iterator could remember the previous node and spare one contains() call when counting predecessors.

Sorry I'm a bit demanding on zero-cost abstractions since I learnt Rust :)

[rizkg]

zero-cost abstractions would be great :) We should discuss together your ideas on how to replace boost::variant

[rchikhi]

thanks for the extensive response.

Yes, you were missing something regarding the GraphTemplate instantiated with variants. The alternative is instantiation without the variant type, but instead with a single kmer size, i.e. directly passing a single templated integer to the GraphUnitigsTemplate class. The two projects that implement this alternative are bcalm: https://github.com/GATB/bcalm/blob/master/src/bcalm_1.cpp#L52 minia: https://github.com/GATB/minia/blob/master/src/Minia.cpp#L116 For your project, you can use the NodeFast/EdgeFast/GraphDataVariantFast alternative, as in https://github.com/GATB/minia/blob/master/src/Minia.cpp#L115. Indeed, for performance, it doesn't make sense to use boost::variant's anymore. These were introduced initially for convenience (and also because we didn't know it had performance drawbacks).

[rchikhi]

We'd be happy to have a header-only library, and in fact, refactor gatb-core. Would you be interested in being involved?

[Piezoid]

Thanks for the answer. I didn't know that GraphUnitigs had a better interface. The trio NodeFast/EdgeFast/GraphDataVariantFast still uses variants, right ? Maybe single alternative variants get optimized away ?

We'd be happy to have a header-only library, and in fact, refactor gatb-core. Would you be interested in being involved? Yes I'd like to, but I don't think I will have time to do so during my internship. As always, tons of ideas but not enough time to implement them...

I'm thinking about a cursor-like API. For example a base abstract class can be derived for each span-specialization. The key point is avoiding handing kmer back and forth to user code. Since kmers are of variable size, it complexifies the API. Kmers are often treated as black boxes in client code. Instead, users should get nucleotides, simple-paths, unitigs and be able to navigate in the graph.

Maybe a more efficient alternative would be specializing user template code for each span with a visitor pattern (but the whole user's algorithm is run inside one visit).

About the cursor API, it could allow some optimizations:

• Remembering the previous kmer, avoiding to query the graph for it while checking the in-degree of current kmer,
• Rolling hash (one barrel-shift and 2 xor per hash),
• Rolling windows for various purposes (eg. minimizers), ...

Ideally the user should be allowed to compose templates for choosing features (like the STL algorithms).

On a smaller scale, I rewrote GraphVector taking advantage of the recent addition of std=c++11. The ensued changes in GraphTemplate is still a bit messy...

[rchikhi]

GraphUnitigs has the same interface as GraphTemplate, actually.

NodeFast/EdgeFast/GraphDataVariantFast don't use boost::variants, they are just a regular data type. The trick is that the program needs to instantiate them based on the k-mer size given at command-line parameter. Thus, instead of checking that k-mer size each time a graph function is called, it is only checked once, in the main(). A typical program doesn't use variable k-mer sizes that differ by more than +-1. Thus it is okay to instantiate once and for all a graph template that supports one desired maximal k-mer size. This is a helpful constraint that would simplify the design of the library.

I don't know what cursor-like APIs are, would you have any good pointer to some documentation?

By the way nice job with the GraphVector rewrite! I'd be happy to take a pull request of all your changes at some point.

[Piezoid]

You're right NodeFast and EdgeFast wrap plain LargeInt. But GraphTemplate<NodeFast,EdgeFast,GraphDataVariantFast> still use the visitor pattern and in src/gatb/debruijn/impl/Graph.hpp we have:

using GraphDataVariantFast = boost::variant<GraphData >; Of course branching in the visitor should be optimized by the compiler.

Say I have a algorithm :

template<size_t span> class MyAlgo<span> {
public: void operator() (GraphUnitig<span>&);
};

How can i run it on an h5 input file that can be configured for any supported kmer size ? I need some sort of visitor pattern to specialize my code for each possible span, right ?

What I mean by cursor-like is an iterator really. Only there might be multiples choices of successors when calling next(). The general idea is small composable components, enclosing a minimalist mutable state that represent a position in a bigger data structure.

[rchikhi]

Ah right yes, I guess in order to keep compatibility with the rest of the code in Graph.cpp, GraphDataVariantFast had to be kept as a boost::variant.

Regarding your toy example,yes it seems that the only way to run this code is to have it compiled for as many span's values as needed, and the relevant one will be selectd at runtime given a user-specified k-mer size. I.e. as it is right now in GATB.

Sorry, I still didn't understand the iterator/cursor-like design. What successors are you talking about?