graph_properties.cc 14.7 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
16
17
18
// 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"
Tiago Peixoto's avatar
   
Tiago Peixoto committed
24
#include "graph_python_interface.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
38
namespace graph_tool
{
39
40
41
std::ostream& operator<<(std::ostream &o, const pos_t &p ) { o << p.x << "," << p.y; return o;}
std::istream& operator>>(std::istream &o, pos_t &p ) { char c; o >> p.x >> c >> p.y; return o;}

42
// global property types
43
const char* type_names[] = {"boolean", "int", "long", "size_t", "float", "double", "string", "pos_t"};
Tiago Peixoto's avatar
Tiago Peixoto committed
44

45
// scalar types
46
const char* scalar_names[] = {"boolean", "int", "long", "size_t", "float", "double"};
47
}
48

Tiago Peixoto's avatar
Tiago Peixoto committed
49
50
51
//==============================================================================
// find_property_map(dp,name,key_type)
//==============================================================================
52
53
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
54
55
{
    for(typeof(dp.begin()) iter = dp.begin(); iter != dp.end(); ++iter)
56
57
        if (iter->first == name && iter->second->key() == key_type)
            return *iter->second;
Tiago Peixoto's avatar
Tiago Peixoto committed
58

59
60
61
62
63
64
65
66
67
68
69
    throw property_not_found(name);
}

//==============================================================================
// RemoveVertexProperty(property)
//==============================================================================
void GraphInterface::RemoveVertexProperty(string property)
{
    dynamic_properties_copy dp;
    try
    {
70
71
72
73
        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)
74
                dp.insert(iter->first, auto_ptr<dynamic_property_map>(iter->second));
75
        }
76
77
78
    }
    catch (property_not_found)
    {
79
        throw GraphException("property '" + property + "' not found");
80
81
82
83
84
85
86
87
88
89
90
91
    }
    _properties = dp;
}

//==============================================================================
// RemoveEdgeProperty(property)
//==============================================================================
void GraphInterface::RemoveEdgeProperty(string property)
{
    dynamic_properties_copy dp;
    try
    {
92
93
94
95
        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)
96
                dp.insert(iter->first, auto_ptr<dynamic_property_map>(iter->second));
97
        }
98
99
100
    }
    catch (property_not_found)
    {
101
        throw GraphException("property '" + property + "' not found");
102
103
104
105
    }
    _properties = dp;
}

Tiago Peixoto's avatar
Tiago Peixoto committed
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//==============================================================================
// 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;
}


129
130
131
132
133
134
//==============================================================================
// edit_property
//==============================================================================
template <class Descriptor>
struct edit_property
{
Tiago Peixoto's avatar
Tiago Peixoto committed
135
136
    template <class Graph>
    void operator()(const Graph& g, const dynamic_properties& dp, dynamic_property_map* prop_map, python::object& op) const
137
    {
138
        typedef mpl::vector<in_degreeS,out_degreeS,total_degreeS> degrees;
139

140
        python::object operation = op[0], variables = op[1];
141

142
143
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
        typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
144

Tiago Peixoto's avatar
Tiago Peixoto committed
145
146
147
148
149
        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;
150
        descriptor_t u;
151
152
        
        populate_python_funcs<descriptor_t>()(g, u, dp, variables);
153

Tiago Peixoto's avatar
Tiago Peixoto committed
154
        put_properties(g, u, *prop_map, operation);
155
156
    }
    
Tiago Peixoto's avatar
Tiago Peixoto committed
157
    template<class Graph>
158
    void put_properties(const Graph& g, typename graph_traits<Graph>::vertex_descriptor& v, 
Tiago Peixoto's avatar
Tiago Peixoto committed
159
                        dynamic_property_map& prop_map, python::object& operation) const
160
    {
161
162
163
164
        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
165
166
            python::object val = operation();
            prop_map.put(*vi, val);
167
        }
168
169
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
170
    template<class Graph>
171
    void put_properties(const Graph& g, typename graph_traits<Graph>::edge_descriptor& e, 
Tiago Peixoto's avatar
Tiago Peixoto committed
172
                        dynamic_property_map& prop_map, python::object& operation) const
173
    {
174
175
176
177
        typename graph_traits<Graph>::edge_iterator ei,e_end;
        for (tie(ei, e_end) = edges(g); ei != e_end; ++ei)
        {
            e = *ei;
178
            Descriptor& ec = e;
Tiago Peixoto's avatar
Tiago Peixoto committed
179
            python::object val = operation();
180
            prop_map.put(ec, val);
181
        }
182
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
183
184
185
186
187
188
189
190
191

    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);
    }

192
193
194
};

//==============================================================================
Tiago Peixoto's avatar
Tiago Peixoto committed
195
// get_property_map()
196
197
198
//==============================================================================

template <class ValueTypes, class Descriptor, class IndexMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
199
class get_property_map
200
201
{
public:
202
    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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
        : _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;
    };
225
226
227
228
229
230
231
232

    template <class ValueType>
    void operator()(ValueType)
    {
        if (_type == _types[mpl::find<ValueTypes,ValueType>::type::pos::value])
        {
            try
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
233
234
235
236
237
                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);
238
239
240
241
242
243
            }
            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
244
245
                _pmap = new python_dynamic_property_map<ValueType>(find_property_map(_dp, _property, typeid(typename IndexMap::key_type)));
            }
246
247
248
249
250
251
252
253
254
        }
    }

private:
    GraphInterface& _gi;
    dynamic_properties& _dp;
    IndexMap _index_map;
    string _property;
    string _type;
255
    const char** _types;
256
    python::object _op;
Tiago Peixoto's avatar
Tiago Peixoto committed
257
    dynamic_property_map*& _pmap;
258
259
};

260

261
262
263
264
//==============================================================================
// EditVertexProperty()
//==============================================================================

265
void GraphInterface::EditVertexProperty(string property, string type, python::object op)
266
{
267
268
269
270
271
272
273
    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
274
    dynamic_property_map* pmap;
275
    typedef graph_traits<multigraph_t>::vertex_descriptor vertex_descriptor;
Tiago Peixoto's avatar
Tiago Peixoto committed
276
277
278
279
    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;
280
281
}

282
283
284
285
286
//==============================================================================
// EditEdgeProperty()
//==============================================================================

void GraphInterface::EditEdgeProperty(string property, string type, python::object op)
287
{
288
289
290
291
292
293
294
    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
295
    dynamic_property_map* pmap;
296
    typedef graph_traits<multigraph_t>::edge_descriptor edge_descriptor;
Tiago Peixoto's avatar
Tiago Peixoto committed
297
298
299
300
    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;
301
302
}

Tiago Peixoto's avatar
Tiago Peixoto committed
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
//==============================================================================
// 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;
}


325
326
327
328
329
//==============================================================================
// ListProperties()
//==============================================================================

template <class ValueTypes>
330
class get_type_name
331
332
{
public:
333
334
    get_type_name(const type_info& type, const char* types[], string& name)
        : _type(type), _types(types), _name(name) {}
335
336
337

    template <class ValueType>
    void operator()(ValueType)
338
    {
339
        if (_type == typeid(ValueType))
340
            _name = _types[mpl::find<ValueTypes,ValueType>::type::pos::value];
341
    }
342
343
private:
    const type_info& _type;
344
    const char** _types;
345
    string& _name;
346
347
348
349
};

void GraphInterface::ListProperties() const
{
350
351
    list<tuple<string,string,string> > graph_properties, vertex_properties, edge_properties;
    
352
    for (typeof(_properties.begin()) p = _properties.begin(); p != _properties.end(); ++p)
353
    {
354
355
356
        tuple<string,string,string> prop;
        get<0>(prop) = p->first;
        mpl::for_each<value_types>(get_type_name<value_types>(p->second->value(), type_names, get<2>(prop)));
357
        if (p->second->key() == typeid(graph_traits<multigraph_t>::vertex_descriptor))
358
359
360
361
        {
            get<1>(prop) = "(vertex)";
            vertex_properties.push_back(prop);
        }
362
363
        else 
            if (p->second->key() == typeid(graph_traits<multigraph_t>::edge_descriptor))
364
365
366
367
            {
                get<1>(prop) = "(edge)";
                edge_properties.push_back(prop);
            }
368
            else
369
370
371
372
373
374
375
376
377
378
379
380
381
382
            {  
                get<1>(prop) = "(graph)";
                graph_properties.push_back(prop);
            }
    }

    list<tuple<string,string,string> > props;
    props.insert(props.end(), graph_properties.begin(), graph_properties.end());
    props.insert(props.end(), vertex_properties.begin(), vertex_properties.end());
    props.insert(props.end(), edge_properties.begin(), edge_properties.end());
    for (typeof(props.begin()) iter = props.begin(); iter != props.end(); ++iter)
    {
        cout << setw(15) << left << get<0>(*iter) << " " << setw(8) << left << get<1>(*iter)
             << "  type: " << get<2>(*iter) << endl;
383
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
384
}
385