graph_properties.cc 13.5 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.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 2
// 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, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

19
20
21
22
23
#include <boost/lambda/bind.hpp>

#include "graph.hh"
#include "histogram.hh"
#include "graph_filtering.hh"
24
#include "graph_python_filtering.hh"
25
#include "graph_selectors.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
26
27
#include "graph_properties.hh"

28
29
30
31
#include <boost/mpl/for_each.hpp>
#include <iostream>
#include <iomanip>

32
33
34
35
36
using namespace std;
using namespace boost;
using namespace boost::lambda;
using namespace graph_tool;

37
typedef mpl::vector<bool, int, long, size_t, float, double, std::string> value_types;
38
const char* type_names[] = {"boolean", "int", "long", "long", "float", "double", "string"};
Tiago Peixoto's avatar
Tiago Peixoto committed
39

40

Tiago Peixoto's avatar
Tiago Peixoto committed
41
42
43
//==============================================================================
// find_property_map(dp,name,key_type)
//==============================================================================
44
45
dynamic_property_map& 
graph_tool::find_property_map(const dynamic_properties& dp, string name, const type_info& key_type)
Tiago Peixoto's avatar
Tiago Peixoto committed
46
47
{
    for(typeof(dp.begin()) iter = dp.begin(); iter != dp.end(); ++iter)
48
49
        if (iter->first == name && iter->second->key() == key_type)
            return *iter->second;
Tiago Peixoto's avatar
Tiago Peixoto committed
50

51
52
53
54
55
56
57
58
59
60
61
    throw property_not_found(name);
}

//==============================================================================
// RemoveVertexProperty(property)
//==============================================================================
void GraphInterface::RemoveVertexProperty(string property)
{
    dynamic_properties_copy dp;
    try
    {
62
63
64
65
        dynamic_property_map& prop_map = find_property_map(_properties, property, typeid(graph_traits<multigraph_t>::vertex_descriptor));
        for (typeof(_properties.begin()) iter = _properties.begin(); iter != _properties.end(); ++iter)
        {
            if (iter->second != &prop_map)
66
                dp.insert(iter->first, auto_ptr<dynamic_property_map>(iter->second));
67
        }
68
69
70
    }
    catch (property_not_found)
    {
71
        throw GraphException("property '" + property + "' not found");
72
73
74
75
76
77
78
79
80
81
82
83
    }
    _properties = dp;
}

//==============================================================================
// RemoveEdgeProperty(property)
//==============================================================================
void GraphInterface::RemoveEdgeProperty(string property)
{
    dynamic_properties_copy dp;
    try
    {
84
85
86
87
        dynamic_property_map& prop_map = find_property_map(_properties, property, typeid(graph_traits<multigraph_t>::edge_descriptor));
        for (typeof(_properties.begin()) iter = _properties.begin(); iter != _properties.end(); ++iter)
        {
            if (iter->second != &prop_map)
88
                dp.insert(iter->first, auto_ptr<dynamic_property_map>(iter->second));
89
        }
90
91
92
    }
    catch (property_not_found)
    {
93
        throw GraphException("property '" + property + "' not found");
94
95
96
97
    }
    _properties = dp;
}

Tiago Peixoto's avatar
Tiago Peixoto committed
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//==============================================================================
// RemoveGraphProperty(property)
//==============================================================================
void GraphInterface::RemoveGraphProperty(string property)
{
    dynamic_properties_copy dp;
    try
    {
        dynamic_property_map& prop_map = find_property_map(_properties, property, typeid(graph_property_tag));
        for (typeof(_properties.begin()) iter = _properties.begin(); iter != _properties.end(); ++iter)
        {
            if (iter->second != &prop_map)
                dp.insert(iter->first, auto_ptr<dynamic_property_map>(iter->second));
        }
    }
    catch (property_not_found)
    {
        throw GraphException("property '" + property + "' not found");
    }
    _properties = dp;
}


121
122
123
124
125
126
//==============================================================================
// edit_property
//==============================================================================
template <class Descriptor>
struct edit_property
{
Tiago Peixoto's avatar
Tiago Peixoto committed
127
128
    template <class Graph>
    void operator()(const Graph& g, const dynamic_properties& dp, dynamic_property_map* prop_map, python::object& op) const
129
    {
130
        typedef mpl::vector<in_degreeS,out_degreeS,total_degreeS> degrees;
131

132
        python::object operation = op[0], variables = op[1];
133

134
135
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
        typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
136

Tiago Peixoto's avatar
Tiago Peixoto committed
137
138
139
140
141
        typedef typename mpl::if_< is_same<Descriptor,vertex_descriptor>,
                                   vertex_descriptor, 
                                   typename mpl::if_<is_same<Descriptor,graph_property_tag>,
                                                     graph_property_tag, 
                                                     edge_descriptor>::type >::type descriptor_t;
142
        descriptor_t u;
143
144
        
        populate_python_funcs<descriptor_t>()(g, u, dp, variables);
145

Tiago Peixoto's avatar
Tiago Peixoto committed
146
        put_properties(g, u, *prop_map, operation);
147
148
    }
    
Tiago Peixoto's avatar
Tiago Peixoto committed
149
    template<class Graph>
150
    void put_properties(const Graph& g, typename graph_traits<Graph>::vertex_descriptor& v, 
Tiago Peixoto's avatar
Tiago Peixoto committed
151
                        dynamic_property_map& prop_map, python::object& operation) const
152
    {
153
154
155
156
        typename graph_traits<Graph>::vertex_iterator vi,v_end;
        for (tie(vi, v_end) = vertices(g); vi != v_end; ++vi)
        {
            v = *vi;
Tiago Peixoto's avatar
Tiago Peixoto committed
157
158
            python::object val = operation();
            prop_map.put(*vi, val);
159
        }
160
161
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
162
    template<class Graph>
163
    void put_properties(const Graph& g, typename graph_traits<Graph>::edge_descriptor& e, 
Tiago Peixoto's avatar
Tiago Peixoto committed
164
                        dynamic_property_map& prop_map, python::object& operation) const
165
    {
166
167
168
169
        typename graph_traits<Graph>::edge_iterator ei,e_end;
        for (tie(ei, e_end) = edges(g); ei != e_end; ++ei)
        {
            e = *ei;
170
            Descriptor& ec = e;
Tiago Peixoto's avatar
Tiago Peixoto committed
171
            python::object val = operation();
172
            prop_map.put(ec, val);
173
        }
174
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
175
176
177
178
179
180
181
182
183

    template<class Graph>
    void put_properties(const Graph& g, graph_property_tag, 
                        dynamic_property_map& prop_map, python::object& operation) const
    {
        python::object val = operation();
        prop_map.put(graph_property_tag(), val);
    }

184
185
186
};

//==============================================================================
Tiago Peixoto's avatar
Tiago Peixoto committed
187
// get_property_map()
188
189
190
//==============================================================================

template <class ValueTypes, class Descriptor, class IndexMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
191
class get_property_map
192
193
{
public:
194
    get_property_map(GraphInterface& gi, dynamic_properties& dp, IndexMap index_map, string property, string type, const char* types[], python::object op, dynamic_property_map*& pmap)
Tiago Peixoto's avatar
Tiago Peixoto committed
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
        : _gi(gi), _dp(dp), _index_map(index_map), _property(property), _type(type), _types(types), _op(op), _pmap(pmap) {}
    
    template <class ValueType>
    class python_dynamic_property_map: public dynamic_property_map
    {
    public:
        python_dynamic_property_map(dynamic_property_map& dmap): _dmap(dmap) {}

        virtual void put(const any& key, const any& val) 
        {
            const python::object& o = any_cast<python::object>(val);
            ValueType value = python::extract<ValueType>(o); 
            _dmap.put(key, value); 
        }

        virtual any get(const any& key) { return _dmap.get(key); }
        virtual string get_string(const any& key) { return _dmap.get_string(key); }
        virtual const std::type_info& key() const { return _dmap.key(); } 
        virtual const std::type_info& value() const { return _dmap.value(); }
    private:
        dynamic_property_map& _dmap;
    };
217
218
219
220
221
222
223
224

    template <class ValueType>
    void operator()(ValueType)
    {
        if (_type == _types[mpl::find<ValueTypes,ValueType>::type::pos::value])
        {
            try
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
225
226
227
228
229
                dynamic_property_map& pmap = find_property_map(_dp, _property, typeid(Descriptor));
                if (pmap.value() != typeid(ValueType))
                    throw GraphException("property \""+ _property + "\" already exists with a type other than " + _type + 
                                         ". Remove it first, or use the same type when editing.");
                _pmap = new python_dynamic_property_map<ValueType>(pmap);
230
231
232
233
234
235
            }
            catch (property_not_found)
            {
                typedef vector_property_map<ValueType, IndexMap> prop_map_t;
                prop_map_t prop_map(_index_map);
                _dp.property(_property, prop_map);
Tiago Peixoto's avatar
Tiago Peixoto committed
236
237
                _pmap = new python_dynamic_property_map<ValueType>(find_property_map(_dp, _property, typeid(typename IndexMap::key_type)));
            }
238
239
240
241
242
243
244
245
246
        }
    }

private:
    GraphInterface& _gi;
    dynamic_properties& _dp;
    IndexMap _index_map;
    string _property;
    string _type;
247
    const char** _types;
248
    python::object _op;
Tiago Peixoto's avatar
Tiago Peixoto committed
249
    dynamic_property_map*& _pmap;
250
251
};

252

253
254
255
256
//==============================================================================
// EditVertexProperty()
//==============================================================================

257
void GraphInterface::EditVertexProperty(string property, string type, python::object op)
258
{
259
260
261
262
263
264
265
    bool valid = false;
    for(int i = 0; i < mpl::size<value_types>::type::value; ++i)
        if (type == type_names[i])
            valid = true;
    if (!valid)
        throw GraphException("invalid type: " + type);

Tiago Peixoto's avatar
Tiago Peixoto committed
266
    dynamic_property_map* pmap;
267
    typedef graph_traits<multigraph_t>::vertex_descriptor vertex_descriptor;
Tiago Peixoto's avatar
Tiago Peixoto committed
268
269
270
271
    mpl::for_each<value_types>(get_property_map<value_types,vertex_descriptor,vertex_index_map_t>(*this, _properties, _vertex_index, property, type, type_names, op, pmap));
    check_filter(*this, lambda::bind<void>(edit_property<vertex_descriptor>(), lambda::_1, var(_properties), var(pmap), var(op)),
                 reverse_check(), directed_check());
    delete pmap;
272
273
}

274
275
276
277
278
//==============================================================================
// EditEdgeProperty()
//==============================================================================

void GraphInterface::EditEdgeProperty(string property, string type, python::object op)
279
{
280
281
282
283
284
285
286
    bool valid = false;
    for(int i = 0; i < mpl::size<value_types>::type::value; ++i)
        if (type == type_names[i])
            valid = true;
    if (!valid)
        throw GraphException("invalid type: " + type);

Tiago Peixoto's avatar
Tiago Peixoto committed
287
    dynamic_property_map* pmap;
288
    typedef graph_traits<multigraph_t>::edge_descriptor edge_descriptor;
Tiago Peixoto's avatar
Tiago Peixoto committed
289
290
291
292
    mpl::for_each<value_types>(get_property_map<value_types,edge_descriptor,edge_index_map_t>(*this, _properties, _edge_index, property, type, type_names, op, pmap));
    check_filter(*this, lambda::bind<void>(edit_property<edge_descriptor>(), lambda::_1, var(_properties), var(pmap), var(op)),
                 reverse_check(), directed_check());
    delete pmap;
293
294
}

Tiago Peixoto's avatar
Tiago Peixoto committed
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
//==============================================================================
// EditGraphProperty()
//==============================================================================

void GraphInterface::EditGraphProperty(string property, string type, python::object op)
{
    bool valid = false;
    for(int i = 0; i < mpl::size<value_types>::type::value; ++i)
        if (type == type_names[i])
            valid = true;
    if (!valid)
        throw GraphException("invalid type: " + type);

    dynamic_property_map* pmap;
    ConstantPropertyMap<size_t,graph_property_tag> graph_index(0);
    mpl::for_each<value_types>(get_property_map<value_types,graph_property_tag,ConstantPropertyMap<size_t,graph_property_tag> >(*this, _properties, graph_index, property, type, type_names, op, pmap));
    check_filter(*this, lambda::bind<void>(edit_property<graph_property_tag>(), lambda::_1, var(_properties), var(pmap), var(op)),
                 reverse_check(), directed_check());
    delete pmap;
}


317
318
319
320
321
322
323
324
//==============================================================================
// ListProperties()
//==============================================================================

template <class ValueTypes>
class print_name
{
public:
325
    print_name(const type_info& type, const char* types[]): _type(type), _types(types) {}
326
327
328

    template <class ValueType>
    void operator()(ValueType)
329
    {
330
331
        if (_type == typeid(ValueType))
            cout << _types[mpl::find<ValueTypes,ValueType>::type::pos::value];
332
    }
333
334
private:
    const type_info& _type;
335
    const char** _types;
336
337
338
339
340
};

void GraphInterface::ListProperties() const
{
    for (typeof(_properties.begin()) p = _properties.begin(); p != _properties.end(); ++p)
341
    {
342
343
344
345
346
347
348
349
350
351
352
        cout << setw(15) << left << p->first << " " << setw(8) << left;
        if (p->second->key() == typeid(graph_traits<multigraph_t>::vertex_descriptor))
            cout << "(vertex)";
        else 
            if (p->second->key() == typeid(graph_traits<multigraph_t>::edge_descriptor))
                cout << "(edge)";
            else
                cout << "(graph)";
        cout << "  type: ";
        mpl::for_each<value_types>(print_name<value_types>(p->second->value(), type_names));
        cout << endl;
353
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
354
}
355