/*
 *  ex_is_reachable.cpp
 *
 * Formatted with tabstops = 4
 *
 */

#include <utility>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/graph_traits.hpp>

template<typename Vertex> 
class reachability_checker : public boost::default_bfs_visitor
{
public:
	reachability_checker(Vertex target, bool& result)
		: m_target(target), m_result(result) {}
	
	template<typename V, typename G>
	void discover_vertex(V u, const G &)
	{
		if (u == m_target)
			m_result = true;
	}

private:
	Vertex	m_target;
	bool&	m_result;
};

// return true if the target is reachable from the source
template<typename Graph>
inline bool
is_reachable(
	typename boost::graph_traits<Graph>::vertex_descriptor source,
	typename boost::graph_traits<Graph>::vertex_descriptor target, const Graph& g)
{
	typedef typename boost::graph_traits<Graph>::vertex_descriptor	Vertex;

	bool							result = false;
	reachability_checker<Vertex>	vis(target, result);

	boost::breadth_first_search(g, source, boost::visitor(vis));
	
	return result;
}

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

int
main()
{
	using namespace boost;

    typedef adjacency_list<vecS, vecS, directedS>	Graph;
    typedef std::pair<int, int>						Edge;
	typedef graph_traits<Graph>::edge_descriptor	edge_type;
	
    // Make labels for the vertices
    enum { A, B, C, D, E, N };
    const int	num_vertices = N;
    const char*	name = "ABCDE";
	
    Edge		edge_array[] =
				{ Edge(A, C), Edge(B, D), Edge(B, E),
				  Edge(C, B), Edge(C, D), Edge(D, E) };
    const int	num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
	
    // declare a graph object
	Graph			g(edge_array, edge_array + num_edges, num_vertices);
	
	// print the graph before attempting to add edges
	std::cout << "DAG before adding another acyclic edge:\n";
	print_graph(g, name);
	
	// attempt to add an edge that would create a directed cycle
	std::cout << "Attempting to add directed cycle edge D -> A\n";
	if (! is_reachable(A, D, g) )
	{
		std::cout << "ERROR: directed cycle allowed!\n";
		return 1;
	}
	else
	{
		std::cout << "Edge D -> A correctly refused\n";
	}
	
	// attempt to add an edge that would not create a directed cycle
	std::cout << "Attempting to add acyclic edge A -> D\n";
	if ( is_reachable(D, A, g) )
	{
		std::cout << "ERROR: acyclic edge refused!\n";
		return 2;
	}
	else
	{
		std::cout << "Edge A -> D correctly accdepted\n";
		add_edge(A, D, g);
	}
	
	// print the graph after attempting to add edges
	std::cout << "DAG after adding another acyclic edge:\n";
	print_graph(g, name);
	
	return 0;
}