graph_random_matching.cc 3.97 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1 2 3
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006-2015 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 22 23
//
// 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"

24 25
#include "random.hh"

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
#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())
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
83
                uniform_int_distribution<> sample(0, candidates.size() - 1);
84 85 86 87 88 89 90 91 92 93
                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,
94
                     bool minimize, rng_t& rng)
95
{
96
    typedef UnityPropertyMap<int,GraphInterface::edge_t> weight_map_t;
97 98 99 100
    typedef mpl::push_back<edge_scalar_properties, weight_map_t>::type
        edge_props_t;

    if(weight.empty())
101
        weight = weight_map_t();
102 103

    run_action<>()
104 105
        (gi, std::bind(do_random_matching(), std::placeholders::_1, gi.get_vertex_index(),
                       std::placeholders::_2, std::placeholders::_3, minimize, std::ref(rng)),
106
         edge_props_t(), writable_edge_scalar_properties())(weight, match);
107 108 109 110 111 112
}

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