graph_random_matching.cc 3.83 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
// Copyright (C) 2006-2012 Tiago de Paula Peixoto <tiago@skewed.de>
2
3
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/>.

#include "graph.hh"
#include "graph_filtering.hh"
#include "graph_properties.hh"
#include "graph_selectors.hh"
#include "graph_util.hh"

22
23
#include "random.hh"

24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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
81
82
83
84
85
86
87
88
89
90
91
#include <boost/python.hpp>


using namespace std;
using namespace boost;
using namespace graph_tool;

struct do_random_matching
{
    template <class Graph, class VertexIndex, class WeightMap, class MatchMap,
              class RNG>
    void operator()(const Graph& g, VertexIndex vertex_index, WeightMap weight,
                    MatchMap match, bool minimize, RNG& rng) const
    {
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;
        typedef typename property_traits<WeightMap>::value_type wval_t;

        vector<vertex_t> vlist;
        typename graph_traits<Graph>::vertex_iterator v, v_end;
        for (tie(v, v_end) = vertices(g); v != v_end; ++v)
            vlist.push_back(*v);

        unchecked_vector_property_map<uint8_t, VertexIndex>
            matched(vertex_index, num_vertices(g));

        typedef random_permutation_iterator<typename vector<vertex_t>::iterator,
                                            RNG>
            random_vertex_iter;
        random_vertex_iter vr(vlist.begin(), vlist.end(), rng),
            vr_end(vlist.end(), vlist.end(), rng);
        for (; vr != vr_end; ++vr)
        {
            vertex_t v = *vr;
            if (matched[v])
                continue;
            wval_t min_w = minimize ? numeric_limits<wval_t>::max() :
                numeric_limits<wval_t>::min() ;
            vector<edge_t> candidates;
            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 w = target(*e, g);
                if (matched[w])
                    continue;
                if ((minimize && (weight[*e] < min_w)) ||
                    (!minimize && (weight[*e] > min_w)))
                {
                    min_w = weight[*e];
                    candidates.clear();
                }
                if (weight[*e] == min_w)
                    candidates.push_back(*e);
            }

            if (!candidates.empty())
            {
                tr1::uniform_int<> sample(0, candidates.size() - 1);
                size_t j = sample(rng);
                match[candidates[j]] = true;
                matched[v] = true;
                matched[target(candidates[j], g)] = true;
            }
        }
    }
};

void random_matching(GraphInterface& gi, boost::any weight, boost::any match,
92
                     bool minimize, rng_t& rng)
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
{
    typedef ConstantPropertyMap<int32_t,GraphInterface::edge_t> weight_map_t;
    typedef mpl::push_back<edge_scalar_properties, weight_map_t>::type
        edge_props_t;

    if(weight.empty())
        weight = weight_map_t(1);

    run_action<>()
        (gi, bind<void>(do_random_matching(), _1, gi.GetVertexIndex(),
                        _2, _3, minimize, ref(rng)),
         edge_props_t(), edge_scalar_properties())(weight, match);
}

void export_random_matching()
{
    python::def("random_matching", &random_matching);
}