#include <boost/assert.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/copy.hpp>
#include <boost/foreach.hpp>

#include <iostream>

struct Vertex
{
	Vertex(){}
	Vertex( const std::string& name )
		: _name(name) {}
	std::string _name;
};
struct Edge
{
	Edge(){}
	Edge( const std::string& name )
		: _name(name) {}
	std::string _name;
};

typedef boost::adjacency_list<
	boost::vecS,
	boost::listS, // dfs works with vecS, but not with listS because dfs use operator[]
	boost::bidirectionalS,
	Vertex,
	Edge,
	boost::no_property,
	boost::listS
	> GraphContainer;


class CycleDetector : public boost::default_dfs_visitor
{
public:
	CycleDetector()
		: _hasCycle( false )
	{}

	template<class EdgeDescriptor, class Graph>
	void back_edge( EdgeDescriptor, const Graph& )
	{
		_hasCycle = true;
	}

public:
	bool _hasCycle;
};

int main( int argc, char** argv )
{
	using namespace boost;
	typedef GraphContainer::vertex_descriptor vertex_descriptor;
	typedef GraphContainer::edge_descriptor edge_descriptor;
	GraphContainer graph;

	Vertex v1("v1");
	Vertex v2("v2");
	Vertex v3("v3");
	Vertex v4("v4");
	vertex_descriptor vd1 = boost::add_vertex( v1, graph );
	vertex_descriptor vd2 = boost::add_vertex( v2, graph );
	vertex_descriptor vd3 = boost::add_vertex( v3, graph );
	vertex_descriptor vd4 = boost::add_vertex( v4, graph );

	boost::add_edge( vd1, vd4, graph );
	boost::add_edge( vd1, vd2, graph );
	boost::add_edge( vd2, vd3, graph );
	boost::add_edge( vd1, vd3, graph );

	CycleDetector vis;
	boost::depth_first_search( graph,
							   boost::visitor( vis )
							   );

	return 0;
}