graph_parallel.hh 4.23 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) 2006-2018 Tiago de Paula Peixoto <tiago@skewed.de>
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
//
// 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 3
// 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, see <http://www.gnu.org/licenses/>.

#ifndef GRAPH_PARALLEL_HH
#define GRAPH_PARALLEL_HH

21
#include "hash_map_wrap.hh"
22
#include "graph_util.hh"
23 24 25
#include "idx_map.hh"

#include <boost/range/adaptor/reversed.hpp>
26 27 28 29 30 31

namespace graph_tool
{
using namespace std;
using namespace boost;

32
// label parallel edges in the order they are found, starting from 1
33 34
struct label_parallel_edges
{
35
    template <class Graph, class ParallelMap>
36
    void operator()(const Graph& g, ParallelMap parallel, bool mark_only) const
37
    {
38
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
39
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;
40
        typename property_map<Graph, edge_index_t>::type eidx = get(edge_index, g);
41

42 43 44 45 46 47
        idx_map<vertex_t, edge_t> vset;
        idx_map<size_t, bool> self_loops;

        #pragma omp parallel if (num_vertices(g) > OPENMP_MIN_THRESH) \
            firstprivate(vset) firstprivate(self_loops)
        parallel_vertex_loop_no_spawn
48 49 50
            (g,
             [&](auto v)
             {
51
                 for (auto e : out_edges_range(v, g))
52
                 {
53
                     vertex_t u = target(e, g);
54 55

                     // do not visit edges twice in undirected graphs
56
                     if (!graph_tool::is_directed(g) && u < v)
57 58 59 60
                         continue;

                     if (u == v)
                     {
61
                         if (self_loops[eidx[e]])
62
                             continue;
63
                         self_loops[eidx[e]] = true;
64 65 66 67 68
                     }

                     auto iter = vset.find(u);
                     if (iter == vset.end())
                     {
69
                         vset[u] = e;
70 71 72 73 74
                     }
                     else
                     {
                         if (mark_only)
                         {
75
                             parallel[e] = true;
76 77 78
                         }
                         else
                         {
79 80
                             parallel[e] = parallel[iter->second] + 1;
                             vset[u] = e;
81 82 83
                         }
                     }
                 }
84 85
                 vset.clear();
                 self_loops.clear();
86
             });
87 88 89 90 91 92
    }
};

// label self loops edges in the order they are found, starting from 1
struct label_self_loops
{
93 94
    template <class Graph, class SelfMap>
    void operator()(const Graph& g, SelfMap self, bool mark_only) const
95
    {
96 97 98 99 100 101 102 103 104 105 106 107 108
        parallel_vertex_loop
            (g,
             [&](auto v)
             {
                 size_t n = 1;
                 for (auto e : out_edges_range(v, g))
                 {
                     if (target(e, g) == v)
                         put(self, e, mark_only ? 1 : n++);
                     else
                    put(self, e, 0);
                 }
             });
109 110 111
    }
};

112 113 114 115 116 117
// remove edges with label larger than 0
struct remove_labeled_edges
{
    template <class Graph, class LabelMap>
    void operator()(Graph& g, LabelMap label) const
    {
118 119
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;
        vector<edge_t> r_edges;
120
        for (auto v : vertices_range(g))
121
        {
122
            for (auto e : out_edges_range(v, g))
123
            {
124 125
                if (label[e] > 0)
                    r_edges.push_back(e);
126
            }
127 128 129 130 131 132

            while (!r_edges.empty())
            {
                remove_edge(r_edges.back(), g);
                r_edges.pop_back();
            }
133 134 135 136
        }
    }
};

137 138 139
} // graph_tool namespace

#endif //GRAPH_PARALLEL_HH