#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/circle_layout.hpp>
#include <boost/graph/kamada_kawai_spring_layout.hpp>

enum vertex_position_t { vertex_position };
namespace boost { BOOST_INSTALL_PROPERTY(vertex, position); }

typedef boost::rectangle_topology<> RectangleTopology;
typedef boost::rectangle_topology<>::point_type Point;

typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,
        // Vertex properties
        boost::property<boost::vertex_index_t, int,
        boost::property<vertex_position_t, Point> >,
        // Edge properties
        boost::property<boost::edge_weight_t, double> > Graph;

typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
typedef boost::graph_traits<Graph>::vertex_iterator VertexIterator;
typedef boost::graph_traits<Graph>::vertices_size_type VerticesSizeType;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDescriptor;
typedef boost::graph_traits<Graph>::edge_iterator EdgeIterator;
typedef boost::graph_traits<Graph>::edges_size_type EdgesSizeType;

struct kamada_kawai_done
{
    kamada_kawai_done(int maxGlobalIterations = 100, int maxLocalIterations = 1000)
        : lastDelta_()
        , maxGlobalIterations_(maxGlobalIterations)
        , globalIterations_(0)
        , maxLocalIterations_(maxLocalIterations)
        , localIterations_(0)
    {}

    template<typename Graph>
    bool operator()(double delta_p,
                    typename boost::graph_traits<Graph>::vertex_descriptor /*p*/,
                    const Graph& /*g*/,
                    bool global)
    {
        //qDebug() << "Iteration =" << globalIterations_ << "/" << localIterations_;
        if(globalIterations_ >= maxGlobalIterations_
                || localIterations_ >= maxLocalIterations_)
            return true;

        if (global)
        {
            double diff = lastDelta_ - delta_p;
            if (diff < 0) diff = -diff;
            lastDelta_ = delta_p;
            ++globalIterations_;
            localIterations_ = 0;
            return diff < 0.01;
        }
        else
        {
            ++localIterations_;
            return delta_p < 0.01;
        }
    }

    double lastDelta_;
    int maxGlobalIterations_;
    int globalIterations_;
    int maxLocalIterations_;
    int localIterations_;
};

int main()
{
    // Create a simple graph
    Graph graph(3);

    VertexIterator vi = boost::vertices(graph).first;
    std::vector<VertexDescriptor> vertices;
    for(int i = 0; i < 3; ++i, ++vi)
    {
        boost::put(boost::vertex_index, graph, *vi, static_cast<size_t>(i));
        Point p;
        p[0] = 10*(i+1);
        p[1] = 20*(i+2);
        boost::put(vertex_position, graph, *vi, p);
        vertices.push_back(*vi);
    }

    std::pair<EdgeDescriptor, bool> result;

    result = boost::add_edge(vertices[0], vertices[1], graph);
    boost::put(boost::edge_weight, graph, result.first, 1.0);

    result = boost::add_edge(vertices[0], vertices[2], graph);
    boost::put(boost::edge_weight, graph, result.first, 1.0);

    // Create a simple rectangular topology to layout within
    boost::minstd_rand randomGenerator;
    randomGenerator.seed(time(0));

    RectangleTopology layoutTopology(randomGenerator, 0.0, 0.0, 19.18, 14.29);

    boost::circle_graph_layout(graph, boost::get(vertex_position, graph), 100.0);
    boost::kamada_kawai_spring_layout(graph,
                                      boost::get(vertex_position, graph),
                                      boost::get(boost::edge_weight, graph),
                                      layoutTopology,
                                      boost::edge_length(3.0),
                                      kamada_kawai_done());

    return 0;
}