#include <boost/property_map.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <vector>

/// A skeleton user defined graph not using any of the builtin Boost Graph Library graph types.
namespace MyGraph {

    class Graph;
    class Vertex;
    class Edge;

    typedef Vertex* VertexDesc;
    typedef Edge* EdgeDesc;
    typedef std::vector<EdgeDesc>::iterator EdgeIterator;
    typedef std::vector<VertexDesc>::iterator VertexIterator;

    class Vertex {
    public:
	unsigned int index();
	std::pair<EdgeIterator, EdgeIterator> outEdges() const;
	std::pair<EdgeIterator, EdgeIterator> inEdges() const;
	unsigned int outEdgeCount() const;
	unsigned int inEdgeCount() const;
	EdgeIterator outEdgeBegin() const;
	EdgeIterator outEdgeEnd() const;
	EdgeIterator inEdgeBegin() const;
	EdgeIterator inEdgeEnd() const;
	void clearEdges();
    };

    class Edge {
    public:
	unsigned int index() const;
	VertexDesc source() const;
	VertexDesc target() const;
    };

    class Graph {
    public:
	std::pair<EdgeIterator, EdgeIterator> edges() const;
	std::pair<VertexIterator, VertexIterator> vertices() const;
	unsigned int vertexCount() const;
	unsigned int edgeCount() const;
	std::pair<EdgeDesc, bool> findEdge(VertexDesc source, VertexDesc target) const;
	VertexDesc addVertex();
	void removeVertex(VertexDesc vertex);
	std::pair<EdgeDesc, bool> addEdge(VertexDesc source, VertexDesc target);
	void removeEdge(EdgeDesc edge);
    };

} // namespace MyGraph

/// An adapter to allow the user defined graph MyGraph to be used as a Boost Graph.
namespace boost {

    /// The Boost Graph Library algorithms use graph_traits to obtain
    /// information about the types to use to access the graph.
    template <>
    struct graph_traits<MyGraph::Graph> {

	// Our user defined graph models all of the following concepts:
	struct bidir_adj_list_traversal_tag : 
	    public virtual vertex_list_graph_tag,
	    public virtual incidence_graph_tag,
	    public virtual adjacency_graph_tag,
	    public virtual edge_list_graph_tag,
	    public virtual bidirectional_graph_tag { };

	// Graph requires:
	typedef MyGraph::VertexDesc			vertex_descriptor;
	typedef MyGraph::EdgeDesc			edge_descriptor;
	typedef directed_tag			        directed_category;
	typedef disallow_parallel_edge_tag	        edge_parallel_category;
	typedef bidir_adj_list_traversal_tag	        traversal_category;
	
	static inline vertex_descriptor null_vertex()
	{
	    return MyGraph::VertexDesc(0);
	}
	
	// IncidenceGraph requires:
	typedef MyGraph::EdgeIterator			out_edge_iterator;
	typedef unsigned int		                degree_size_type;
	
	// BidirectionalGraph requires:
	typedef MyGraph::EdgeIterator			in_edge_iterator;
	
	// Adjacency Graph requires:
	typedef adjacency_iterator_generator
  	    <MyGraph::Graph, vertex_descriptor, out_edge_iterator>::type
	                                                adjacency_iterator;
	
	// VertexListGraph requires:
	typedef MyGraph::VertexIterator			vertex_iterator;
	typedef unsigned int		                vertices_size_type;
	
	// EdgeListGraph requires:
	typedef MyGraph::EdgeIterator			edge_iterator;
	typedef unsigned int			        edges_size_type;
    };
    
} // namespace boost

/// In addition we must provide the following operations.
/// These definitions are logically part of MyGraph.
namespace MyGraph {

    /// IncidenceGraph refines Graph requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::out_edge_iterator,
	      boost::graph_traits<MyGraph::Graph>::out_edge_iterator>
    out_edges(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
	return v->outEdges();
    }

    inline
    boost::graph_traits<MyGraph::Graph>::vertex_descriptor
    source(boost::graph_traits<MyGraph::Graph>::edge_descriptor e, const MyGraph::Graph& g)
    {
	return e->source();
    }
    
    inline
    boost::graph_traits<MyGraph::Graph>::vertex_descriptor
    target(boost::graph_traits<MyGraph::Graph>::edge_descriptor e, const MyGraph::Graph& g)
    {
	return e->target();
    }
    
    inline
    boost::graph_traits<MyGraph::Graph>::degree_size_type
    out_degree(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
	return v->outEdgeCount();
    }
    
    
    /// BidirectionalGraph refines IncidenceGraph and requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::in_edge_iterator, boost::graph_traits<MyGraph::Graph>::in_edge_iterator>
    in_edges(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
	return v->inEdges();
    }
    
    inline
    boost::graph_traits<MyGraph::Graph>::degree_size_type
    in_degree(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
	return v->inEdgeCount();
    }
    
    inline
    boost::graph_traits<MyGraph::Graph>::degree_size_type
    degree(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
	return in_degree(v, g) + out_degree(v, g);
    }
    
    /// AdjacencyGraph refines Graph and requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::adjacency_iterator, boost::graph_traits<MyGraph::Graph>::adjacency_iterator>
    adjacent_vertices(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
	boost::graph_traits<MyGraph::Graph>::adjacency_iterator begin(v->outEdgeBegin(), &g);
	boost::graph_traits<MyGraph::Graph>::adjacency_iterator end(v->outEdgeEnd(), &g);
	return std::make_pair(begin, end);
    }
    
    /// VertexListGraph refines IncidenceGraph and AdjacencyGraph and requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::vertex_iterator, boost::graph_traits<MyGraph::Graph>::vertex_iterator>
    vertices(const MyGraph::Graph& g)
    {
	return g.vertices();
    }
    
    inline
    boost::graph_traits<MyGraph::Graph>::vertices_size_type
    num_vertices(const MyGraph::Graph& g)
    {
	return g.vertexCount();
    }
    
    /// EdgeListGraph refines Graph and requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::edge_iterator, boost::graph_traits<MyGraph::Graph>::edge_iterator>
    edges(const MyGraph::Graph& g)
    {
	return g.edges();
    }

    inline
    boost::graph_traits<MyGraph::Graph>::edges_size_type
    num_edges(const MyGraph::Graph& g)
    {
	return g.edgeCount();
    }
    
    /// AdjacencyMatrix refines Graph and requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::edge_descriptor, bool>
    edge(boost::graph_traits<MyGraph::Graph>::vertex_descriptor u,
	 boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
	return g.findEdge(u, v);
    }
    
    /// MutableGraph refines Graph and requires:
    inline
    boost::graph_traits<MyGraph::Graph>::vertex_descriptor
    add_vertex(MyGraph::Graph& g)
    {
	return g.addVertex();
    }
    
    inline
    void
    clear_vertex(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, MyGraph::Graph& g)
    {
	v->clearEdges();
    }
    
    inline
    void
    remove_vertex(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, MyGraph::Graph& g)
    {
	g.removeVertex(v);
    }
    
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::edge_descriptor, bool>
    add_edge(boost::graph_traits<MyGraph::Graph>::vertex_descriptor u, boost::graph_traits<MyGraph::Graph>::vertex_descriptor v,
	     MyGraph::Graph& g)
    {
	return g.addEdge(u, v);
    }
    
    inline
    void
    remove_edge(boost::graph_traits<MyGraph::Graph>::vertex_descriptor u, boost::graph_traits<MyGraph::Graph>::vertex_descriptor v,
		MyGraph::Graph& g)
    {
	std::pair<MyGraph::EdgeDesc, bool> edge_pair = g.findEdge(u, v);
	if (edge_pair.second){
	    g.removeEdge(edge_pair.first);
	}
	
    }
    
    inline
    void
    remove_edge(boost::graph_traits<MyGraph::Graph>::edge_descriptor e, MyGraph::Graph& g)
    {
	g.removeEdge(e);
    }
    
    inline
    void
    remove_edge(boost::graph_traits<MyGraph::Graph>::edge_iterator e_iter, MyGraph::Graph& g)
    {
	g.removeEdge(*e_iter);
    }
    
    /// We also need to provide the predefined property maps used by the algorithms we will use.

    /// The vertex_index_t property map:
    class VertexDescMap
	: public boost::put_get_helper<unsigned int, VertexDescMap>
    {
    public:
	typedef boost::readable_property_map_tag category;
	typedef unsigned int value_type;
	typedef unsigned int reference;
	typedef MyGraph::VertexDesc key_type;
	VertexDescMap()
	{
	}
	VertexDescMap(const MyGraph::Graph& g)
	{
	}
	
	unsigned int operator[](key_type v) const
	{
	    return v->index();
	}
    };
    
    inline 
    VertexDescMap
    get(boost::vertex_index_t, const MyGraph::Graph& g)
    {
	return VertexDescMap(g);
    }
    
    /// The edge_index_t property map:
    class EdgeDescMap
	: public boost::put_get_helper<EdgeDesc, EdgeDescMap>
    {
    public:
	typedef boost::readable_property_map_tag category;
	typedef unsigned int value_type;
	typedef unsigned int reference;
	typedef MyGraph::EdgeDesc key_type;
	EdgeDescMap()
	{
	}
	EdgeDescMap(const MyGraph::Graph& g)
	{
	}
	
	unsigned int operator[](key_type e) const
	{
	    return e->index();
	}
    };
    
    inline 
    EdgeDescMap
    get(boost::edge_index_t, const MyGraph::Graph& g)
    {
	return EdgeDescMap(g);
    }
    
} // namespace MyGraph

/// We must also provide specializations for property_map for our
/// graph for the predefined property maps we support.
///
/// NOTE: This mechanism is not currently described in the
/// documentation on how to provide an adapter for a user defined
/// graph.
namespace boost {
    
    template<>
    struct property_map<MyGraph::Graph, vertex_index_t>
    {
	typedef MyGraph::VertexDescMap type;
	
	/// The BGL graphs all seem to define their
	/// property_map<...>::const_type the same as their
	/// property_map<...>::type (ie both non-const). It seems that
	/// ::const_type ought to be the const version of ::type.
	/// However, making it a const type results in
	/// make_iterator_property_map not working.
	typedef const MyGraph::VertexDescMap const_type;
    };
    
    /// We also provide a specialization for the edge_index_t which serves
    /// the same purpose as vertex_index_t except for the edges.
    template<>
    struct property_map<MyGraph::Graph, edge_index_t>
    {
	typedef MyGraph::EdgeDescMap type;
	typedef const MyGraph::EdgeDescMap const_type;
    };

} // namespace boost