graph.cc 11.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  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 22 23 24 25 26

#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>
27
#include <boost/python/make_function.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
28 29 30 31 32 33 34 35 36 37

#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"
38
#include "graph_util.hh"
39
#include "shared_map.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
40 41 42 43 44 45 46

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


47
// this is the constructor for the graph interface
Tiago Peixoto's avatar
Tiago Peixoto committed
48
GraphInterface::GraphInterface()
49 50 51 52 53 54
    :_mg(),
     _reversed(false),
     _directed(true),
     _vertex_index(get(vertex_index,_mg)),
     _edge_index(get(edge_index_t(),_mg)),
     _vertex_filter_map(_vertex_index),
55 56
     _vertex_filter_invert(false),
     _vertex_filter_active(false),
57
     _edge_filter_map(_edge_index),
58 59
     _edge_filter_invert(false),
     _edge_filter_active(false)
Tiago Peixoto's avatar
Tiago Peixoto committed
60 61 62 63
{

}

64
// the destructor
Tiago Peixoto's avatar
Tiago Peixoto committed
65 66 67 68
GraphInterface::~GraphInterface()
{
}

69 70
// this will get the number of vertices, either the "soft" O(1) way, or the hard
// O(V) way, which is necessary if the graph is filtered
Tiago Peixoto's avatar
Tiago Peixoto committed
71 72 73 74
size_t GraphInterface::GetNumberOfVertices() const
{
    size_t n = 0;
    if (IsVertexFilterActive())
75
        run_action<>()(*this, var(n)=bind<size_t>(HardNumVertices(),_1))();
Tiago Peixoto's avatar
Tiago Peixoto committed
76
    else
77
        run_action<>()(*this, var(n)=bind<size_t>(SoftNumVertices(),_1))();
Tiago Peixoto's avatar
Tiago Peixoto committed
78 79 80
    return n;
}

81 82 83
// this will get the number of edges, either the "soft" O(E) way, or the hard
// O(E) way, which is necessary if the graph is filtered. Both cases are of
// linear complexity, since num_edges() is O(E) in Boost's adjacency_list
Tiago Peixoto's avatar
Tiago Peixoto committed
84 85 86 87
size_t GraphInterface::GetNumberOfEdges() const
{
    size_t n = 0;
    if (IsEdgeFilterActive() || IsVertexFilterActive())
88
        run_action<>()(*this, var(n)=bind<size_t>(HardNumEdges(),_1))();
Tiago Peixoto's avatar
Tiago Peixoto committed
89
    else
90
        run_action<>()(*this, var(n)=bind<size_t>(SoftNumEdges(),_1))();
Tiago Peixoto's avatar
Tiago Peixoto committed
91 92 93
    return n;
}

94 95
// generalized functor to obtain histogram of different types of "degrees"
struct get_vertex_histogram
Tiago Peixoto's avatar
Tiago Peixoto committed
96
{
97 98
    template <class Graph, class DegreeSelector, class Hist>
    void operator()(const Graph* gp, DegreeSelector deg, Hist& hist) const
Tiago Peixoto's avatar
Tiago Peixoto committed
99
    {
100
        const Graph& g = *gp;
101 102
        SharedMap<Hist> s_hist(hist);
        int i, N = num_vertices(g);
103 104
        #pragma omp parallel for default(shared) private(i) \
            firstprivate(s_hist) schedule(dynamic)
105 106 107 108
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
109
                continue;
110
            s_hist[deg(v,g)]++;
111 112
        }
        s_hist.Gather();
Tiago Peixoto's avatar
Tiago Peixoto committed
113 114 115
    }
};

116 117

// this will return the vertex histogram of degrees or scalar properties
118
hist_t
119
GraphInterface::GetVertexHistogram(GraphInterface::deg_t deg) const
Tiago Peixoto's avatar
Tiago Peixoto committed
120 121
{
    hist_t hist;
122
    
123
    try
Tiago Peixoto's avatar
Tiago Peixoto committed
124
    {
125 126 127
        run_action<>()(*this, bind<void>(get_vertex_histogram(), _1, _2,
                                         var(hist)),
                       all_selectors())(degree_selector(deg, _properties));
Tiago Peixoto's avatar
Tiago Peixoto committed
128 129 130
    }
    catch (dynamic_get_failure &e)
    {
131 132
        throw GraphException("error getting scalar property: " +
                             string(e.what()));
Tiago Peixoto's avatar
Tiago Peixoto committed
133 134 135 136 137
    }

    return hist;
}

138 139 140
// generalized functor to obtain histogram of edge properties
struct get_edge_histogram
{
141 142 143 144
    template <class Graph, class Prop, class Hist>
    void operator()(const Graph* gp, Prop eprop, Hist& hist) const
    {        
        const Graph& g = *gp;
145 146 147
        SharedMap<Hist> s_hist(hist);

        int i, N = num_vertices(g);
148 149
        #pragma omp parallel for default(shared) private(i) \
            firstprivate(s_hist)  schedule(dynamic)
150 151 152 153 154 155 156 157 158
        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)
159
                s_hist[eprop[*e]]++;
160 161
        }
        s_hist.Gather();
162 163 164 165 166 167 168 169 170

        typedef typename graph_traits<Graph>::directed_category
            directed_category;
        if(is_convertible<directed_category,undirected_tag>::value)
        {
            for (typeof(s_hist.begin()) iter = s_hist.begin();
                 iter != s_hist.end(); ++iter)
                iter->second /= typename Hist::value_type::second_type(2);
        }
171 172 173
    }
};

174 175

// returns the histogram of a given edge property
176
hist_t GraphInterface::GetEdgeHistogram(string property) const
177 178
{
    hist_t hist;
179
    try
180
    {
181 182 183 184
        run_action<>()(*this, bind<void>(get_edge_histogram(), _1, _2,
                                         var(hist)),
                       edge_scalar_properties())
            (prop(property, _edge_index, _properties));
185
    }
186
    catch (dynamic_get_failure& e)
187
    {
188 189
        throw GraphException("error getting scalar property: " +
                             string(e.what()));
190 191 192 193 194
    }

    return hist;
}

195 196 197
// this will label the components of a graph to a given vertex property, from
// [0, number of components - 1]. If the graph is directed the "strong
// components" are used.
198
struct label_components
Tiago Peixoto's avatar
Tiago Peixoto committed
199
{
200
    template <class Graph, class CompMap>
201
    void operator()(const Graph* gp, CompMap comp_map) const
202
    {
203
        const Graph& g = *gp;
204 205 206 207 208
        typedef typename graph_traits<Graph>::directed_category
            directed_category;
        get_components(g, comp_map,
                       typename is_convertible<directed_category,
                                               directed_tag>::type());
209 210 211
    }

    template <class Graph, class CompMap>
212 213
    void get_components(const Graph& g, CompMap comp_map,
                        boost::true_type is_directed) const
Tiago Peixoto's avatar
Tiago Peixoto committed
214
    {
215
        strong_components(g, comp_map);
Tiago Peixoto's avatar
Tiago Peixoto committed
216 217
    }

218
    template <class Graph, class CompMap>
219 220
    void get_components(const Graph& g, CompMap comp_map,
                        boost::false_type is_directed) const
Tiago Peixoto's avatar
Tiago Peixoto committed
221
    {
222
        connected_components(g, comp_map);
Tiago Peixoto's avatar
Tiago Peixoto committed
223
    }
224

Tiago Peixoto's avatar
Tiago Peixoto committed
225 226
};

227
void GraphInterface::LabelComponents(string prop)
Tiago Peixoto's avatar
Tiago Peixoto committed
228
{
229 230
    try
    {
231 232 233 234 235 236 237 238 239
        run_action<>()(*this, label_components(), _1, vertex_scalar_selectors())
            (degree_selector(prop, _properties));
    }
    catch (property_not_found) 
    {
        typedef vector_property_map<int32_t, vertex_index_map_t> comp_map_t;
        comp_map_t comp_map(_vertex_index);
        _properties.property(prop, comp_map);
        run_action<>()(*this, bind<void>(label_components(), _1, comp_map))();
Tiago Peixoto's avatar
Tiago Peixoto committed
240 241 242
    }
}

243
// label parallel edges in the order they are found, starting from 0
Tiago Peixoto's avatar
Tiago Peixoto committed
244 245 246
struct label_parallel_edges
{
    template <class Graph, class EdgeIndexMap, class ParallelMap>
247
    void operator()(const Graph* gp, EdgeIndexMap edge_index,
248
                    ParallelMap parallel) const
Tiago Peixoto's avatar
Tiago Peixoto committed
249
    {
250
        const Graph& g = *gp;
251 252
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;

253 254 255
        int i, N = num_vertices(g);
        #pragma omp parallel for default(shared) private(i) schedule(dynamic)
        for (i = 0; i < N; ++i)
256
        {
257 258 259 260
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;

261 262 263
            tr1::unordered_set<edge_t,DescriptorHash<EdgeIndexMap> >
                p_edges(0, DescriptorHash<EdgeIndexMap>(edge_index));

264
            typename graph_traits<Graph>::out_edge_iterator e1, e2, e_end;
265
            for (tie(e1, e_end) = out_edges(v, g); e1 != e_end; ++e1)
266
            {
267 268 269 270
                if (p_edges.find(*e1) != p_edges.end())
                    continue;
                size_t n = 0;
                put(parallel, *e1, n);
271
                for (tie(e2, e_end) = out_edges(v, g); e2 != e_end; ++e2)
272 273 274 275 276
                    if (*e2 != *e1 && target(*e1, g) == target(*e2, g))
                    {
                        put(parallel, *e2, ++n);
                        p_edges.insert(*e2);
                    }
277 278
            }
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
279 280 281 282 283 284
    }
};

void GraphInterface::LabelParallelEdges(string property)
{
    try
285 286 287 288 289
    {        
        run_action<>()(*this, bind<void>(label_parallel_edges(), _1, 
                                         _edge_index, _2),
                       edge_scalar_properties()) 
            (prop(property, _edge_index, _properties));
Tiago Peixoto's avatar
Tiago Peixoto committed
290
    }
291
    catch (property_not_found)
Tiago Peixoto's avatar
Tiago Peixoto committed
292
    {
293
        typedef vector_property_map<int32_t,edge_index_map_t> parallel_map_t;
294 295
        parallel_map_t parallel_map(_edge_index);
        _properties.property(property, parallel_map);
296 297
        run_action<>()(*this, bind<void>(label_parallel_edges(), _1, 
                                         _edge_index, parallel_map))();
Tiago Peixoto's avatar
Tiago Peixoto committed
298 299 300 301
    }
}


302
// this inserts the edge index map as a property
Tiago Peixoto's avatar
Tiago Peixoto committed
303 304 305 306 307
void GraphInterface::InsertEdgeIndexProperty(string property)
{
    _properties.property(property, _edge_index);
}

308
// this inserts the vertex index map as a property
Tiago Peixoto's avatar
Tiago Peixoto committed
309 310 311 312 313
void GraphInterface::InsertVertexIndexProperty(string property)
{
    _properties.property(property, _vertex_index);
}

314 315

// signal handling
Tiago Peixoto's avatar
Tiago Peixoto committed
316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337

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:
338 339
        std::cerr << "SIGSEGV (Segmentation fault). "
                  << "There's a bug somewhere in the program. Go fix it.";
Tiago Peixoto's avatar
Tiago Peixoto committed
340 341 342 343 344
        break;
    case SIGBUS:
        std::cerr << "SIGBUS (BUS error). The bus is broken, I guess...";
        break;
    case SIGFPE:
345 346
        std::cerr << "SIGFPE (Floating-point exception). "
                  << "INFs and NANs are wreaking havoc.";
Tiago Peixoto's avatar
Tiago Peixoto committed
347 348 349 350 351 352 353 354
        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:
355 356
        std::cerr << "SIGXFSZ (File size limit exceeded). "
                  << "The fascist sysadmin doesn't let you write more.";
Tiago Peixoto's avatar
Tiago Peixoto committed
357 358 359 360 361 362
        break;
    }
    std::cerr << " Bailing out cowardly and calling abort()." << std::endl;
    abort();
}

363
// initialize signal handling
Tiago Peixoto's avatar
Tiago Peixoto committed
364 365 366 367 368 369 370 371 372 373 374 375 376 377 378

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