graph_properties.hh 18.9 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1 2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2007-2012 Tiago de Paula Peixoto <tiago@skewed.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
4 5 6
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
Tiago Peixoto's avatar
Tiago Peixoto committed
7
// as published by the Free Software Foundation; either version 3
Tiago Peixoto's avatar
Tiago Peixoto committed
8 9 10 11 12 13 14 15
// 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
16
// along with this program. If not, see <http://www.gnu.org/licenses/>.
Tiago Peixoto's avatar
Tiago Peixoto committed
17 18 19 20

#ifndef GRAPH_PROPERTIES_HH
#define GRAPH_PROPERTIES_HH

21
#include <typeinfo>
Tiago Peixoto's avatar
Tiago Peixoto committed
22
#include <string>
23
#include <vector>
24 25 26 27 28 29 30 31 32 33 34 35
#if (GCC_VERSION >= 40400)
#   include <tr1/unordered_set>
#   include <tr1/unordered_map>
#   include <tr1/random>
#   include <tr1/memory>
#else
#   include <boost/tr1/unordered_set.hpp>
#   include <boost/tr1/unordered_map.hpp>
#   include <boost/tr1/random.hpp>
#   include <boost/tr1/memory.hpp>
#endif
#include <boost/functional/hash.hpp>
36
#include <boost/python/object.hpp>
37
#include <boost/python/extract.hpp>
38

39 40 41 42 43 44 45 46
#include <boost/version.hpp>
#if (BOOST_VERSION >= 104000)
#   include <boost/property_map/property_map.hpp>
#   include <boost/property_map/dynamic_property_map.hpp>
#else
#   include <boost/property_map.hpp>
#   include <boost/dynamic_property_map.hpp>
#endif
47
#include "fast_vector_property_map.hh"
48 49
#include <boost/mpl/vector.hpp>
#include <boost/mpl/for_each.hpp>
50 51
#include <boost/mpl/transform.hpp>
#include <boost/mpl/find.hpp>
52
#include <boost/bind.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
53

54
#include "graph.hh"
55
#include "graph_exceptions.hh"
56

57
// this file provides general functions for manipulating graph properties
58 59

namespace graph_tool
Tiago Peixoto's avatar
Tiago Peixoto committed
60
{
61 62
using namespace std;
using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
63

64 65 66 67 68
// Metaprogramming
// ===============
//
// Metafunctions and data structures to deal with property maps

69 70
// Global Property Types
// ---------------------
71
// global property types. only these types are allowed in property maps
72 73 74 75 76 77 78 79
// Note: we must avoid a vector<bool> (and bools in general) since it is quite
//       broken, and use a vector<uint8_t> instead!
//       see: http://www.gotw.ca/publications/N1211.pdf

typedef mpl::vector<uint8_t, int32_t, int64_t, double, long double, string,
                    vector<uint8_t>, vector<int32_t>, vector<int64_t>,
                    vector<double>, vector<long double>, vector<string>,
                    python::object>
80 81
    value_types;

82 83
extern const char* type_names[]; // respective type names (defined in
                                 // graph_properties.cc)
84 85

// scalar types: types contained in value_types which are scalar
86 87
typedef mpl::vector<uint8_t, int32_t, int64_t, double, long double>
    scalar_types;
88 89

// integer_types: scalar types which are integer
90
typedef mpl::vector<uint8_t, int32_t, int64_t> integer_types;
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107

// floating_types: scalar types which are floating point
typedef mpl::vector<double, long double> floating_types;

struct make_vector
{
    template <class ValueType> struct apply { typedef vector<ValueType> type; };
};

// scalar_vector_types: vector types with floating point values
typedef mpl::transform<scalar_types,make_vector>::type scalar_vector_types;

// integer_vector_types: vector types with floating point values
typedef mpl::transform<integer_types,make_vector>::type integer_vector_types;

// floating_vector_types: vector types with floating point values
typedef mpl::transform<floating_types,make_vector>::type floating_vector_types;
108

109 110 111
//
// Property Map Types
// ------------------
112

113 114
// metafunction to generate the correct property map type given a value type and
// an index map
115 116 117 118 119
struct property_map_type
{
    template <class ValueType, class IndexMap>
    struct apply
    {
120
        typedef checked_vector_property_map<ValueType,IndexMap> type;
121
    };
122 123
};

124 125
// metafunction to get the sequence of property map types of ValueTypes and
// IndexMap
126 127 128 129 130 131 132 133 134
struct property_map_types
{
   // this wraps an unary metafunction class Bind into a unary metafunction,
   // i.e., it is an identity operation. I'm not sure why it's necessary, but
   // using pure unary bind expressions below didn't work for me, and this fixed
   // it.
    template <class Bind>
    struct bind_wrap1
    {
135
        template <class T1> struct apply
136 137 138
        { typedef typename Bind::template apply<T1>::type type; };
    };

139
    template <class ValueTypes, class IndexMap,
140
              class IncludeIndexMap = mpl::bool_<true> >
141 142 143 144
    struct apply
    {
        typedef typename mpl::transform<
            ValueTypes,
145 146
            bind_wrap1<mpl::bind2<property_map_type,
                                  mpl::_1,
147 148 149
                                  IndexMap> >
            >::type scalar_properties;

150
        // put index map itself
151 152 153 154 155
        typedef typename mpl::if_<
            IncludeIndexMap,
            typename mpl::push_back<scalar_properties,IndexMap>::type,
            scalar_properties
            >::type type;
156
    };
157
};
158

159 160 161 162 163
// Property map manipulation
// =========================
//
// Functions which deal with several aspects of property map manipulation

164

165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
// this functor tests whether or not a given boost::any object holds a type
// contained in a given type Sequence
template <class Sequence>
struct belongs
{
    struct get_type
    {
        get_type(const boost::any& val, bool& found)
            : _val(val), _found(found) {}

        template <class Type>
        void operator()(Type) const
        {
            const Type* ptr = any_cast<Type>(&_val);
            if (ptr != 0)
                _found = true;
        }

        const boost::any& _val;
        bool& _found;
    };

    bool operator()(const boost::any& prop)
    {
        bool found = false;
        mpl::for_each<Sequence>(get_type(prop, found));
        return found;
    }
};

// this will return the name of a given type
template <class TypeSequence = value_types,
          class NamedSequence = value_types>
class get_type_name
{
public:
    get_type_name(const char* names[] = type_names)
        : _type_names(type_names)
    {
        if (_all_names.empty())
        {
            mpl::for_each<TypeSequence>
207 208
                (bind<void>(get_all_names(), _1,
                            ref(_type_names), ref(_all_names)));
209 210 211
        }
    }

212
    const string& operator()(const std::type_info& type) const
213 214 215
    {
        string* name;
        mpl::for_each<TypeSequence>
216 217
            (bind<void>(find_name(), _1, ref(type),
                        ref(_all_names), ref(name)));
218 219 220 221 222 223 224 225 226 227 228 229
        return *name;
    }

    const vector<string>& all_names() const
    {
        return _all_names;
    }

private:
    struct find_name
    {
        template <class Type>
230
        void operator()(Type, const std::type_info& type,
231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257
                        vector<string>& all_names,
                        string*& name) const
        {
            size_t index = mpl::find<TypeSequence,Type>::type::pos::value;
            if (type == typeid(Type))
                name = &all_names[index];
        }
    };

    struct get_all_names
    {
        template <class Type>
        void operator()(Type, const char** type_names,
                        vector<string>& names) const
        {
            size_t index = mpl::find<NamedSequence,Type>::type::pos::value;
            names.push_back(type_names[index]);
        }
    };

    const char** _type_names;
    static vector<string> _all_names;
};

template <class TypeSequence, class NamedSequence>
vector<string> get_type_name<TypeSequence,NamedSequence>::_all_names;

258 259 260 261
//
// Extra Property Map Types
// ========================

262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318

// handle type convertions

// generic types
template <class Type1, class Type2>
struct convert
{
    Type1 operator()(const Type2& v) const
    {
        return do_convert(v, is_convertible<Type2,Type1>());
    }

    Type1 do_convert(const Type2& v, mpl::bool_<true>) const
    {
        return Type1(v);
    }

    Type1 do_convert(const Type2& v, mpl::bool_<false>) const
    {
        return specific_convert<Type1,Type2>()(v);
    }

    template <class T1, class T2>
    struct specific_convert
    {
        T1 operator()(const T2& v) const
        {
            throw bad_lexical_cast(); // default action
        }
    };

    // specific specializations

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

    // string
    template <class T1>
    struct specific_convert<T1,string>
    {
        T1 operator()(const string& v) const
        {
            //uint8_t is not char, it is bool!
            if (is_same<T1, uint8_t>::value)
                return convert<T1,int>()(lexical_cast<int>(v));
            else
319
                return lexical_cast<T1>(v);
320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365
        }
    };

    template <class T2>
    struct specific_convert<string,T2>
    {
        string operator()(const T2& v) const
        {
            //uint8_t is not char, it is bool!
            if (is_same<T2, uint8_t>::value)
                return lexical_cast<string>(convert<int,T2>()(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;
        }
    };

};

// python::object to string, to solve ambiguity
template<> template<>
struct convert<string,python::object>::specific_convert<string,python::object>
{
    string operator()(const python::object& v) const
    {
        python::extract<string> x(v);
        if (x.check())
                return x();
        else
            throw bad_lexical_cast();
    }
};

366 367 368 369 370
// the following class wraps a generic property map, so it can be used as a
// property with a given Key and Value type. The keys and values are converted
// to the desired Key and Value type, which may cause a performance impact,
// since virtual functions are used. Should be used only when property map
// access time is not crucial
371 372
template <class Value, class Key,
          template <class T1, class T2> class Converter = convert>
373 374 375 376 377 378
class DynamicPropertyMapWrap
{
public:
    typedef Value value_type;
    typedef Value reference;
    typedef Key key_type;
379
    typedef read_write_property_map_tag category;
380

381 382
    template <class PropertyTypes>
    DynamicPropertyMapWrap(boost::any pmap, PropertyTypes)
383 384
    {
        ValueConverter* converter = 0;
385
        mpl::for_each<PropertyTypes>
386
            (bind<void>(choose_converter(), _1, ref(pmap), ref(converter)));
387 388 389 390 391
        if (converter == 0)
            throw bad_lexical_cast();
        else
            _converter = tr1::shared_ptr<ValueConverter>(converter);
    }
392

393 394
    DynamicPropertyMapWrap() {}

395 396
    Value get(const Key& k) const
    {
397
        return (*_converter).get(k);
398 399 400 401
    }

    void put(const Key& k, const Value& val)
    {
402
        (*_converter).put(k, val);
403 404 405
    }

private:
406 407 408
    class ValueConverter
    {
    public:
409 410
        virtual Value get(const Key& k) = 0;
        virtual void put(const Key& k, const Value& val) = 0;
411 412
    };

413
    template <class PropertyMap>
414 415 416
    class ValueConverterImp: public ValueConverter
    {
    public:
417
        ValueConverterImp(PropertyMap pmap): _pmap(pmap) {}
418 419
        typedef typename property_traits<PropertyMap>::value_type val_t;
        typedef typename property_traits<PropertyMap>::key_type key_t;
420 421 422

        virtual Value get(const Key& k)
        {
423 424 425
            return get_dispatch(_pmap, k,
                                is_convertible<typename property_traits<PropertyMap>::category,
                                readable_property_map_tag>());
426 427 428
        }

        virtual void put(const Key& k, const Value& val)
429
        {
430 431 432 433 434 435 436 437 438 439 440
            return  put_dispatch(_pmap, k, _c_put(val),
                                 is_convertible<typename property_traits<PropertyMap>::category,
                                                writable_property_map_tag>());
        }

        template <class PMap>
        Value get_dispatch(PMap pmap, const typename property_traits<PMap>::key_type& k,
                           mpl::bool_<true>)
        {
            return _c_get(boost::get(pmap, k));
        }
441

442 443 444 445 446
        template <class PMap>
        Value get_dispatch(PMap pmap, const typename property_traits<PMap>::key_type& k,
                           mpl::bool_<false>)
        {
            throw graph_tool::ValueException("Property map is not readable.");
447
        }
448

449 450 451 452 453 454 455 456 457 458 459 460 461 462 463
        template <class PMap>
        void put_dispatch(PMap pmap, const typename property_traits<PMap>::key_type& k,
                          typename property_traits<PMap>::value_type val,
                          mpl::bool_<true>)
        {
            boost::put(pmap, k, val);
        }

        template <class PMap>
        void put_dispatch(PMap pmap, const typename property_traits<PMap>::key_type& k,
                          typename property_traits<PMap>::value_type val,
                          mpl::bool_<false>)
        {
            throw ValueException("Property map is not writable.");
        }
464

465 466
    private:
        PropertyMap _pmap;
467 468
        Converter<Value, val_t> _c_get;
        Converter<val_t, Value> _c_put;
469 470 471 472
    };

    struct choose_converter
    {
473 474
        template <class PropertyMap>
        void operator()(PropertyMap, boost::any& dmap,
475 476
                        ValueConverter*& converter) const
        {
477 478 479
            if (typeid(PropertyMap) == dmap.type())
                converter = new ValueConverterImp<PropertyMap>
                    (any_cast<PropertyMap>(dmap));
480 481 482 483
        }
    };

    tr1::shared_ptr<ValueConverter> _converter;
484 485
};

486
template <class Value, class Key, class ConvKey>
487
Value get(const graph_tool::DynamicPropertyMapWrap<Value,Key>& pmap,
488
          ConvKey k)
489
{
490 491
    Key key = k;
    return pmap.get(key);
492 493 494
}

template <class Value, class Key>
495 496
void put(graph_tool::DynamicPropertyMapWrap<Value,Key>& pmap,
         Key k, const Value& val)
497
{
498
    pmap.put(k, val);
499 500
}

501 502
// the following is hash functor which, will hash a vertex or edge descriptor
// based on its index
503
template <class IndexMap>
504
class DescriptorHash
505
    : public unary_function<typename IndexMap::key_type, size_t>
506 507 508 509
{
public:
    DescriptorHash() {}
    DescriptorHash(IndexMap index_map): _index_map(index_map) {}
510
    size_t operator()(typename IndexMap::key_type const& d) const
511
    {
512
        return hash_value(_index_map[d]);
513
    }
514 515 516 517
private:
    IndexMap _index_map;
};

518 519
// the following is a property map based on a hashed container, which uses the
// above hash function for vertex or edge descriptors
520 521
template <class IndexMap, class Value>
class HashedDescriptorMap
522
    : public put_get_helper<Value&, HashedDescriptorMap<IndexMap,Value> >
523 524 525
{
public:
    typedef DescriptorHash<IndexMap> hashfc_t;
526
    typedef tr1::unordered_map<typename IndexMap::key_type,Value,hashfc_t>
527
        map_t;
528
    typedef associative_property_map<map_t> prop_map_t;
529

530 531 532 533
    typedef typename property_traits<prop_map_t>::value_type value_type;
    typedef typename property_traits<prop_map_t>::reference reference;
    typedef typename property_traits<prop_map_t>::key_type key_type;
    typedef typename property_traits<prop_map_t>::category category;
534

535 536
    HashedDescriptorMap(IndexMap index_map)
        : _base_map(new map_t(0, hashfc_t(index_map))), _prop_map(*_base_map) {}
537
    HashedDescriptorMap(){}
538

539 540 541 542
    reference operator[](const key_type& k) { return _prop_map[k]; }
    const reference operator[](const key_type& k) const { return _prop_map[k]; }

private:
543
    shared_ptr<map_t> _base_map;
544 545 546 547 548 549 550 551
    prop_map_t _prop_map;
};


// this wraps a container as a property map which is automatically initialized
// with a given default value
template <class Container>
class InitializedPropertyMap
552 553
    : public put_get_helper<typename Container::value_type::second_type&,
                            InitializedPropertyMap<Container> >
554 555 556 557 558
{
public:
    typedef typename Container::value_type::second_type value_type;
    typedef value_type& reference;
    typedef typename Container::key_type key_type;
559
    typedef read_write_property_map_tag category;
560 561

    InitializedPropertyMap(Container& base_map, value_type def)
562
        : _base_map(&base_map), _default(def) {}
563 564 565 566
    InitializedPropertyMap(){}

    reference operator[](const key_type& k)
    {
567
        return get(k);
568 569 570 571
    }

    const reference operator[](const key_type& k) const
    {
572
        return get(k);
573 574 575 576
    }

    const reference get(const key_type& k) const
    {
577 578 579 580 581
        typename Container::iterator val;
        val = _base_map->find(k);
        if (val == _base_map->end())
            val = _base_map->insert(make_pair(k, _default)).first;
        return val->second;
582 583 584 585 586 587 588
    }

private:
    Container* _base_map;
    value_type _default;
};

589
// the following is a property map which always returns a constant value
590 591
template <class Value, class Key>
class ConstantPropertyMap
592
    : public put_get_helper<Value, ConstantPropertyMap<Value,Key> >
593 594 595 596 597
{
public:
    typedef Value value_type;
    typedef value_type& reference;
    typedef Key key_type;
598
    typedef readable_property_map_tag category;
599

600
    ConstantPropertyMap(const value_type& c): _c(c) {}
601 602
    ConstantPropertyMap(){}

603
    const value_type& operator[](const key_type& k) const { return _c; }
604 605 606 607 608

private:
    value_type _c;
};

609

610 611
// this wraps an existing property map, but always converts its values to a
// given type
612 613
template <class PropertyMap, class Type,
          template <class T1, class T2> class Converter = convert>
614 615 616 617 618 619 620 621
class ConvertedPropertyMap
{
public:
    typedef Type value_type;
    typedef typename property_traits<PropertyMap>::value_type orig_type;
    typedef value_type reference;
    typedef typename property_traits<PropertyMap>::key_type key_type;
    typedef read_write_property_map_tag category;
622

623 624 625 626
    ConvertedPropertyMap(PropertyMap base_map)
        : _base_map(base_map) {}
    ConvertedPropertyMap(){}

627
    value_type do_get(const key_type& k) const
628
    {
629
        return _convert_to(get(_base_map, k));
630 631
    }

632
    void do_put(const key_type& k, const value_type& v)
633
    {
634
        put(_base_map, k, _convert_from(v));
635 636 637
    }
private:
    PropertyMap _base_map;
638 639
    Converter<value_type, orig_type> _convert_to;
    Converter<orig_type, value_type> _convert_from;
640
};
641

642
template <class PropertyMap, class Type>
643 644
Type get(ConvertedPropertyMap<PropertyMap,Type> pmap,
         typename ConvertedPropertyMap<PropertyMap,Type>::key_type k)
645
{
646
    return pmap.do_get(k);
647 648 649
}

template <class PropertyMap, class Type>
650 651 652
void put(ConvertedPropertyMap<PropertyMap,Type> pmap,
         typename property_traits<PropertyMap>::key_type k,
         const typename ConvertedPropertyMap<PropertyMap,Type>::value_type& val)
653
{
654
    pmap.do_put(k, val);
655 656 657
}

} // graph_tool namespace
658

Tiago Peixoto's avatar
Tiago Peixoto committed
659
#endif