graph_geometric.hh 5.26 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2007-2010 Tiago de Paula Peixoto <tiago@skewed.de>
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//
// 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_GEOMETRIC_HH
#define GRAPH_GEOMETRIC_HH

#include <iostream>
22
23
24
25
26
27
#if (GCC_VERSION >= 40400)
#   include <tr1/unordered_map>
#else
#   include <boost/tr1/unordered_map.hpp>
#endif

28
29
30
#include <boost/functional/hash.hpp>
#include "graph_util.hh"

31
32
33
#include <ext/numeric>
using __gnu_cxx::power;

34
35
36
37
38
39
namespace graph_tool
{
using namespace std;
using namespace boost;


40
41
42
template <class Point, class Range>
void get_box(const Point& p, double w, vector<int>& box,
             const Range& ranges, bool periodic)
43
44
45
46
{
    if (box.size() != p.size())
        box.resize(p.size());
    for (size_t i = 0; i < p.size(); ++i)
47
48
49
50
51
    {
        box[i] = int(floor(p[i] / w));
        if (periodic && p[i] == ranges[i].second)
            box[i] -= 1;
    }
52
53
}

54
55
56
template <class Point, class Range>
double get_dist(const Point& p1, const Point& p2,
                const Range& ranges, bool periodic)
57
{
58
    double r = 0, diff, size;
59
    for (size_t i = 0; i < p1.size(); ++i)
60
61
62
63
64
65
66
67
68
    {
        diff = abs(p1[i] - p2[i]);
        if (periodic)
        {
            size = abs(ranges[i].second - ranges[i].first);
            diff = min(diff, abs(diff - size));
        }
        r += pow(diff, 2);
    }
69
70
71
    return sqrt(r);
}

72
void periodic(vector<int>& box, const vector<pair<int,int> >& ranges)
73
{
74
    for (size_t i = 0; i < box.size(); ++i)
75
    {
76
77
78
79
        if (box[i] >= ranges[i].second)
            box[i] = ranges[i].first;
        if (box[i] < ranges[i].first)
            box[i] = ranges[i].second - 1;
80
81
82
    }
}

83

84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
template <class Graph>
bool is_adjacent(typename graph_traits<Graph>::vertex_descriptor v1,
                 typename graph_traits<Graph>::vertex_descriptor v2,
                 Graph& g)
{
    typename graph_traits<Graph>::out_edge_iterator e, e_end;
    for (tie(e, e_end) = out_edges(v1, g); e != e_end; ++e)
        if (target(*e, g) == v2)
            return true;
    return false;
}

struct get_geometric
{
    template <class Graph, class Pos>
    void operator()(Graph& g, Pos upos, vector<vector<double> >& points,
                    vector<pair<double, double> >& ranges,
                    double r, bool periodic_boundary) const
    {
        int N = points.size();
        typename Pos::checked_t pos = upos.get_checked();
        vector<int> box;
106
107
108
109
110
111
112
113
114
115
116
117
        vector<pair<int, int> > box_ranges;

        double w = 2 * r;
        if (periodic_boundary)
        {
            box_ranges.resize(ranges.size());
            for (size_t i = 0; i < ranges.size(); ++i)
            {
                box_ranges[i].first = floor(ranges[i].first / w);
                box_ranges[i].second = ceil(ranges[i].second / w);
            }
        }
118
119
120
121
122
123
124
125
126
127

        tr1::unordered_multimap<vector<int>,
                                typename graph_traits<Graph>::vertex_descriptor,
                                boost::hash<vector<int> > > boxes;

        for (int i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = add_vertex(g);
            pos[v].resize(points[i].size());
            copy(points[i].begin(), points[i].end(), pos[v].begin());
128
            get_box(points[i], w, box, ranges, periodic_boundary);
129
130
131
132
133
134
135
136
137
            boxes.insert(make_pair(box, v));
        }

        #pragma omp parallel for default(shared) private(i, box) \
            schedule(dynamic)
        for (int i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);

138
            get_box(points[i], w, box, ranges, periodic_boundary);
139
            for (int k = 0; k < power(3, int(box.size())); ++k)
140
            {
141
142
                for (int j = 0; j < box.size(); ++j)
                  box[j] += ((k / power(3, j)) % 3) - 1;
143

144
145
146
                if (periodic_boundary)
                    periodic(box, box_ranges);

147
148
149
150
151
152
                typeof(boxes.begin()) iter, end;
                for (tie(iter, end) = boxes.equal_range(box);
                     iter != end; ++iter)
                {
                    typename graph_traits<Graph>::vertex_descriptor w =
                        iter->second;
153
154
                    double d = get_dist(pos[v], pos[w], ranges,
                                        periodic_boundary);
155

156
157
                    if (w > v && d <= r &&
                        (!periodic_boundary || !is_adjacent(v, w, g)))
158
159
160
161
162
                    {
                        #pragma omp critical
                        add_edge(v, w, g);
                    }
                }
163
                get_box(points[i], w, box, ranges, periodic_boundary);
164
165
166
167
168
169
170
171
            }
        }
    }
};

} // namespace graph_tool

#endif // GRAPH_GEOMETRIC_HH