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

#include <iostream>
#include <algorithm>

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::vecS,
	boost::bidirectionalS,
	Vertex,
	Edge,
	boost::no_property,
	boost::listS
	> GraphContainer;


template<class TGraph>
class OrderEdge
{
public:
	typedef typename TGraph::edge_descriptor edge_descriptor;

	OrderEdge( const TGraph& graph )
		: _graph( graph )
	{}

	inline bool operator()( const edge_descriptor& ed1, const edge_descriptor& ed2 ) const
	{
		const Vertex& v1 = _graph[ target( ed1, _graph ) ];
		const Vertex& v2 = _graph[ target( ed2, _graph ) ];
		return v1._name < v2._name;
	}
private:
	const TGraph& _graph;
};

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 );

	BOOST_FOREACH( GraphContainer::vertex_descriptor vd, vertices( graph ) )
	{
		Vertex& v = graph[vd];
		std::cout << "------------------------------" << std::endl;
		std::cout << "- before sort edges of " << v._name << std::endl;
		BOOST_FOREACH( GraphContainer::edge_descriptor ed, boost::out_edges( vd, graph ) )
		{
			std::cout << " * " <<  graph[target(ed, graph)]._name << std::endl;
		}

		GraphContainer::out_edge_iterator oe_it, oe_itEnd;
		boost::tie( oe_it, oe_itEnd ) = boost::out_edges( vd, graph );
		std::sort( oe_it, oe_itEnd, OrderEdge<GraphContainer>(graph) );
//		GraphContainer::edge_descriptor tmp = *oe_it;
//		*(oe_it) = *(oe_it+1);
//		*(oe_it+1) = tmp;

		std::cout << "- after sort edges of " << v._name << std::endl;
		BOOST_FOREACH( GraphContainer::edge_descriptor ed, boost::out_edges( vd, graph ) )
		{
			std::cout << " * " <<  graph[target(ed, graph)]._name << std::endl;
		}
	}

	return 0;
}