graph.cc 25.1 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
19
20
21
22
23
24
25
26
27
// 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.

#include <algorithm>
#include <tr1/unordered_set>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/random.hpp>
28
#include <boost/python/make_function.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
29
30
31
32
33
34
35
36
37
38

#include <unistd.h>    /* standard unix functions, like getpid()         */
#include <sys/types.h> /* various type definitions, like pid_t           */
#include <signal.h>    /* signal name macros, and the signal() prototype */

#include "graph.hh"
#include "histogram.hh"
#include "graph_filtering.hh"
#include "graph_selectors.hh"
#include "graph_properties.hh"
39
#include "shared_map.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
40
41
42
43
44
45
46
47
48
49
50

using namespace std;
using namespace boost;
using namespace boost::lambda;
using namespace graph_tool;


pair<GraphInterface::degree_t,string> graph_tool::get_degree_type(GraphInterface::deg_t degree)
{
    GraphInterface::degree_t deg;
    string name;
51
    try
Tiago Peixoto's avatar
Tiago Peixoto committed
52
    {
53
        deg = boost::get<GraphInterface::degree_t>(degree);
Tiago Peixoto's avatar
Tiago Peixoto committed
54
55
56
    }
    catch (bad_get)
    {
57
58
        name = boost::get<std::string>(degree);
        deg = GraphInterface::SCALAR;
Tiago Peixoto's avatar
Tiago Peixoto committed
59
60
61
62
63
64
65
66
67
    }
    return make_pair(deg,name);
}


//==============================================================================
// GraphInterface()
//==============================================================================
GraphInterface::GraphInterface()
68
:_mg(),
Tiago Peixoto's avatar
Tiago Peixoto committed
69
70
71
72
 _reversed(false),
 _directed(true),
 _vertex_index(get(vertex_index,_mg)),
 _edge_index(get(edge_index_t(),_mg)),
Tiago Peixoto's avatar
   
Tiago Peixoto committed
73
 _vertex_filter_map(_vertex_index),
74
75
 _vertex_range(make_pair(0.0, numeric_limits<double>::max())),
 _vertex_range_include(make_pair(true, true)),
Tiago Peixoto's avatar
   
Tiago Peixoto committed
76
77
 _vertex_range_invert(false),
 _edge_filter_map(_edge_index),
78
79
 _edge_range(make_pair(0.0, numeric_limits<double>::max())),
 _edge_range_include(make_pair(true, true)),
Tiago Peixoto's avatar
   
Tiago Peixoto committed
80
 _edge_range_invert(false)
Tiago Peixoto's avatar
Tiago Peixoto committed
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
{

}

//==============================================================================
// ~GraphInterface()
//==============================================================================
GraphInterface::~GraphInterface()
{
}

//==============================================================================
// SetVertexFilter()
//==============================================================================

96
97
void GraphInterface::SetVertexFilterProperty(string property)
{
98
#ifndef NO_RANGE_FILTERING
99
    _vertex_filter_property = property;
100

101
    if (property != "")
Tiago Peixoto's avatar
Tiago Peixoto committed
102
    {
103
        try
104
105
106
107
        {
            dynamic_property_map& pmap = find_property_map(_properties, property, typeid(graph_traits<multigraph_t>::vertex_descriptor));

            if (get_static_property_map<vector_property_map<double,vertex_index_map_t> >(&pmap))
108
                _vertex_filter_map = get_static_property_map<vector_property_map<double,vertex_index_map_t> >(pmap);
109
            else if (get_static_property_map<HashedDescriptorMap<vertex_index_map_t,double> >(&pmap))
110
                _vertex_filter_map = get_static_property_map<HashedDescriptorMap<vertex_index_map_t,double> >(pmap);
111
            else if (get_static_property_map<vector_property_map<size_t,vertex_index_map_t> >(&pmap))
112
                _vertex_filter_map = get_static_property_map<vector_property_map<size_t,vertex_index_map_t> >(pmap);
113
            else if (get_static_property_map<HashedDescriptorMap<vertex_index_map_t,size_t> >(&pmap))
114
                _vertex_filter_map = get_static_property_map<HashedDescriptorMap<vertex_index_map_t,size_t> >(pmap);
115
            else if (get_static_property_map<vertex_index_map_t>(&pmap))
116
                _vertex_filter_map = get_static_property_map<vertex_index_map_t>(pmap);
117
            else
118
                _vertex_filter_map = DynamicPropertyMapWrap<double, graph_traits<multigraph_t>::vertex_descriptor>(pmap);
119
        }
120
        catch (property_not_found)
121
122
123
        {
            throw GraphException("property " + property + " not found");
        }
124
    }
Tiago Peixoto's avatar
   
Tiago Peixoto committed
125
126
127
    else
    {
        _vertex_filter_map = _vertex_index;
128
129
        _vertex_range = make_pair(0.0, numeric_limits<double>::max());
        _vertex_range_include = make_pair(true, true);
Tiago Peixoto's avatar
   
Tiago Peixoto committed
130
131
        _vertex_range_invert = false;
    }
132
#else
133
134
    if (property != "")
        throw GraphException("support for graph range filtering was not enabled during compilation.");
135
#endif
Tiago Peixoto's avatar
Tiago Peixoto committed
136
137
}

Tiago Peixoto's avatar
   
Tiago Peixoto committed
138
bool GraphInterface::IsVertexFilterActive() const { return _vertex_filter_property != ""; }
Tiago Peixoto's avatar
Tiago Peixoto committed
139

140
void GraphInterface::SetEdgeFilterProperty(string property)
Tiago Peixoto's avatar
Tiago Peixoto committed
141
{
142
#ifndef NO_RANGE_FILTERING
143
    _edge_filter_property = property;
144

145
    if (property != "")
Tiago Peixoto's avatar
Tiago Peixoto committed
146
    {
147
148
149
        try
        {
            dynamic_property_map& pmap = find_property_map(_properties, property, typeid(graph_traits<multigraph_t>::edge_descriptor));
150

151
            if (get_static_property_map<vector_property_map<double,edge_index_map_t> >(&pmap))
152
                _edge_filter_map = get_static_property_map<vector_property_map<double,edge_index_map_t> >(pmap);
153
            else if (get_static_property_map<HashedDescriptorMap<edge_index_map_t,double> >(&pmap))
154
                _edge_filter_map = get_static_property_map<HashedDescriptorMap<edge_index_map_t,double> >(pmap);
155
            else if (get_static_property_map<vector_property_map<size_t,edge_index_map_t> >(&pmap))
156
                _edge_filter_map = get_static_property_map<vector_property_map<size_t,edge_index_map_t> >(pmap);
157
            else if (get_static_property_map<HashedDescriptorMap<edge_index_map_t,size_t> >(&pmap))
158
                _edge_filter_map = get_static_property_map<HashedDescriptorMap<edge_index_map_t,size_t> >(pmap);
159
            else if (get_static_property_map<edge_index_map_t>(&pmap))
160
                _edge_filter_map = get_static_property_map<edge_index_map_t>(pmap);
161
            else
162
                _edge_filter_map = DynamicPropertyMapWrap<double, graph_traits<multigraph_t>::edge_descriptor>(pmap);
163
        }
164
        catch (property_not_found)
165
166
167
        {
            throw GraphException("property " + property + " not found");
        }
168
    }
Tiago Peixoto's avatar
   
Tiago Peixoto committed
169
170
171
    else
    {
        _edge_filter_map = _edge_index;
172
173
        _edge_range = make_pair(0.0, numeric_limits<double>::max());
        _edge_range_include = make_pair(true, true);
Tiago Peixoto's avatar
   
Tiago Peixoto committed
174
175
        _edge_range_invert = false;
    }
176
#else
177
178
    if (property != "")
        throw GraphException("support for graph range filtering was not enabled during compilation.");
179
#endif
Tiago Peixoto's avatar
Tiago Peixoto committed
180
181
}

Tiago Peixoto's avatar
   
Tiago Peixoto committed
182
bool GraphInterface::IsEdgeFilterActive() const {return _edge_filter_property != "";}
Tiago Peixoto's avatar
Tiago Peixoto committed
183

Tiago Peixoto's avatar
   
Tiago Peixoto committed
184
void GraphInterface::SetVertexFilterRange(std::pair<double,double> allowed_range, std::pair<bool,bool> include, bool invert)
185
{
186
#ifndef NO_RANGE_FILTERING
187
188
189
    if (isinf(allowed_range.first) == 1)
        allowed_range.first = numeric_limits<double>::max();
    else if (isinf(allowed_range.first) == -1)
190
        allowed_range.first = -numeric_limits<double>::max();
191
192
193
    if (isinf(allowed_range.second) == 1)
        allowed_range.second = numeric_limits<double>::max();
    else if (isinf(allowed_range.second) == -1)
194
        allowed_range.second = -numeric_limits<double>::max();
195

196
    _vertex_range = allowed_range;
Tiago Peixoto's avatar
   
Tiago Peixoto committed
197
198
    _vertex_range_include = include;
    _vertex_range_invert = invert;
199
#else
200
    throw GraphException("support for graph range filtering was not enabled during compilation.");
201
202
203
#endif
}

Tiago Peixoto's avatar
   
Tiago Peixoto committed
204
void GraphInterface::SetEdgeFilterRange(std::pair<double,double> allowed_range, std::pair<bool,bool> include, bool invert)
205
{
Tiago Peixoto's avatar
   
Tiago Peixoto committed
206
#ifndef NO_RANGE_FILTERING
207
208
209
    if (isinf(allowed_range.first) == 1)
        allowed_range.first = numeric_limits<double>::max();
    else if (isinf(allowed_range.first) == -1)
210
        allowed_range.first = -numeric_limits<double>::max();
211
212
213
    if (isinf(allowed_range.second) == 1)
        allowed_range.second = numeric_limits<double>::max();
    else if (isinf(allowed_range.second) == -1)
214
        allowed_range.second = -numeric_limits<double>::max();
215

Tiago Peixoto's avatar
   
Tiago Peixoto committed
216
217
218
    _edge_range = allowed_range;
    _edge_range_include = include;
    _edge_range_invert = invert;
219
#else
Tiago Peixoto's avatar
   
Tiago Peixoto committed
220
221
    throw GraphException("support for graph range filtering was not enabled during compilation.");
#endif
222
223
}

224
225
226
227
228
229
230
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
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
348
349
350

//==============================================================================
// reindex_edges()
// This function will reindex all the edges, in the order in which they are 
// found, taking care of preserving all the properties
//==============================================================================

template<class Graph, class EdgeIndex>
void reindex_edges(Graph &g, EdgeIndex edge_index, dynamic_properties& dp)
{
    size_t n_edges = num_edges(g);
    if (n_edges == 0)
        return;
    vector<pair<typename graph_traits<Graph>::edge_descriptor,bool> > edge_map(n_edges, make_pair(typename graph_traits<Graph>::edge_descriptor(), false));
    typename graph_traits<Graph>::vertex_iterator v, v_end;
    typename graph_traits<Graph>::out_edge_iterator e, e_end;
    for (tie(v, v_end) = vertices(g); v != v_end; ++v)
        for (tie(e, e_end) = out_edges(*v, g); e != e_end; ++e)
        {
            size_t index = edge_index[*e];
            if (index >= edge_map.size())
                edge_map.resize(index+1);
            edge_map[index] = make_pair(*e, true);
        }
    size_t new_index = 0;
    for (tie(v, v_end) = vertices(g); v != v_end; ++v)
        for (tie(e, e_end) = out_edges(*v, g); e != e_end; ++e)
        {
            typename graph_traits<Graph>::edge_descriptor old_edge = edge_map[new_index].first;
            if (edge_map[new_index].second)
            {
                // another edge exists with the same index; indexes
                // must be swapped, as well as the properties
                edge_index[old_edge] = edge_index[*e];
                edge_map[edge_index[*e]] = make_pair(old_edge, true);
                edge_index[*e] = new_index;
                edge_map[new_index] = make_pair(*e, true);
                for (typeof(dp.begin()) p = dp.begin(); p != dp.end(); ++p)
                    if (p->second->key() == typeid(typename graph_traits<Graph>::edge_descriptor))
                    {
                        boost::any temp = p->second->get(*e);
                        p->second->put(*e, p->second->get(old_edge));
                        p->second->put(old_edge, temp);
                    }
            }
            else
            {
                // no other edge has this index; it must be then
                // assigned for this edge, and the properties must be
                // copied over
                size_t old_index = edge_index[*e];
                for (typeof(dp.begin()) p = dp.begin(); p != dp.end(); ++p)
                    if (p->second->key() == typeid(typename graph_traits<Graph>::edge_descriptor))
                    {
                        edge_index[*e] = old_index;
                        boost::any val = p->second->get(*e);
                        edge_index[*e] = new_index;
                        p->second->put(*e, val);
                    }
            }
            ++new_index;
        }
}

void GraphInterface::PurgeEdges()
{
    if (!IsEdgeFilterActive())
        return;

    RangeFilter<edge_filter_map_t> filter(_edge_filter_map, _edge_range, _edge_range_include, _edge_range_invert);
    graph_traits<multigraph_t>::vertex_iterator v, v_end;
    graph_traits<multigraph_t>::out_edge_iterator e, e_end;
    vector<graph_traits<multigraph_t>::edge_descriptor> deleted_edges;
    for (tie(v, v_end) = vertices(_mg); v != v_end; ++v)
    {
        for (tie(e, e_end) = out_edges(*v, _mg); e != e_end; ++e)
            if (!filter(*e))
                deleted_edges.push_back(*e);
        for (typeof(deleted_edges.begin()) iter = deleted_edges.begin(); iter != deleted_edges.end(); ++iter)
            remove_edge(*iter, _mg);
        deleted_edges.clear();
    }
    reindex_edges(_mg, _edge_index, _properties);
}

void GraphInterface::PurgeVertices()
{
    if (!IsVertexFilterActive())
        return;

    RangeFilter<vertex_filter_map_t> filter(_vertex_filter_map, _vertex_range, _vertex_range_include, _vertex_range_invert);
    size_t N = num_vertices(_mg);
    vector<bool> deleted(N, false);
    for (size_t i = 0; i < N; ++i)
        deleted[i] = !filter(vertex(i, _mg));

    //migrate properties
    size_t last = 0;
    for (size_t i = 0; i < N; ++i)
    {
        graph_traits<multigraph_t>::vertex_descriptor v = vertex(i, _mg);
        if (filter(v))
        {
            for (typeof(_properties.begin()) p = _properties.begin(); p != _properties.end(); ++p)
                if (p->second->key() == typeid(graph_traits<multigraph_t>::vertex_descriptor))
                    try
                    {
                        p->second->put(vertex(last, _mg), p->second->get(v));
                    }
                    catch (dynamic_const_put_error) {} // index prop. is const
            last++;
        }
    }

    //remove vertices
    for (size_t i = N-1; i >= 0 && i < N; --i)
    {
        if (deleted[i])
        {
            graph_traits<multigraph_t>::vertex_descriptor v = vertex(i, _mg);
            clear_vertex(v, _mg);
            remove_vertex(v, _mg);
        }
    }
    reindex_edges(_mg, _edge_index, _properties);
}

Tiago Peixoto's avatar
Tiago Peixoto committed
351
352
353
354
355
356
357
//==============================================================================
// GetNumberOfVertices()
//==============================================================================
size_t GraphInterface::GetNumberOfVertices() const
{
    size_t n = 0;
    if (IsVertexFilterActive())
358
        check_filter(*this,var(n)=bind<size_t>(HardNumVertices(),_1),reverse_check(),directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
359
360
361
362
363
364
365
366
367
368
369
370
    else
        check_filter(*this,var(n)=bind<size_t>(SoftNumVertices(),_1),reverse_check(),directed_check());
    return n;
}

//==============================================================================
// GetNumberOfEdges()
//==============================================================================
size_t GraphInterface::GetNumberOfEdges() const
{
    size_t n = 0;
    if (IsEdgeFilterActive() || IsVertexFilterActive())
371
        check_filter(*this,var(n)=bind<size_t>(HardNumEdges(),_1),reverse_check(),directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
372
373
374
375
376
377
    else
        check_filter(*this,var(n)=bind<size_t>(SoftNumEdges(),_1),reverse_check(),directed_check());
    return n;
}

//==============================================================================
378
379
// get_vertex_histogram
// generalized functor to obtain histogram of different types of "degrees"
Tiago Peixoto's avatar
Tiago Peixoto committed
380
381
//==============================================================================
template <class DegreeSelector>
382
struct get_vertex_histogram
Tiago Peixoto's avatar
Tiago Peixoto committed
383
{
384
    get_vertex_histogram(DegreeSelector& deg): _degree(deg) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
385
    template <class Graph, class Hist>
386
    void operator()(const Graph& g, Hist& hist) const
Tiago Peixoto's avatar
Tiago Peixoto committed
387
    {
388
389
390
391
392
393
394
        SharedMap<Hist> s_hist(hist);
        int i, N = num_vertices(g);
        #pragma omp parallel for default(shared) private(i) firstprivate(s_hist) schedule(dynamic)
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
395
                continue;
396
397
398
            s_hist[_degree(v,g)]++;
        }
        s_hist.Gather();
Tiago Peixoto's avatar
Tiago Peixoto committed
399
400
401
402
    }
    DegreeSelector& _degree;
};

403
struct choose_vertex_histogram
Tiago Peixoto's avatar
Tiago Peixoto committed
404
{
405
    choose_vertex_histogram(const GraphInterface& g, GraphInterface::deg_t deg, GraphInterface::hist_t& hist)
406
        : _g(g), _hist(hist)
Tiago Peixoto's avatar
Tiago Peixoto committed
407
    {
408
        tie(_deg, _deg_name) = get_degree_type(deg);
Tiago Peixoto's avatar
Tiago Peixoto committed
409
410
411
412
    }
    template <class DegreeSelector>
    void operator()(DegreeSelector)
    {
413
414
        if (mpl::at<degree_selector_index,DegreeSelector>::type::value == _deg)
        {
415
            DegreeSelector selector(_deg_name, _g, true);
416
417
            check_filter(_g, bind<void>(get_vertex_histogram<DegreeSelector>(selector), _1, var(_hist)),reverse_check(),directed_check());
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
418
419
420
421
    }
    const GraphInterface &_g;
    GraphInterface::hist_t &_hist;
    GraphInterface::degree_t _deg;
422
    string _deg_name;
Tiago Peixoto's avatar
Tiago Peixoto committed
423
424
425
};

//==============================================================================
426
// GetVertexHistogram(deg_type)
Tiago Peixoto's avatar
Tiago Peixoto committed
427
//==============================================================================
428
GraphInterface::hist_t GraphInterface::GetVertexHistogram(GraphInterface::deg_t deg) const
Tiago Peixoto's avatar
Tiago Peixoto committed
429
430
{
    hist_t hist;
431
    try
Tiago Peixoto's avatar
Tiago Peixoto committed
432
    {
433
        mpl::for_each<mpl::vector<in_degreeS, out_degreeS, total_degreeS, scalarS> >(choose_vertex_histogram(*this, deg, hist));
Tiago Peixoto's avatar
Tiago Peixoto committed
434
435
436
    }
    catch (dynamic_get_failure &e)
    {
437
        throw GraphException("error getting scalar property: " + string(e.what()));
Tiago Peixoto's avatar
Tiago Peixoto committed
438
439
440
441
442
    }

    return hist;
}

443
444
445
446
447
448
449
450
451
452
//==============================================================================
// get_edge_histogram
// generalized functor to obtain histogram of edge properties
//==============================================================================
struct get_edge_histogram
{
    get_edge_histogram(scalarS& prop): _prop(prop) {}
    template <class Graph, class Hist>
    void operator()(const Graph& g, Hist& hist) const
    {
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
        SharedMap<Hist> s_hist(hist);

        int i, N = num_vertices(g);
        #pragma omp parallel for default(shared) private(i) firstprivate(s_hist) schedule(dynamic)
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;

            typename graph_traits<Graph>::out_edge_iterator e, e_begin, e_end;
            tie(e_begin,e_end) = out_edges(v,g);
            for(e = e_begin; e != e_end; ++e)
                if(is_convertible<typename graph_traits<Graph>::directed_category, undirected_tag>::value)
                    s_hist[_prop(*e,g)] += 0.5;
                else
                    s_hist[_prop(*e,g)]++;
        }
        s_hist.Gather();
472
473
474
475
476
477
478
479
480
481
    }
    scalarS& _prop;
};

//==============================================================================
// GetEdgeHistogram(property)
//==============================================================================
GraphInterface::hist_t GraphInterface::GetEdgeHistogram(string property) const
{
    hist_t hist;
482
    try
483
    {
484
        scalarS prop(property, *this, false);
485
        check_filter(*this, bind<void>(get_edge_histogram(prop), _1, var(hist)),reverse_check(),directed_check());
486
487
488
    }
    catch (dynamic_get_failure &e)
    {
489
        throw GraphException("error getting scalar property: " + string(e.what()));
490
491
492
493
494
495
    }


    return hist;
}

Tiago Peixoto's avatar
Tiago Peixoto committed
496
//==============================================================================
497
// LabelComponents(property)
Tiago Peixoto's avatar
Tiago Peixoto committed
498
499
//==============================================================================

500
struct label_components
Tiago Peixoto's avatar
Tiago Peixoto committed
501
{
502
503
    template <class Graph, class CompMap>
    void operator()(const Graph &g, CompMap comp_map) const
504
    {
505
        get_components(g, comp_map, typename is_convertible<typename graph_traits<Graph>::directed_category, directed_tag>::type());
506
507
508
509
    }

    template <class Graph, class CompMap>
    void get_components(const Graph& g, CompMap comp_map, boost::true_type is_directed) const
Tiago Peixoto's avatar
Tiago Peixoto committed
510
    {
511
        strong_components(g, comp_map);
Tiago Peixoto's avatar
Tiago Peixoto committed
512
513
    }

514
515
    template <class Graph, class CompMap>
    void get_components(const Graph& g, CompMap comp_map, boost::false_type is_directed) const
Tiago Peixoto's avatar
Tiago Peixoto committed
516
    {
517
        connected_components(g, comp_map);
Tiago Peixoto's avatar
Tiago Peixoto committed
518
    }
519

Tiago Peixoto's avatar
Tiago Peixoto committed
520
521
};

522
void GraphInterface::LabelComponents(string prop)
Tiago Peixoto's avatar
Tiago Peixoto committed
523
{
524
525
    typedef vector_property_map<size_t, vertex_index_map_t> comp_map_t;
    comp_map_t comp_map(_vertex_index);
Tiago Peixoto's avatar
Tiago Peixoto committed
526

527
    check_filter(*this, bind<void>(label_components(), _1, comp_map), reverse_check(), directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
528

529
530
    try
    {
531
532
        find_property_map(_properties, prop, typeid(graph_traits<multigraph_t>::vertex_descriptor));
        RemoveVertexProperty(prop);
Tiago Peixoto's avatar
Tiago Peixoto committed
533
    }
534
    catch (property_not_found) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
535

536
    _properties.property(prop, comp_map);
Tiago Peixoto's avatar
Tiago Peixoto committed
537
538
}

Tiago Peixoto's avatar
Tiago Peixoto committed
539
540
541
542
543
544
545
546
547
//==============================================================================
// label_parallel_edges
// label parallel edges in order
//==============================================================================
struct label_parallel_edges
{
    template <class Graph, class EdgeIndexMap, class ParallelMap>
    void operator()(const Graph& g, EdgeIndexMap edge_index, ParallelMap parallel) const
    {
548
549
550
        int i, N = num_vertices(g);
        #pragma omp parallel for default(shared) private(i) schedule(dynamic)
        for (i = 0; i < N; ++i)
551
        {
552
553
554
555
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;

556
557
            tr1::unordered_set<typename graph_traits<Graph>::edge_descriptor,DescriptorHash<EdgeIndexMap> > p_edges(0, DescriptorHash<EdgeIndexMap>(edge_index));
            typename graph_traits<Graph>::out_edge_iterator e1, e2, e_end;
558
            for (tie(e1, e_end) = out_edges(v, g); e1 != e_end; ++e1)
559
            {
560
561
562
563
                if (p_edges.find(*e1) != p_edges.end())
                    continue;
                size_t n = 0;
                put(parallel, *e1, n);
564
                for (tie(e2, e_end) = out_edges(v, g); e2 != e_end; ++e2)
565
566
567
568
569
                    if (*e2 != *e1 && target(*e1, g) == target(*e2, g))
                    {
                        put(parallel, *e2, ++n);
                        p_edges.insert(*e2);
                    }
570
571
            }
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
572
573
574
575
576
577
578
579
580
581
    }
};

//==============================================================================
// LabelParallelEdges(property)
//==============================================================================
void GraphInterface::LabelParallelEdges(string property)
{
    try
    {
582
583
        DynamicPropertyMapWrap<size_t,graph_traits<multigraph_t>::edge_descriptor> parallel_map(find_property_map(_properties, property, typeid(graph_traits<multigraph_t>::edge_descriptor)));
        check_filter(*this, bind<void>(label_parallel_edges(), _1, _edge_index, parallel_map), reverse_check(), directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
584
    }
585
    catch (property_not_found)
Tiago Peixoto's avatar
Tiago Peixoto committed
586
    {
587
        typedef vector_property_map<long,edge_index_map_t> parallel_map_t;
588
589
590
        parallel_map_t parallel_map(_edge_index);
        check_filter(*this, bind<void>(label_parallel_edges(), _1, _edge_index, parallel_map), reverse_check(), directed_check());
        _properties.property(property, parallel_map);
Tiago Peixoto's avatar
Tiago Peixoto committed
591
592
593
594
    }
}


Tiago Peixoto's avatar
Tiago Peixoto committed
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
//==============================================================================
// InsertEdgeIndexProperty(property)
//==============================================================================
void GraphInterface::InsertEdgeIndexProperty(string property)
{
    _properties.property(property, _edge_index);
}

//==============================================================================
// InsertVertexIndexProperty(property)
//==============================================================================
void GraphInterface::InsertVertexIndexProperty(string property)
{
    _properties.property(property, _vertex_index);
}

//==============================================================================
// InitSignalHandling()
//==============================================================================

void catch_sig_stop(int sig_num)
{
    std::cerr << "graph-tool: received signal ";
    switch (sig_num)
    {
    case SIGINT:
        std::cerr << "SIGINT (Interrupt).";
        break;
    case SIGTERM:
        std::cerr << "SIGTERM (Termination).";
        break;
    case SIGQUIT:
        std::cerr << "SIGQUIT (Terminal quit).";
        break;
    case SIGHUP:
        std::cerr << "SIGHUP (Hangup).";
        break;
    case SIGPWR:
        std::cerr << "SIGPWR (Power failure restart).";
        break;
    case SIGSEGV:
        std::cerr << "SIGSEGV (Segmentation fault). There's a bug somewhere in the program. Go fix it.";
        break;
    case SIGBUS:
        std::cerr << "SIGBUS (BUS error). The bus is broken, I guess...";
        break;
    case SIGFPE:
        std::cerr << "SIGFPE (Floating-point exception). INFs and NANs are wreaking havoc.";
        break;
    case SIGILL:
        std::cerr << "SIGILL (Illegal instruction). Did you compile it right?";
        break;
    case SIGXCPU:
        std::cerr << "SIGXCPU (CPU limit exceeded). Time's over.";
        break;
    case SIGXFSZ:
        std::cerr << "SIGXFSZ (File size limit exceeded). The fascist sysadmin doesn't let you write more.";
        break;
    }
    std::cerr << " Bailing out cowardly and calling abort()." << std::endl;
    abort();
}


void GraphInterface::InitSignalHandling()
{
    signal(SIGINT, catch_sig_stop);
    signal(SIGTERM, catch_sig_stop);
    signal(SIGQUIT, catch_sig_stop);
    signal(SIGHUP, catch_sig_stop);
    signal(SIGPWR, catch_sig_stop);
    signal(SIGSEGV, catch_sig_stop);
    signal(SIGBUS, catch_sig_stop);
    signal(SIGFPE, catch_sig_stop);
    signal(SIGILL, catch_sig_stop);
    signal(SIGXCPU, catch_sig_stop);
    signal(SIGXFSZ, catch_sig_stop);
}