graph_cairo_draw.cc

// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006-2017 Tiago de Paula Peixoto <tiago@skewed.de>
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 3
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#include "graph.hh"

#ifdef HAVE_CAIROMM

#include "graph_filtering.hh"

#include <boost/python.hpp>
#include <boost/utility/enable_if.hpp>

#include "graph_selectors.hh"
#include "graph_properties.hh"

#include <iostream>
#include <array>
#include <chrono>

#include "hash_map_wrap.hh"
#include "demangle.hh"

#include "coroutine.hh"
#include "graph_python_interface.hh"

#include <cairommconfig.h>
#include <cairomm/context.h>
#include <cairomm/surface.h>
#include PYCAIRO_HEADER

#include <boost/mpl/map/map50.hpp>

using namespace std;
using namespace boost;
using namespace graph_tool;

enum vertex_attr_t {
    VERTEX_SHAPE = 100,
    VERTEX_COLOR,
    VERTEX_FILL_COLOR,
    VERTEX_SIZE,
    VERTEX_ASPECT,
    VERTEX_ROTATION,
    VERTEX_ANCHOR,
    VERTEX_PENWIDTH,
    VERTEX_HALO,
    VERTEX_HALO_COLOR,
    VERTEX_HALO_SIZE,
    VERTEX_TEXT,
    VERTEX_TEXT_COLOR,
    VERTEX_TEXT_POSITION,
    VERTEX_TEXT_ROTATION,
    VERTEX_TEXT_OFFSET,
    VERTEX_FONT_FAMILY,
    VERTEX_FONT_SLANT,
    VERTEX_FONT_WEIGHT,
    VERTEX_FONT_SIZE,
    VERTEX_SURFACE,
    VERTEX_PIE_FRACTIONS,
    VERTEX_PIE_COLORS,
};

enum edge_attr_t {
    EDGE_COLOR = 200,
    EDGE_PENWIDTH,
    EDGE_START_MARKER,
    EDGE_MID_MARKER,
    EDGE_END_MARKER,
    EDGE_MARKER_SIZE,
    EDGE_MID_MARKER_POSITION,
    EDGE_CONTROL_POINTS,
    EDGE_DASH_STYLE,
    EDGE_GRADIENT,
    EDGE_TEXT,
    EDGE_TEXT_COLOR,
    EDGE_TEXT_DISTANCE,
    EDGE_TEXT_PARALLEL,
    EDGE_FONT_FAMILY,
    EDGE_FONT_SLANT,
    EDGE_FONT_WEIGHT,
    EDGE_FONT_SIZE,
    EDGE_SLOPPY,
    EDGE_SEAMLESS
};

enum vertex_shape_t {
    SHAPE_CIRCLE = 300,
    SHAPE_TRIANGLE,
    SHAPE_SQUARE,
    SHAPE_PENTAGON,
    SHAPE_HEXAGON,
    SHAPE_HEPTAGON,
    SHAPE_OCTAGON,
    SHAPE_DOUBLE_CIRCLE,
    SHAPE_DOUBLE_TRIANGLE,
    SHAPE_DOUBLE_SQUARE,
    SHAPE_DOUBLE_PENTAGON,
    SHAPE_DOUBLE_HEXAGON,
    SHAPE_DOUBLE_HEPTAGON,
    SHAPE_DOUBLE_OCTAGON,
    SHAPE_PIE,
    SHAPE_NONE
};

enum edge_marker_t {
    MARKER_SHAPE_NONE = 400,
    MARKER_SHAPE_ARROW,
    MARKER_SHAPE_CIRCLE,
    MARKER_SHAPE_SQUARE,
    MARKER_SHAPE_DIAMOND,
    MARKER_SHAPE_BAR
};

typedef pair<double, double> pos_t;
typedef std::tuple<double, double, double, double> color_t;
typedef gt_hash_map<int, boost::any> attrs_t;

typedef boost::mpl::map43<
    boost::mpl::pair<boost::mpl::int_<VERTEX_SHAPE>, vertex_shape_t>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_COLOR>, color_t>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_FILL_COLOR>, color_t>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_SIZE>, double>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_ASPECT>, double>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_ROTATION>, double>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_ANCHOR>, int32_t>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_PENWIDTH>, double>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_HALO>, uint8_t>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_HALO_COLOR>, color_t>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_HALO_SIZE>, double>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_TEXT>, string>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_TEXT_COLOR>, color_t>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_TEXT_POSITION>, double>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_TEXT_ROTATION>, double>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_TEXT_OFFSET>, vector<double> >,
    boost::mpl::pair<boost::mpl::int_<VERTEX_FONT_FAMILY>, string>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_FONT_SLANT>, int32_t>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_FONT_WEIGHT>, int32_t>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_FONT_SIZE>, double>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_SURFACE>, boost::python::object>,
    boost::mpl::pair<boost::mpl::int_<VERTEX_PIE_FRACTIONS>, vector<double> >,
    boost::mpl::pair<boost::mpl::int_<VERTEX_PIE_COLORS>, vector<color_t> >,
    boost::mpl::pair<boost::mpl::int_<EDGE_COLOR>, color_t>,
    boost::mpl::pair<boost::mpl::int_<EDGE_PENWIDTH>, double>,
    boost::mpl::pair<boost::mpl::int_<EDGE_START_MARKER>, edge_marker_t>,
    boost::mpl::pair<boost::mpl::int_<EDGE_MID_MARKER>, edge_marker_t>,
    boost::mpl::pair<boost::mpl::int_<EDGE_END_MARKER>, edge_marker_t>,
    boost::mpl::pair<boost::mpl::int_<EDGE_MARKER_SIZE>, double>,
    boost::mpl::pair<boost::mpl::int_<EDGE_MID_MARKER_POSITION>, double>,
    boost::mpl::pair<boost::mpl::int_<EDGE_CONTROL_POINTS>, vector<double> >,
    boost::mpl::pair<boost::mpl::int_<EDGE_DASH_STYLE>, vector<double> >,
    boost::mpl::pair<boost::mpl::int_<EDGE_GRADIENT>, vector<double> >,
    boost::mpl::pair<boost::mpl::int_<EDGE_TEXT>, string>,
    boost::mpl::pair<boost::mpl::int_<EDGE_TEXT_COLOR>, color_t>,
    boost::mpl::pair<boost::mpl::int_<EDGE_TEXT_DISTANCE>, double>,
    boost::mpl::pair<boost::mpl::int_<EDGE_TEXT_PARALLEL>, uint8_t>,
    boost::mpl::pair<boost::mpl::int_<EDGE_FONT_FAMILY>, string>,
    boost::mpl::pair<boost::mpl::int_<EDGE_FONT_SLANT>, int32_t>,
    boost::mpl::pair<boost::mpl::int_<EDGE_FONT_WEIGHT>, int32_t>,
    boost::mpl::pair<boost::mpl::int_<EDGE_FONT_SIZE>, double>,
    boost::mpl::pair<boost::mpl::int_<EDGE_SLOPPY>, uint8_t>,
    boost::mpl::pair<boost::mpl::int_<EDGE_SEAMLESS>, uint8_t> >
        attr_types;

namespace std
{
ostream& operator<<(ostream& out, const color_t& c)
{
    out << std::get<0>(c) << " " << std::get<1>(c) << " " << std::get<2>(c) << " " << std::get<3>(c);
    return out;
}

istream& operator>>(istream& in, color_t& c)
{
    in >> std::get<0>(c) >> std::get<1>(c) >> std::get<2>(c) >> std::get<3>(c);
    return in;
}
}

istream& operator>>(istream& in, vertex_shape_t& c)
{
    int tmp;
    in >> tmp;
    c = vertex_shape_t(tmp);
    return in;
}

istream& operator>>(istream& in, edge_marker_t& c)
{
    int tmp;
    in >> tmp;
    c = edge_marker_t(tmp);
    return in;
}

namespace boost
{
template <>
string lexical_cast<string,python::object>(const python::object& val)
{
    return python::extract<string>(val);
}
}

template <class T1, class T2>
struct specific_convert;

template <class Type1, class Type2>
struct Converter
{
    Type1 operator()(const Type2& v) const
    {
        return do_convert(v, std::is_convertible<Type2,Type1>());
    }

    Type1 do_convert(const Type2& v, std::true_type) const
    {
        return Type1(v);
    }

    Type1 do_convert(const Type2& v, std::false_type) const
    {
        try
        {
            return specific_convert<Type1,Type2>()(v);
        }
        catch (bad_lexical_cast&)
        {
            string name1 = name_demangle(typeid(Type1).name());
            string name2 = name_demangle(typeid(Type2).name());
            string val_name;
            try
            {
                val_name = lexical_cast<string>(v);
            }
            catch (bad_lexical_cast)
            {
                val_name = "<no lexical cast available>";
            }
            throw GraphException("error converting from type '" + name2 +
                                 "' to type '" + name1 + "', val: " + val_name);
        }
    }

    template <class T1, class T2, class Enable = void>
    struct specific_convert
    {
        T1 operator()(const T2& v) const
        {
            return dispatch(v, typename std::is_convertible<T2, T1>::type());
        }

        T1 dispatch(const T2& v, std::true_type) const
        {
            return T1(v);
        }

        T1 dispatch(const T2& v, std::false_type) const
        {
            return lexical_cast<T1>(v);
        }
    };

    template <class T1> // noop
    struct specific_convert<T1, T1>
    {
        T1 operator()(const T1& v) const
        {
            return v;
        }
    };

    // specific specializations
    // string
    template <class T1>
    struct specific_convert<T1, string>
    {
        T1 operator()(const string& v) const
        {
            //uint8_t is not char, it is bool!
            if (std::is_same<T1, uint8_t>::value)
                return convert<T1,int>()(lexical_cast<int>(v));
            else
                return lexical_cast<T1>(v);
        }
    };

    // boost::python::object
    template <class T1>
    struct specific_convert<T1,boost::python::object>
    {
        T1 operator()(const boost::python::object& v) const
        {
            boost::python::extract<T1> x(v);
            if (x.check())
                return x();
            else
                throw bad_lexical_cast();
        }
    };

    template <class T2>
    struct specific_convert<string, T2,
                            typename std::enable_if
                            <boost::mpl::not_<
                                 std::is_same<T2,boost::python::object> >::type::value>::type>
    {
        string operator()(const T2& v) const
        {
            //uint8_t is not char, it is bool!
            if (std::is_same<T2, uint8_t>::value)
                return convert<string, int>()(lexical_cast<int>(v));
            else
                return lexical_cast<string>(v);
        }
    };

    // vectors
    template <class T1, class T2>
    struct specific_convert<vector<T1>, vector<T2> >
    {
        vector<T1> operator()(const vector<T2>& v) const
        {
            vector<T1> v2(v.size());
            convert<T1,T2> c;
            for (size_t i = 0; i < v.size(); ++i)
                v2[i] = c(v[i]);
            return v2;
        }
    };

    // color_t
    template <class T2>
    struct specific_convert<color_t, vector<T2> >
    {
        specific_convert<double, T2> c;
        color_t operator()(const vector<T2>& cv) const
        {
            if (cv.size() < 3)
                return std::make_tuple(0., 0., 0., 0.);
            if (cv.size() < 4)
                return std::make_tuple(c(cv[0]), c(cv[1]), c(cv[2]), 1.);
            return std::make_tuple(c(cv[0]), c(cv[1]), c(cv[2]), c(cv[3]));
        }
    };

    // vector<color_t>
    template <class T2>
    struct specific_convert<vector<color_t>, vector<T2> >
    {
        specific_convert<double, T2> c;
        vector<color_t> operator()(const vector<T2>& cv) const
        {
            if (cv.size() < 4)
                throw bad_lexical_cast();
            vector<color_t> color;
            for (size_t i = 0; i < cv.size() / 4; ++i)
            {
                if (4 * i + 3 >= cv.size())
                    throw bad_lexical_cast();
                color.push_back(std::make_tuple(c(cv[4*i]), c(cv[4*i + 1]),
                                                c(cv[4*i + 2]), c(cv[4*i + 3])));
            }
            return color;
        }
    };

    // vertex_shape_t
    template <class T2>
    struct specific_convert<vertex_shape_t, T2,
                            typename std::enable_if
                            <boost::mpl::and_<typename boost::mpl::not_<
                                                  std::is_same<T2,string> >::type,
                                              typename boost::mpl::not_<
                                                  std::is_same<T2,boost::python::object> >::type>::type::value>::type>
    {
        specific_convert<int, T2> c;
        vertex_shape_t operator()(const T2& v) const
        {
            return static_cast<vertex_shape_t>(c(v));
        }
    };

    // edge_marker_t
    template <class T2>
    struct specific_convert<edge_marker_t, T2,
                            typename std::enable_if
                            <boost::mpl::and_<typename boost::mpl::not_<
                                                  std::is_same<T2,string> >::type,
                                              typename boost::mpl::not_<
                                                  std::is_same<T2,boost::python::object> >::type>::type::value>::type>
    {
        specific_convert<int, T2> c;
        edge_marker_t operator()(const T2& v) const
        {
            return static_cast<edge_marker_t>(c(v));
        }
    };
};


template <class Descriptor>
class AttrDict
{
public:
    AttrDict(Descriptor descriptor, attrs_t& attrs, attrs_t& defaults)
        : _descriptor(descriptor), _attrs(attrs), _defaults(defaults) {}

    template <class Value>
    Value get(int k)
    {
        auto iter = _attrs.find(k);
        if (iter != _attrs.end())
        {
            typedef DynamicPropertyMapWrap<Value, Descriptor, Converter> pmap_t;
            pmap_t pmap(any_cast<pmap_t>(iter->second));
            return pmap.get(_descriptor);
        }
        try
        {
            return any_cast<Value>(_defaults[k]);
        }
        catch (bad_any_cast&)
        {
            throw ValueException("Error getting attribute " + lexical_cast<string>(k) +
                                 ", wanted: " + name_demangle(typeid(Value).name()) +
                                 ", got: " + name_demangle(_defaults[k].type().name()));
        }
    }

private:
    Descriptor _descriptor;
    attrs_t& _attrs;
    attrs_t& _defaults;
};

void draw_polygon(size_t N, double radius, Cairo::Context& cr)
{
    cr.save();
    cr.rotate(M_PI * (1. / 2 - 1. / N));
    cr.move_to(radius, 0);
    for (size_t i = 0; i < N; ++i)
    {
        double angle = (2 * M_PI * (i + 1)) / N;
        cr.line_to(radius * cos(angle), radius * sin(angle));
    }
    cr.close_path();
    cr.restore();
}

double get_polygon_anchor(size_t N, double radius, double angle)
{
    double theta = angle - M_PI * (1. / 2 - 1. / N);
    if (N % 2 == 0)
        theta += M_PI / N;
    if (theta > 2 * M_PI)
        theta -= 2 * M_PI;
    if (theta < 2 * M_PI)
        theta += 2 * M_PI;
    theta = fmod(theta, 2. * M_PI / N);
    if (theta > M_PI / N)
        theta -= 2. * M_PI / N;
    return radius * cos(M_PI / N) / cos(theta);
}


void draw_pie(double radius, const vector<double>& f,
              const vector<color_t>& colors, Cairo::Context& cr)
{
    if (colors.empty())
        throw ValueException("No pie colors!");
    double s = 0;
    for (size_t i = 0; i < f.size(); ++i)
        s += f[i];
    double last = 0;
    double pos = 0;
    cr.save();
    cr.begin_new_path();
    for (size_t i = 0; i < f.size(); ++i)
    {
        pos += f[i];
        double angle = (2 * pos * M_PI) / s;
        cr.move_to(0, 0);
        cr.arc(0, 0, radius, last, angle);
        last = angle;
        size_t j = i % colors.size();
        cr.set_source_rgba(get<0>(colors[j]),
                           get<1>(colors[j]),
                           get<2>(colors[j]),
                           get<3>(colors[j]));
        cr.fill();
    }
    cr.restore();
}


void move_radially(pos_t& pos, const pos_t& origin, double dr)
{
    double angle = atan2(pos.second - origin.second,
                         pos.first - origin.first);
    if (angle < 0)
        angle += 2 * M_PI;
    pos.first += dr * cos(angle);
    pos.second += dr * sin(angle);
}

double get_user_dist(Cairo::Context& cr, double norm = 1.)
{
    double x = norm / sqrt(2.), y = norm / sqrt(2.);
    cr.device_to_user_distance(x, y);
    return sqrt(x * x + y * y);
}

void get_surface_size(Cairo::RefPtr<Cairo::Surface> sfc,
                      double& width, double& height)
{
    Cairo::RefPtr<Cairo::Context> cr = Cairo::Context::create(sfc);
    double x1, x2, y1, y2;

    cr->get_clip_extents(x1, y1, x2, y2);

    width = x2 - x1;
    height = y2 - y1;
}

double dist(const pos_t& p1, const pos_t& p2)
{
    return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2));
};

double get_spline_len(const vector<double>& cts)
{
    double len = 0;
    for (size_t i = 0; i + 7 < cts.size(); i += 6)
    {
        double dx = cts[i + 6] - cts[i];
        double dy = cts[i + 6 + 1] - cts[i + 1];
        len += sqrt(dx * dx + dy * dy);
    }
    return len;
}

pos_t get_spline_point(const vector<double>& cts, double d)
{
    pos_t p;
    double pos = 0;
    for (size_t i = 0; i + 7 < cts.size(); i += 6)
    {
        double dx = cts[i + 6] - cts[i];
        double dy = cts[i + 6 + 1] - cts[i + 1];
        double l = sqrt(dx * dx + dy * dy);
        if (l < 1e-8)
            continue;
        if (pos + l >= d || i + 13 >= cts.size())
        {
            double t = 1 - (pos + l - d) / l;

            p.first = pow(1 - t, 3) * cts[i] +
                3 * t * pow(1 - t, 2) * cts[i + 2] +
                3 * t * t * (1 - t) * cts[i + 4] +
                t * t * t * cts[i + 6];

            p.second = pow(1 - t, 3) * cts[i + 1] +
                3 * t * pow(1 - t, 2) * cts[i + 3] +
                3 * t * t * (1 - t) * cts[i + 5] +
                t * t * t * cts[i + 7];
            break;
        }
        pos += l;
    }
    return p;
}

pos_t get_spline_diff(const vector<double>& cts, double d)
{
    pos_t diff;
    double pos = 0;
    for (size_t i = 0; i + 7 < cts.size(); i += 6)
    {
        double dx = cts[i + 6] - cts[i];
        double dy = cts[i + 6 + 1] - cts[i + 1];
        double l = sqrt(dx * dx + dy * dy);
        if (l < 1e-8)
            continue;
        if (pos + l >= d || i + 13 >= cts.size())
        {
            double t = 1 - (pos + l - d) / l;

            diff.first = -3 * pow(1 - t, 2) * cts[i] +
                (3 * pow(1 - t, 2) - 6 * t * (1-t)) * cts[i + 2] +
                (-3 * t * t + 6 * t * (1 - t)) * cts[i + 4] +
                3 * t * t * cts[i + 6];

            diff.second= -3 * pow(1 - t, 2) * cts[i + 1] +
                (3 * pow(1 - t, 2) - 6 * t * (1-t)) * cts[i + 3] +
                (-3 * t * t + 6 * t * (1 - t)) * cts[i + 5] +
                3 * t * t * cts[i + 7];
            break;
        }
        pos += l;
    }
    return diff;
}

template <class Descriptor>
class VertexShape
{
public:
    VertexShape(pos_t& pos, AttrDict<Descriptor> attrs)
        : _pos(pos), _attrs(attrs)

    {}

    double get_size(Cairo::Context& cr)
    {
        double size = _attrs.template get<double>(VERTEX_SIZE);
        size = get_user_dist(cr, size);

        string text = _attrs.template get<string>(VERTEX_TEXT);
        if (text != "")
        {
            double text_pos = _attrs.template get<double>(VERTEX_TEXT_POSITION);
            if (text_pos == -1)
            {
                cr.select_font_face(_attrs.template get<string>(VERTEX_FONT_FAMILY),
                                    static_cast<Cairo::FontSlant>(_attrs.template get<int32_t>(VERTEX_FONT_SLANT)),
                                    static_cast<Cairo::FontWeight>(_attrs.template get<int32_t>(VERTEX_FONT_WEIGHT)));
                cr.set_font_size(get_user_dist(cr, _attrs.template get<double>(VERTEX_FONT_SIZE)));
                Cairo::TextExtents extents;
                cr.get_text_extents(text, extents);
                double s = max(extents.width, extents.height) * 1.4;
                vertex_shape_t shape = _attrs.template get<vertex_shape_t>(VERTEX_SHAPE);
                if (shape >= SHAPE_DOUBLE_CIRCLE && shape != SHAPE_PIE)
                {
                    s /= 0.7;
                    double pw = _attrs.template get<double>(VERTEX_PENWIDTH);
                    pw = get_user_dist(cr, pw);
                    s += pw;
                }
                size = max(size, s);
            }
        }
        return size;
    }

    pos_t get_anchor(const pos_t& origin, Cairo::Context& cr,
                     bool force_border=false)
    {
        int anchor_type =_attrs.template get<int32_t>(VERTEX_ANCHOR);
        if (anchor_type == 0 && !force_border)
            return _pos;

        double angle = atan2(_pos.second - origin.second,
                             _pos.first - origin.first);
        double rot = _attrs.template get<double>(VERTEX_ROTATION);

        if (angle < 0)
            angle += 2 * M_PI;

        double r = get_size(cr) / 2;
        double dr = r;

        double pw = _attrs.template get<double>(VERTEX_PENWIDTH);
        pw = get_user_dist(cr, pw);
        r += pw / 2.5;

        pos_t anchor;
        size_t nsides = 0;
        vertex_shape_t shape = _attrs.template get<vertex_shape_t>(VERTEX_SHAPE);
        switch (shape)
        {
        case SHAPE_TRIANGLE:
        case SHAPE_SQUARE:
        case SHAPE_PENTAGON:
        case SHAPE_HEXAGON:
        case SHAPE_HEPTAGON:
        case SHAPE_OCTAGON:
        case SHAPE_DOUBLE_TRIANGLE:
        case SHAPE_DOUBLE_SQUARE:
        case SHAPE_DOUBLE_PENTAGON:
        case SHAPE_DOUBLE_HEXAGON:
        case SHAPE_DOUBLE_HEPTAGON:
        case SHAPE_DOUBLE_OCTAGON:
            nsides = shape - SHAPE_TRIANGLE + 3;
            if (nsides > 8)
                nsides -= 7;
            dr = get_polygon_anchor(nsides, r, angle - rot);
            break;
        case SHAPE_CIRCLE:
        case SHAPE_DOUBLE_CIRCLE:
        case SHAPE_PIE:
            dr = r;
            break;
        case SHAPE_NONE:
            break;
        default:
            throw ValueException("Invalid vertex shape: " +
                                 lexical_cast<string>(int(_attrs.template get<vertex_shape_t>(VERTEX_SHAPE))));
        }

        double aspect = _attrs.template get<double>(VERTEX_ASPECT);

        anchor = _pos;
        anchor.first -= dr * cos(angle) * aspect;
        anchor.second -= dr * sin(angle);

        return anchor;
    }

    std::pair<pos_t, double> get_anchor_spline(const vector<double>& cts,
                                               Cairo::Context& cr,
                                               bool loop = false,
                                               bool src = false)
    {
        double len = get_spline_len(cts);
        double x, one;
        pos_t p0 = get_spline_point(cts, 0);
        pos_t p1 = get_spline_point(cts, len);
        if (dist(p0, _pos) < dist(p1, _pos) || (loop && src))
        {
            x = 1;
            one = 1;
        }
        else
        {
            x = 0;
            one = -1;
        }

        int anchor_type =_attrs.template get<int32_t>(VERTEX_ANCHOR);
        if (anchor_type == 0)
            return make_pair(_pos, x);

        if (loop)
            x = 0.5;

        double dl = 0.5;
        pos_t pos, anchor;
        pos = get_spline_point(cts, len * x);
        anchor = get_anchor(pos, cr);
        if (dist(anchor, _pos) == 0 || dist(pos, _pos) < dist(anchor, _pos))
            return make_pair(_pos, x * len);

        size_t i = 0;
        while (abs(dist(pos, anchor)) > 1e-6)
        {
            double nx = min(max(x - dl * one, 0.), 1.);
            pos = get_spline_point(cts, len * nx);
            anchor = get_anchor(pos, cr);
            size_t j = 0;
            while (dist(pos, _pos) < dist(anchor, _pos)) // x is inside
            {
                dl /= 2;
                nx = min(max(x - dl * one, 0.), 1.);
                pos = get_spline_point(cts, len * nx);
                anchor = get_anchor(pos, cr);
                j++;
                if (nx == 0. || nx == 1. || j > 100)
                    break;
            }

            x = nx;
            dl = min(dist(pos, anchor) / len, 0.5);
            i++;
            if (i > 1000)
                break;
        }
        return make_pair(pos, x * len);
    }

    pos_t get_pos()
    {
        return _pos;
    }

    void draw(Cairo::Context& cr, bool outline=false)
    {
        color_t color, fillcolor;
        double size, pw;
        size = get_size(cr);

        std::array<double, 4> clip;
        cr.get_clip_extents(clip[0], clip[1], clip[2], clip[3]);
        if ((_pos.first + 2 * size < clip[0] && _pos.second + 2 * size < clip[1]) ||
            (_pos.first - 2 * size > clip[2] && _pos.second - 2 * size > clip[3]))
            return;

        double aspect = _attrs.template get<double>(VERTEX_ASPECT);
        double rot = _attrs.template get<double>(VERTEX_ROTATION);

        if (!outline)
            cr.save();
        cr.translate(_pos.first, _pos.second);
        cr.rotate(rot);

        if (!outline && _attrs.template get<uint8_t>(VERTEX_HALO))
        {
            color_t c = _attrs.template get<color_t>(VERTEX_HALO_COLOR);
            double hs = _attrs.template get<double>(VERTEX_HALO_SIZE);
            cr.set_source_rgba(get<0>(c), get<1>(c), get<2>(c), get<3>(c));
            if (aspect != 1.)
            {
                cr.save();
                cr.scale(aspect, 1.0);
            }
            cr.arc(0, 0, size * hs / 2, 0, 2 * M_PI);
            cr.fill();
            if (aspect != 1.)
                cr.restore();
        }

        boost::python::object osrc = _attrs.template get<boost::python::object>(VERTEX_SURFACE);

        pw =_attrs.template get<double>(VERTEX_PENWIDTH);
        pw = get_user_dist(cr, pw);
        cr.set_line_width(pw);

        if (!outline)
        {
            color = _attrs.template get<color_t>(VERTEX_COLOR);
            cr.set_source_rgba(get<0>(color), get<1>(color), get<2>(color),
                               get<3>(color));
        }

        size_t nsides = 0;
        vertex_shape_t shape = _attrs.template get<vertex_shape_t>(VERTEX_SHAPE);
        switch (shape)
        {
        case SHAPE_CIRCLE:
        case SHAPE_DOUBLE_CIRCLE:
            if (aspect != 1.)
            {
                cr.save();
                cr.scale(aspect, 1.0);
            }
            cr.arc(0, 0, size / 2., 0, 2 * M_PI);
            cr.close_path();
            if (aspect != 1.)
                cr.restore();
            if (shape == SHAPE_DOUBLE_CIRCLE && !outline)
            {
                cr.stroke();
                if (aspect != 1.)
                {
                    cr.save();
                    cr.scale(aspect, 1.0);
                }
                cr.arc(0, 0, min(size / 2 - 2 * pw,
                                 size * 0.8 / 2),
                       0, 2 * M_PI);
                if (aspect != 1.)
                    cr.restore();
            }
            break;
        case SHAPE_PIE:
            {
                if (!outline)
                {
                    vector<double> f = _attrs.template get<vector<double> >(VERTEX_PIE_FRACTIONS);
                    vector<color_t> fcolors = _attrs.template get<vector<color_t> >(VERTEX_PIE_COLORS);
                    draw_pie(size / 2 + pw / 2, f, fcolors, cr);
                }
                else
                {
                    cr.arc(0, 0, size / 2., 0, 2 * M_PI);
                    cr.close_path();
                }
            }
            break;
        case SHAPE_TRIANGLE:
        case SHAPE_SQUARE:
        case SHAPE_PENTAGON:
        case SHAPE_HEXAGON:
        case SHAPE_HEPTAGON:
        case SHAPE_OCTAGON:
        case SHAPE_DOUBLE_TRIANGLE:
        case SHAPE_DOUBLE_SQUARE:
        case SHAPE_DOUBLE_PENTAGON:
        case SHAPE_DOUBLE_HEXAGON:
        case SHAPE_DOUBLE_HEPTAGON:
        case SHAPE_DOUBLE_OCTAGON:
            nsides = shape - SHAPE_TRIANGLE + 3;
            if (nsides > 8)
                nsides -= 7;
            if (aspect != 1.)
            {
                cr.save();
                cr.scale(aspect, 1.0);
            }
            draw_polygon(nsides, size / 2, cr);
            if (aspect != 1.)
                cr.restore();
            if (shape >= SHAPE_DOUBLE_TRIANGLE && !outline)
            {
                cr.stroke();
                if (aspect != 1.)
                {
                    cr.save();
                    cr.scale(aspect, 1.0);
                }
                draw_polygon(nsides, min(size / 2 - 2 * pw,
                                         size * 0.8 / 2), cr);
                if (aspect != 1.)
                    cr.restore();
            }
            break;
        case SHAPE_NONE:
            break;
        default:
            throw ValueException("Invalid vertex shape: " +
                                 lexical_cast<string>(int(_attrs.template get<vertex_shape_t>(VERTEX_SHAPE))));
        }

        if (!outline && shape != SHAPE_PIE)
        {
            fillcolor = _attrs.template get<color_t>(VERTEX_FILL_COLOR);
            cr.set_source_rgba(get<0>(fillcolor), get<1>(fillcolor),
                               get<2>(fillcolor), get<3>(fillcolor));
            cr.fill_preserve();

            cr.set_source_rgba(get<0>(color), get<1>(color), get<2>(color),
                               get<3>(color));
            cr.stroke();
        }

        if (osrc != boost::python::object() && !outline)
        {
            double swidth, sheight;
            PycairoSurface* src = (PycairoSurface*) osrc.ptr();
            Cairo::RefPtr<Cairo::Surface> surface(new Cairo::Surface(src->surface));
            get_surface_size(surface, swidth, sheight);
            Cairo::RefPtr<Cairo::SurfacePattern> pat(Cairo::SurfacePattern::create(surface));
            //pat->set_extend(Cairo::EXTEND_REPEAT);

            double r = size / sqrt(2);
            double scale = r / max(swidth / aspect, sheight);

            Cairo::Matrix m = Cairo::identity_matrix();
            m.translate(swidth / 2, sheight / 2);
            m.scale(1. / scale, 1. / scale);
            pat->set_matrix(m);

            cr.set_source(pat);
            cr.rectangle(-r * aspect / 2, -r / 2, r * aspect, r);
            cr.fill();
        }

        if (!outline)
        {
            string text = _attrs.template get<string>(VERTEX_TEXT);
            if (text != "")
            {
                cr.save();

                double text_pos = 0;
                double text_rotation = 0;
                vector<double> text_offset;

                cr.select_font_face(_attrs.template get<string>(VERTEX_FONT_FAMILY),
                                    static_cast<Cairo::FontSlant>(_attrs.template get<int32_t>(VERTEX_FONT_SLANT)),
                                    static_cast<Cairo::FontWeight>(_attrs.template get<int32_t>(VERTEX_FONT_WEIGHT)));
                cr.set_font_size(get_user_dist(cr, _attrs.template get<double>(VERTEX_FONT_SIZE)));
                text_pos = _attrs.template get<double>(VERTEX_TEXT_POSITION);
                text_rotation = _attrs.template get<double>(VERTEX_TEXT_ROTATION);
                text_offset = _attrs.template get<vector<double> >(VERTEX_TEXT_OFFSET);
                text_offset.resize(2, 0.0);

                cr.rotate(text_rotation);

                Cairo::TextExtents extents;
                cr.get_text_extents(text, extents);
                Cairo::FontExtents fextents;
                cr.get_font_extents(fextents);

                if (text_pos < 0)
                {
                    cr.translate(-extents.width / 2 - extents.x_bearing + text_offset[0],
                                 extents.height / 2 + text_offset[1]);
                }
                else
                {
                    pos_t origin;
                    origin.first = _pos.first + size * cos(text_pos);
                    origin.second = _pos.second + size * sin(text_pos);

                    pos_t anchor = get_anchor(origin, cr, true);
                    double angle = atan2(_pos.second - anchor.second,