graph_properties.hh 18.6 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  Tiago de Paula Peixoto <tiago@forked.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
21

#ifndef GRAPH_PROPERTIES_HH
#define GRAPH_PROPERTIES_HH

#include <string>
22
#include <vector>
23
#include <tr1/unordered_map>
24
#include <tr1/memory>
25
#include <boost/python/object.hpp>
26

27
#include <boost/property_map.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
28
#include <boost/dynamic_property_map.hpp>
29
#include <boost/vector_property_map.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
30
#include <boost/functional/hash.hpp>
31
32
#include <boost/mpl/vector.hpp>
#include <boost/mpl/for_each.hpp>
33
34
35
#include <boost/mpl/transform.hpp>
#include <boost/mpl/find.hpp>
#include <boost/lambda/bind.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
36

37
38
#include "graph.hh"

39
// this file provides general functions for manipulating graph properties
40
41

namespace graph_tool
Tiago Peixoto's avatar
Tiago Peixoto committed
42
{
43
44
using namespace std;
using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
45

46
47
48
49
50
// Metaprogramming
// ===============
//
// Metafunctions and data structures to deal with property maps

51
// global property types. only these types are allowed in property maps
52
53
54
55
56
57
58
59
// 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>
60
61
    value_types;

62
63
extern const char* type_names[]; // respective type names (defined in
                                 // graph_properties.cc)
64
65

// scalar types: types contained in value_types which are scalar
66
67
typedef mpl::vector<uint8_t, int32_t, int64_t, double, long double>
    scalar_types;
68
69

// integer_types: scalar types which are integer
70
typedef mpl::vector<uint8_t, int32_t, int64_t> integer_types;
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

// 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;
88

89
90
91
92
93
94
95
96
97
98

// metafunction to get the associated property map types to ValueTypes and
// IndexMap

struct property_map_type
{
    template <class ValueType, class IndexMap>
    struct apply
    {
        typedef vector_property_map<ValueType,IndexMap> type;
99
    };
100
101
102
103
104
105
106
107
108
109
110
};

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
    {
111
        template <class T1> struct apply
112
113
114
        { typedef typename Bind::template apply<T1>::type type; };
    };

115
    template <class ValueTypes, class IndexMap,
116
117
118
119
120
              class IncludeIndexMap = mpl::bool_<false> >
    struct apply
    {
        typedef typename mpl::transform<
            ValueTypes,
121
122
            bind_wrap1<mpl::bind2<property_map_type,
                                  mpl::_1,
123
124
125
                                  IndexMap> >
            >::type scalar_properties;

126
        // put index map itself
127
128
129
130
131
        typedef typename mpl::if_<
            IncludeIndexMap,
            typename mpl::push_back<scalar_properties,IndexMap>::type,
            scalar_properties
            >::type type;
132
    };
133
};
134

135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// Property map manipulation
// =========================
//
// Functions which deal with several aspects of property map manipulation

// the following exception gets thrown when no properties are found
#pragma GCC visibility push(default)
class PropertyNotFound: public GraphException
{
public:
    PropertyNotFound(const string& name, const type_info& key,
                     const string& extra_info = "");
    PropertyNotFound(const string& name, const type_info& key,
                     const type_info& value, const string& extra_info = "");
    PropertyNotFound(const string& name, const type_info& key,
                     const vector<string>& values,
                     const string& extra_info = "");
};
#pragma GCC visibility push(default)
154

155
156
// this function gets the "static" property map behind the dynamic property map,
// or throws bad_cast if it doesn't match the correct type
Tiago Peixoto's avatar
Tiago Peixoto committed
157
template <class PropertyMap>
158
PropertyMap& get_static_property_map(dynamic_property_map& map)
Tiago Peixoto's avatar
Tiago Peixoto committed
159
{
160
    return dynamic_cast
161
        <boost::detail::dynamic_property_map_adaptor<PropertyMap>&>(map).base();
Tiago Peixoto's avatar
Tiago Peixoto committed
162
163
}

164
165
// same as above, but returns a pointer and does not throw an exception, and
// returns 0 in case of failure
166
template <class PropertyMap>
167
PropertyMap* get_static_property_map(dynamic_property_map* map)
168
{
169
    boost::detail::dynamic_property_map_adaptor<PropertyMap>* adaptor =
170
        dynamic_cast
171
        <boost::detail::dynamic_property_map_adaptor<PropertyMap>*>(map);
172
    if (adaptor)
173
        return &adaptor->base();
174
    else
175
        return 0;
176
177
}

178
// this function gets the dynamic property map inside dp which matches the given
179
// name and key type. It throws PropertyNotFound in case of failure
180
dynamic_property_map&
181
find_property_map(const dynamic_properties& dp, const string& name,
182
                  const type_info& key_type);
183

184
185
186
// convenience function which finds and returns the appropriate static property
// from the dynamic properties
template <class PropertyMap>
187
PropertyMap& find_static_property_map(const dynamic_properties& dp,
188
                                      const string& name)
189
{
190
    typedef typename property_traits<PropertyMap>::key_type key_type;
191
    dynamic_property_map& dmap = find_property_map(dp, name,
192
                                                   typeid(key_type));
193
194
195
    return get_static_property_map<PropertyMap>(dmap);
}

196
197
198
199
200
// the following function returns the actual property map wrapped as a
// boost::any object
struct get_static_prop; // forward decl.
template <class IndexMap>
boost::any prop(const string& name, IndexMap,
201
                const dynamic_properties& dp, bool dynamic = false)
202
203
204
205
206
207
{
    using namespace lambda;
    typedef typename property_traits<IndexMap>::key_type key_t;
    dynamic_property_map& dmap =
        find_property_map(dp, name, typeid(key_t));
    boost::any prop;
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
    if (dynamic)
    {
        prop = &dmap;
    }
    else
    {
        typedef typename property_map_types::apply<value_types,IndexMap>::type
            properties_t;
        bool found = false;
        mpl::for_each<properties_t>(lambda::bind<void>(get_static_prop(),
                                                       lambda::_1,
                                                       &dmap, var(prop),
                                                       var(found)));
        if (!found)
            throw PropertyNotFound(name, typeid(key_t),
                                   "This is a graph-tool bug. :-( "
                                   "Please follow but report instructions at "
                                   PACKAGE_BUGREPORT);
    }
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
    return prop;
}

// used in function prop() above
struct get_static_prop
{
    template <class PropertyMap>
    void operator()(PropertyMap, dynamic_property_map* dmap,
                    boost::any& smap, bool& found) const
    {
        PropertyMap* pmap = get_static_property_map<PropertyMap>(dmap);
        if (pmap != 0)
        {
            smap = boost::any(*pmap);
            found = true;
        }
    }
};

246
247
248
249
250
251
boost::any vertex_prop(const string& name, const GraphInterface& gi,
                       bool dynamic = false);
boost::any edge_prop(const string& name, const GraphInterface& gi,
                     bool dynamic = false);
boost::any graph_prop(const string& name, const GraphInterface& gi,
                      bool dynamic = false);
252

253
254
255
256
257
258
259
260
261
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
319
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
// 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())
        {
            using namespace lambda;
            mpl::for_each<TypeSequence>
                (lambda::bind<void>(get_all_names(), lambda::_1,
                                    var(_type_names), var(_all_names)));
        }
    }

    const string& operator()(const type_info& type) const
    {
        using namespace lambda;
        string* name;
        mpl::for_each<TypeSequence>
            (lambda::bind<void>(find_name(), lambda::_1, var(type),
                                var(_all_names), var(name)));
        return *name;
    }

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

private:
    struct find_name
    {
        template <class Type>
        void operator()(Type, const type_info& type,
                        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;

348
349
// this class contains a copy of a dynamic_properties, which does not delete its
// members when it deconstructs
350
struct dynamic_properties_copy: public dynamic_properties
Tiago Peixoto's avatar
Tiago Peixoto committed
351
352
{
    dynamic_properties_copy() {}
353
354
    dynamic_properties_copy(dynamic_properties& dp)
        : dynamic_properties(dp) {}
355
    dynamic_properties_copy
356
357
358
        (const function<auto_ptr<dynamic_property_map>
         (const string&, const boost::any&, const boost::any&)>& fn)
            : dynamic_properties(fn) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
359
    ~dynamic_properties_copy()
360
    {
361
362
        for (typeof(this->begin()) iter = this->begin(); iter != this->end();
             ++iter)
363
            iter->second = 0; // will be deleted when original dp deconstructs
Tiago Peixoto's avatar
Tiago Peixoto committed
364
365
366
    }
};

367
// the following class wraps a dynamic_property_map, so it can be used as a
368
// regular property map. The values are converted to the desired Value type,
369
370
// 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
373
374
375
376
377
template <class Value, class Key>
class DynamicPropertyMapWrap
{
public:
    typedef Value value_type;
    typedef Value reference;
    typedef Key key_type;
378
    typedef read_write_property_map_tag category;
379

380
381
382
383
384
385
386
387
388
389
390
391
    DynamicPropertyMapWrap(dynamic_property_map& dmap)
        :_dmap(&dmap)
    {
        ValueConverter* converter = 0;
        mpl::for_each<scalar_types>
            (lambda::bind<void>(choose_converter(), lambda::_1,
                                lambda::var(_dmap), lambda::var(converter)));
        if (converter == 0)
            throw bad_lexical_cast();
        else
            _converter = tr1::shared_ptr<ValueConverter>(converter);
    }
392
393
    DynamicPropertyMapWrap() {}

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

    void put(const Key& k, const Value& val)
    {
401
        _dmap->put(k, val);
402
403
404
    }

private:
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
    class ValueConverter
    {
    public:
        virtual Value operator()(dynamic_property_map& map, const Key& k) = 0;
    };

    template <class OrigValue>
    class ValueConverterImp: public ValueConverter
    {
    public:
        virtual Value operator()(dynamic_property_map& dmap, const Key& k)
        {
            OrigValue val = any_cast<OrigValue>(dmap.get(k));
            return lexical_cast<Value>(val);
        }
    };

    struct choose_converter
    {
        template <class Type>
        void operator()(Type, dynamic_property_map* dmap,
                        ValueConverter*& converter) const
        {
            if (typeid(Type) == dmap->value())
                converter = new ValueConverterImp<Type>();
        }
    };

433
    dynamic_property_map* _dmap;
434
    tr1::shared_ptr<ValueConverter> _converter;
435
436
};

437
template <class Value, class Key, class ConvKey>
438
Value get(const graph_tool::DynamicPropertyMapWrap<Value,Key>& pmap,
439
          ConvKey k)
440
{
441
442
    Key key = k;
    return pmap.get(key);
443
444
445
}

template <class Value, class Key>
446
447
void put(graph_tool::DynamicPropertyMapWrap<Value,Key>& pmap,
         Key k, const Value& val)
448
{
449
    pmap.put(k, val);
450
451
}

452
453
// the following is hash functor which, will hash a vertex or edge descriptor
// based on its index
454
template <class IndexMap>
455
class DescriptorHash
456
    : public unary_function<typename IndexMap::key_type, size_t>
457
458
459
460
{
public:
    DescriptorHash() {}
    DescriptorHash(IndexMap index_map): _index_map(index_map) {}
461
    size_t operator()(typename IndexMap::key_type const& d) const
462
    {
463
        return hash_value(_index_map[d]);
464
    }
465
466
467
468
private:
    IndexMap _index_map;
};

469
470
// the following is a property map based on a hashed container, which uses the
// above hash function for vertex or edge descriptors
471
472
template <class IndexMap, class Value>
class HashedDescriptorMap
473
    : public put_get_helper<Value&, HashedDescriptorMap<IndexMap,Value> >
474
475
476
{
public:
    typedef DescriptorHash<IndexMap> hashfc_t;
477
    typedef tr1::unordered_map<typename IndexMap::key_type,Value,hashfc_t>
478
        map_t;
479
    typedef associative_property_map<map_t> prop_map_t;
480

481
482
483
484
    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;
485

486
487
    HashedDescriptorMap(IndexMap index_map)
        : _base_map(new map_t(0, hashfc_t(index_map))), _prop_map(*_base_map) {}
488
    HashedDescriptorMap(){}
489

490
491
492
493
    reference operator[](const key_type& k) { return _prop_map[k]; }
    const reference operator[](const key_type& k) const { return _prop_map[k]; }

private:
494
    shared_ptr<map_t> _base_map;
495
496
497
498
499
500
501
502
    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
503
504
    : public put_get_helper<typename Container::value_type::second_type&,
                            InitializedPropertyMap<Container> >
505
506
507
508
509
{
public:
    typedef typename Container::value_type::second_type value_type;
    typedef value_type& reference;
    typedef typename Container::key_type key_type;
510
    typedef read_write_property_map_tag category;
511
512

    InitializedPropertyMap(Container& base_map, value_type def)
513
        : _base_map(&base_map), _default(def) {}
514
515
516
517
    InitializedPropertyMap(){}

    reference operator[](const key_type& k)
    {
518
        return get(k);
519
520
521
522
    }

    const reference operator[](const key_type& k) const
    {
523
        return get(k);
524
525
526
527
    }

    const reference get(const key_type& k) const
    {
528
529
530
531
532
        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;
533
534
535
536
537
538
539
    }

private:
    Container* _base_map;
    value_type _default;
};

540
// the following is a property map which always returns a constant value
541
542
template <class Value, class Key>
class ConstantPropertyMap
543
    : public put_get_helper<Value, ConstantPropertyMap<Value,Key> >
544
545
546
547
548
{
public:
    typedef Value value_type;
    typedef value_type& reference;
    typedef Key key_type;
549
    typedef readable_property_map_tag category;
550
551
552
553

    ConstantPropertyMap(value_type c): _c(c) {}
    ConstantPropertyMap(){}

554
    const value_type& operator[](const key_type& k) const { return _c; }
555
556
557
558
559

private:
    value_type _c;
};

560
561
562
563
564
565
566
567
568
569
570
// this wraps an existing property map, but always converts its values to a
// given type
template <class PropertyMap, class Type>
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;
571

572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
    ConvertedPropertyMap(PropertyMap base_map)
        : _base_map(base_map) {}
    ConvertedPropertyMap(){}

    value_type get(const key_type& k) const
    {
        return boost::get(_base_map, k);
    }

    void put(const key_type& k, const Type& v)
    {
        put(_base_map, k, orig_type(v));
    }
private:
    PropertyMap _base_map;
};
588

589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
template <class PropertyMap, class Type>
Type get(const graph_tool::ConvertedPropertyMap<PropertyMap,Type>& pmap,
         const typename property_traits<PropertyMap>::key_type& k)
{
    return pmap.get(k);
}

template <class PropertyMap, class Type>
void put(graph_tool::ConvertedPropertyMap<PropertyMap,Type> pmap,
         const typename property_traits<PropertyMap>::key_type& k,
         const typename property_traits<PropertyMap>::value_type& val)
{
    pmap.put(k, val);
}

} // graph_tool namespace
605

Tiago Peixoto's avatar
Tiago Peixoto committed
606
#endif