graph_parallel.hh 4.05 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-2017 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
26
27
28

namespace graph_tool
{
using namespace std;
using namespace boost;

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

39
40
41
42
43
44
45
46
47
48
49
50
51
        parallel_vertex_loop
            (g,
             [&](auto v)
             {
                 gt_hash_map<vertex_t, edge_t> vset;
                 gt_hash_map<size_t, bool> self_loops;

                 typename graph_traits<Graph>::out_edge_iterator e, e_end;
                 for (tie(e, e_end) = out_edges(v, g); e != e_end; ++e)
                 {
                     vertex_t u = target(*e, g);

                     // do not visit edges twice in undirected graphs
52
                     if (!graph_tool::is_directed(g) && u < v)
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
                         continue;

                     if (u == v)
                     {
                         if (self_loops[eidx[*e]])
                             continue;
                         self_loops[eidx[*e]] = true;
                     }

                     auto iter = vset.find(u);
                     if (iter == vset.end())
                     {
                         vset[u] = *e;
                     }
                     else
                     {
                         if (mark_only)
                         {
                             parallel[*e] = true;
                         }
                         else
                         {
                             parallel[*e] = parallel[iter->second] + 1;
                             vset[u] = *e;
                         }
                     }
                 }
             });
81
82
83
84
85
86
    }
};

// label self loops edges in the order they are found, starting from 1
struct label_self_loops
{
87
88
    template <class Graph, class SelfMap>
    void operator()(const Graph& g, SelfMap self, bool mark_only) const
89
    {
90
91
92
93
94
95
96
97
98
99
100
101
102
        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);
                 }
             });
103
104
105
    }
};

106
107
108
109
110
111
// remove edges with label larger than 0
struct remove_labeled_edges
{
    template <class Graph, class LabelMap>
    void operator()(Graph& g, LabelMap label) const
    {
112
        for (auto v : vertices_range(g))
113
114
115
        {
            typedef typename graph_traits<Graph>::edge_descriptor edge_t;
            vector<edge_t> r_edges;
116
            for (auto e : out_edges_range(v, g))
117
            {
118
119
                if (label[e] > 0)
                    r_edges.push_back(e);
120
121
122
123
124
125
126
            }
            for (size_t j = 0; j < r_edges.size(); ++j)
                remove_edge(r_edges[j], g);
        }
    }
};

127
128
129
} // graph_tool namespace

#endif //GRAPH_PARALLEL_HH