Class TriangleEdgeScore¶

Inheritance Relationships¶

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.

count score(node u, node v) override¶

virtual void run() override¶

Compute the edge score.