# Posted By

dirkchang on 01/25/11

# Statistics

Viewed 254 times
Favorited by 0 user(s)

# liarliar version B (using boost::graph, based on Kevin Bacon example)

/ Published in: C++
Save to your folder(s)

Copy this code and paste it in your HTML
`/* * main.cpp * *  Created on: 2011/1/24 *      Author: dirk */ #include <iostream>#include <fstream>#include <map>#include <vector>#include <string> #include <boost/graph/adjacency_list.hpp>#include <boost/graph/visitors.hpp>#include <boost/graph/breadth_first_search.hpp> // we use bundled property heretypedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph; typedef std::pair<size_t, size_t> Edge;typedef std::map<std::string, size_t> NameVertexMap;typedef std::vector<Edge> EdgeArray; template <typename DistanceMap>class bacon_number_recorder : public boost::default_bfs_visitor {public:	bacon_number_recorder(DistanceMap d) : _d(d) {} 	// overloading tree_edge function	template <typename Edge, typename Graph>	void tree_edge(Edge e, const Graph &g) const {		typename Graph::vertex_descriptor u = boost::source(e, g), v = boost::target(e, g);		_d[v] = _d[u] + 1;	} private:	DistanceMap _d;}; template <typename DistanceMap>static bacon_number_recorder<DistanceMap> record_bacon_number(DistanceMap d) {	return bacon_number_recorder<DistanceMap>(d);} int main(int argc, char **argv) {	// preparing the data	std::ifstream fin(argv[1]);	if(!fin) {		std::cerr << "Can't open data file, leaving...\n";		return EXIT_FAILURE;	} 	// reading the file	int i_no_chunks(0), i_no_accused(0);	NameVertexMap nvm_members;	NameVertexMap::iterator nvm_it;	bool b_inserted;	std::string str_accuser, str_accused;	EdgeArray edge_array;	size_t max_id(0), u(0), v(0); 	fin >> i_no_chunks;	edge_array.reserve(i_no_chunks * 5);	for(int i = 0; i < i_no_chunks; ++i) {		fin >> str_accuser >> i_no_accused; 		boost::tie(nvm_it, b_inserted) = nvm_members.insert(std::make_pair(str_accuser, max_id));		if(b_inserted) {			u = max_id;			++max_id;		} else {			u = nvm_it->second;		} 		for(int j = 0; j < i_no_accused; ++j) {			fin >> str_accused; 			boost::tie(nvm_it, b_inserted) = nvm_members.insert(std::make_pair(str_accused, max_id));			if(b_inserted) {				v = max_id;				++max_id;			} else {				v = nvm_it->second;			}			edge_array.push_back(std::make_pair(u,v));		}	}	Graph graph(&edge_array[0], &edge_array[edge_array.size()-1], nvm_members.size()); 	// processing the data	std::vector<int> bacon_number(boost::num_vertices(graph), 0);	bacon_number[0] = 0;	boost::breadth_first_search(graph, 0, boost::visitor(record_bacon_number(&bacon_number[0]))); 	// output the results	int i_groups[2] = {0,0};	Graph::vertex_iterator i, end;	for(boost::tie(i, end) = boost::vertices(graph); i != end; ++i) {		++i_groups[bacon_number[*i]%2];	} 	if(i_groups[0]>i_groups[1]) {		std::cout << i_groups[0] << ' ' << i_groups[1] << '\n';	} else {		std::cout << i_groups[1] << ' ' << i_groups[0] << '\n';	}}`

## Comments

Subscribe to comments

You need to login to post a comment.