Thrill  0.1
bfs.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * examples/bfs/bfs.hpp
3  *
4  * Part of Project Thrill - http://project-thrill.org
5  *
6  * Copyright (C) 2017 Robert Williger <[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_BFS_BFS_HEADER
13 #define THRILL_EXAMPLES_BFS_BFS_HEADER
14 
15 #include <cereal/types/vector.hpp>
17 
18 #include <limits>
19 #include <vector>
20 
21 namespace examples {
22 namespace bfs {
23 
25 using VertexId = size_t;
26 using EdgeList = std::vector<VertexId>;
27 
31 };
32 
33 std::ostream& operator << (std::ostream& os, const NodeParentPair& pair) {
34  return os << '(' << pair.node << ',' << pair.parent << ')';
35 }
36 
37 class BfsNode
38 {
39 public:
41  VertexId nodeIndex = INVALID;
42  size_t treeIndex = INVALID;
44  size_t level = INVALID;
45 
46  BfsNode() = default;
47 
48  template <typename Archive>
49  void serialize(Archive& archive) {
50  archive(edges, nodeIndex, treeIndex, parent, level);
51  }
52 };
53 
54 std::ostream& operator << (std::ostream& os, const BfsNode& node) {
55  os << "(" << node.nodeIndex << ": [";
56 
57  if (!node.edges.empty()) {
58  os << node.edges[0];
59  for (size_t i = 1; i != node.edges.size(); ++i)
60  os << ',' << node.edges[i];
61  }
62 
63  os << "], par: " << node.parent << ", lvl: " << node.treeIndex << '_' << node.level << ')';
64 
65  return os;
66 }
67 
68 struct TreeInfo {
69  size_t startIndex;
70  size_t levels;
71 };
72 
73 } // namespace bfs
74 } // namespace examples
75 
76 #endif // !THRILL_EXAMPLES_BFS_BFS_HEADER
77 
78 /******************************************************************************/
static uint_pair max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.hpp:226
std::ostream & operator<<(std::ostream &os, const NodeParentPair &pair)
Definition: bfs.hpp:33
VertexId parent
Definition: bfs.hpp:43
Definition: bfs.hpp:21
VertexId nodeIndex
Definition: bfs.hpp:41
void serialize(Archive &archive)
Definition: bfs.hpp:49
std::vector< VertexId > EdgeList
Definition: bfs.hpp:26
const size_t INVALID
Definition: bfs.hpp:24
EdgeList edges
Definition: bfs.hpp:40
size_t VertexId
Definition: bfs.hpp:25