Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
bfs.cpp File Reference
#include "bfs.hpp"
#include <thrill/api/cache.hpp>
#include <thrill/api/generate.hpp>
#include <thrill/api/group_by_iterator.hpp>
#include <thrill/api/group_by_key.hpp>
#include <thrill/api/group_to_index.hpp>
#include <thrill/api/min.hpp>
#include <thrill/api/print.hpp>
#include <thrill/api/read_lines.hpp>
#include <thrill/api/reduce_to_index.hpp>
#include <thrill/api/size.hpp>
#include <thrill/api/sort.hpp>
#include <thrill/api/sum.hpp>
#include <thrill/api/write_lines.hpp>
#include <thrill/api/zip.hpp>
#include <thrill/api/zip_with_index.hpp>
#include <tlx/cmdline_parser.hpp>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>
+ Include dependency graph for bfs.cpp:

Go to the source code of this file.

Functions

BfsResult BFS (DIA< BfsNode > &graph, size_t graphSize, VertexId startIndex, bool full_bfs=false)
 runs A BFS on graph starting at startIndex. More...
 
BfsResult BFS (thrill::Context &ctx, std::string input_path, std::string output_path, VertexId startIndex, bool full_bfs=false)
 
bool BFSNextLevel (DIA< BfsNode > &graph, size_t &currentLevel, const size_t currentTreeIndex, const size_t graphSize)
 
size_t doubleSweepDiameter (thrill::Context &ctx, std::string input_path, std::string output_path, std::string output_path2, VertexId startIndex)
 
DIA< BfsNodeLoadBFSGraph (thrill::Context &ctx, size_t &graphSize, const std::string &path, VertexId startIndex)
 
int main (int argc, char *argv[])
 
void outputBFSResult (DIA< BfsNode > &graph, size_t num_trees, std::string output_path)
 
bool PrepareNextTree (DIA< BfsNode > &graph, size_t &startIndex, const size_t currentTreeIndex)
 

Function Documentation

BfsResult BFS ( DIA< BfsNode > &  graph,
size_t  graphSize,
VertexId  startIndex,
bool  full_bfs = false 
)

runs A BFS on graph starting at startIndex.

If full_bfs is true then all nodes will eventually be reached possibly resulting in a forest instead of a simple tree

Definition at line 217 of file bfs.cpp.

References BFSNextLevel(), and PrepareNextTree().

Referenced by BFS(), doubleSweepDiameter(), and main().

BfsResult BFS ( thrill::Context &  ctx,
std::string  input_path,
std::string  output_path,
VertexId  startIndex,
bool  full_bfs = false 
)

Definition at line 237 of file bfs.cpp.

References BFS(), LoadBFSGraph(), and outputBFSResult().

bool BFSNextLevel ( DIA< BfsNode > &  graph,
size_t &  currentLevel,
const size_t  currentTreeIndex,
const size_t  graphSize 
)
size_t doubleSweepDiameter ( thrill::Context &  ctx,
std::string  input_path,
std::string  output_path,
std::string  output_path2,
VertexId  startIndex 
)
DIA<BfsNode> LoadBFSGraph ( thrill::Context &  ctx,
size_t &  graphSize,
const std::string &  path,
VertexId  startIndex 
)
void outputBFSResult ( DIA< BfsNode > &  graph,
size_t  num_trees,
std::string  output_path 
)

Definition at line 164 of file bfs.cpp.

References examples::bfs::INVALID, BfsNode::level, BfsNode::nodeIndex, and BfsNode::treeIndex.

Referenced by BFS(), and doubleSweepDiameter().

bool PrepareNextTree ( DIA< BfsNode > &  graph,
size_t &  startIndex,
const size_t  currentTreeIndex 
)

Definition at line 131 of file bfs.cpp.

References examples::bfs::INVALID, BfsNode::level, BfsNode::nodeIndex, BfsNode::parent, and BfsNode::treeIndex.

Referenced by BFS().