//=======================================================================
// Graph Connectives: Union
// g1 and g2 are two graphs which users want to unite.
// G is the union graph of (g1,g2)
//=======================================================================

#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/tuple/tuple.hpp>

namespace boost {
	template <typename G_1_2_type, typename G_type>

	void copy_graph(G_1_2_type G_copy, G_type& G, int inc_position)	{

		graph_traits < G_1_2_type >::vertex_iterator i, end;
		graph_traits < G_1_2_type >::adjacency_iterator ai, a_end, next;
		property_map < G_1_2_type, vertex_index_t >::type
			index_map = get(vertex_index, G_copy);

		for (tie(i, end) = vertices(G_copy); i != end; ++i) {
			tie(ai, a_end) = adjacent_vertices(*i, G_copy);
			for (; ai != a_end; ++ai){ 
				int source = get(index_map, *i)		+ inc_position;
				int target = get(index_map, *ai)	+ inc_position;
				add_edge(source,	target,	G);
			}
		}
	}
	template <typename G1_type,typename G2_type, typename G_type>
	void graph_union(G1_type G1, G2_type G2, G_type& G){	
			// Copy graph 1 to G 
			int inc_position = 0;
			copy_graph<G1_type,G_type>(G1,	G,	inc_position);
			// Copy graph 2 to G but increase positions by the size of graph 1
			inc_position = num_vertices(G1);
			copy_graph<G2_type,G_type>(G2,	G,	inc_position);
	}
	
} // boost