[Networkit] Interface conventions for analytics algorithms

Florian Weber uagws at student.kit.edu
Sun Nov 2 01:21:40 CET 2014


Sorry for the late answer ;-)

> I somehow agree with both points. So far I don’t see enough benefits 
> of callable objects to justify all the refactoring work. What would 
> be the big benefit of putting our algorithms in stdlib algorithms? I 
> can’t imagine a case.

Let's say we have a container of Graphs or any other of our data-types
and an algorithm that maps those to bool (=predicate). If we no want to
find the first element that fulfills that predicate we can use
`std::find_if` instead of writing the loop ourselves, stating much
clearer what we want. If we just want to know whether any element
fulfills it, we can use std::any_of.

If the container is sorted and we have an algorithm that provides an
order on it, we can do similar things with std::lower_bound and
std::binary_search.

Somewhat more likely: If we want to do some kind of map-reduce, the
stdlib already offers std::transform and std::accumulate which do
basically that.

The bottom-line of all this is: Yes, we can work without those, and we
can also use lambdas to wrap the algorithms in callable objects again,
but usually it is a good idea to use the stdlib-algorithms, since they
tend to be more explicit then raw loops and certainly contain less bugs.
(Also: they are likely faster:
http://florianjw.de/de/ModernesCPP_data/search.svg)

Since I am already writing about this, I'd like to use the opportuniuty
to also make a general recommendation for everyone to really take some
time to look into the stuff in the <algorithm>- and <numeric>-headers.

>>> * Instead of a base-class we could just alias std::function
>>> which would give us structural typing here (the python-fans of
>>> you may like that, especially since this wouldn't compromise on 
>>> type-safety)
> - Florian
> 
> I don’t really understand this. Can you explain?

It's actually not that important, but the basic idea is that in order to
implement an algorithm, the convention is to inherit from a base-class
with virtual methods and work with some kind of pointer or reference to
that base-class in the code that tries to accept everything. This works
quite well, but since C++ has a static type-system it should rarely, if
ever, be a problem to just say: “I want something callable that has the
following parameters and return-types.” This is basically impossible to
achieve for normal-functions if we use normal inheritance. On the other
hand we could do something like that:

using GraphFromFileFactory = std::function<Graph(const std::string&)>;

and than just accept the typedef. The advantage is that we only force
the structure of the Factory on our users, not some kind of base-class.

The reason for me to mention python is that this would somehow mimic
pythons parameters not needing a certain base-class but just having to
implement the methods. And unlike python this wouldn't compromise on safety.

Florian

-------------- n?chster Teil --------------
Ein Dateianhang mit Bin?rdaten wurde abgetrennt...
Dateiname   : signature.asc
Dateityp    : application/pgp-signature
Dateigr??e  : 819 bytes
Beschreibung: OpenPGP digital signature
URL         : <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20141102/4aee429c/attachment.sig>


More information about the NetworKit mailing list