Class TriangleEdgeScore

Inheritance Relationships

Base Type

Class Documentation

class TriangleEdgeScore : public NetworKit::EdgeScore<count>

A parallel triangle counting implementation based on ideas in [0].

This implementation avoids less work but needs therefore also less checks and is (apart from a fast initialization) parallel without any locks. In experiments this implementation seems to be fast both in non-parallel as well as in parallel settings. With only one thread its performance is similar to the sequential ChibaNishizekiTriangleEdgeScore in NetworKit.

[0] Triangle Listing Algorithms: Back from the Diversion Mark Ortmann and Ulrik Brandes * 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). 2014, 1-8

Public Functions

TriangleEdgeScore(const Graph &G)
virtual count score(edgeid eid) override

Get the edge score of the edge with the given edge id.

virtual count score(node u, node v) override

Get the edge score of the given edge.

virtual void run() override

The generic run method which calls runImpl() and takes care of setting hasRun to the appropriate value.