Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
triangles.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * examples/triangles/triangles.hpp
3  *
4  * Part of Project Thrill - http://project-thrill.org
5  *
6  * Copyright (C) 2016 Alexander Noe <[email protected]>
7  *
8  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
9  ******************************************************************************/
10 
11 #pragma once
12 #ifndef THRILL_EXAMPLES_TRIANGLES_TRIANGLES_HEADER
13 #define THRILL_EXAMPLES_TRIANGLES_TRIANGLES_HEADER
14 
16 #include <thrill/api/size.hpp>
17 
18 #include <utility>
19 
20 using Node = size_t;
21 using Edge = std::pair<Node, Node>;
22 
23 using namespace thrill; // NOLINT
24 
25 namespace std {
26 
27 template <>
28 struct hash<Edge>{
29  size_t operator () (const Edge& v) const {
30 
31  size_t seed = 0;
32  seed ^= std::hash<size_t>()(
33  v.first) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
34  seed ^= std::hash<size_t>()(
35  v.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
36  return seed;
37  }
38 };
39 
40 } // namespace std
41 
42 namespace examples {
43 namespace triangles {
44 
45 template <bool UseDetection = false, typename Stack>
46 size_t CountTriangles(const DIA<Edge, Stack>& edges) {
47 
48  auto edges_length_2 =
49  InnerJoin(
50  LocationDetectionFlag<UseDetection>(),
51  edges, edges,
52  [](const Edge& e) { return e.second; },
53  [](const Edge& e) { return e.first; },
54  [](const Edge& e1, const Edge& e2) {
55  assert(e1.second == e2.first);
56  return std::make_pair(e1.first, e2.second);
57  });
58 
59  auto triangles =
60  InnerJoin(
61  LocationDetectionFlag<UseDetection>(),
62  edges_length_2, edges,
63  [](const Edge& e) { return e; },
64  [](const Edge& e) { return e; },
65  [](const Edge& /* e1 */, const Edge& /* e2 */) {
66  return (size_t)1;
67  });
68 
69  return triangles.Size();
70 }
71 
72 } // namespace triangles
73 } // namespace examples
74 
75 #endif // !THRILL_EXAMPLES_TRIANGLES_TRIANGLES_HEADER
76 
77 /******************************************************************************/
std::pair< Node, Node > Edge
Definition: triangles.hpp:21
auto InnerJoin(const LocationDetectionFlag< LocationDetectionValue > &, const FirstDIA &first_dia, const SecondDIA &second_dia, const KeyExtractor1 &key_extractor1, const KeyExtractor2 &key_extractor2, const JoinFunction &join_function, const HashFunction &hash_function=HashFunction())
Performs an inner join between this DIA and the DIA given in the first parameter. ...
Definition: inner_join.hpp:713
size_t Node
Definition: triangles.hpp:20
unsigned seed
size_t CountTriangles(const DIA< Edge, Stack > &edges)
Definition: triangles.hpp:46
HashCrc32< T > hash
Select a hashing method.
Definition: hash.hpp:262