#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:

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< BfsNode >	LoadBFSGraph (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

◆ BFS() [1/2]

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().

◆ BFS() [2/2]

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().

◆ BFSNextLevel()

bool BFSNextLevel	(	DIA< BfsNode > &	graph,
		size_t &	currentLevel,
		const size_t	currentTreeIndex,
		const size_t	graphSize
	)

Definition at line 84 of file bfs.cpp.

References DIA< ValueType_, Stack_ >::FlatMap(), examples::bfs::INVALID, BfsNode::level, NodeParentPair::node, and thrill::api::Zip().

Referenced by BFS().

◆ doubleSweepDiameter()

size_t doubleSweepDiameter	(	thrill::Context &	ctx,
		std::string	input_path,
		std::string	output_path,
		std::string	output_path2,
		VertexId	startIndex
	)

Definition at line 249 of file bfs.cpp.

References BFS(), BfsNode::edges, examples::bfs::INVALID, BfsNode::level, LoadBFSGraph(), LOG1, DIA< ValueType_, Stack_ >::Map(), Context::my_rank(), BfsNode::nodeIndex, and outputBFSResult().

Referenced by main().

◆ LoadBFSGraph()

DIA<BfsNode> LoadBFSGraph	(	thrill::Context &	ctx,
		size_t &	graphSize,
		const std::string &	path,
		VertexId	startIndex
	)

Definition at line 45 of file bfs.cpp.

References BfsNode::edges, BfsNode::level, BfsNode::nodeIndex, BfsNode::parent, thrill::api::ReadLines(), and BfsNode::treeIndex.

Referenced by BFS(), and doubleSweepDiameter().

◆ main()

int main	(	int	argc,
		char *	argv[]
	)

Examples:: examples/tutorial/k-means_step1.cpp, examples/tutorial/k-means_step2.cpp, examples/tutorial/k-means_step3.cpp, examples/tutorial/k-means_step4.cpp, examples/tutorial/k-means_step5.cpp, and examples/tutorial/k-means_step6.cpp.

Definition at line 301 of file bfs.cpp.

References CmdlineParser::add_flag(), CmdlineParser::add_opt_param_string(), CmdlineParser::add_param_string(), BFS(), doubleSweepDiameter(), CmdlineParser::print_result(), CmdlineParser::process(), and thrill::api::Run().

◆ outputBFSResult()

void outputBFSResult	(	DIA< BfsNode > &	graph,
		size_t	num_trees,
		std::string	output_path
	)

Definition at line 164 of file bfs.cpp.

References DIA< ValueType_, Stack_ >::Filter(), examples::bfs::INVALID, BfsNode::level, BfsNode::nodeIndex, and BfsNode::treeIndex.