filtered_graph_maximum_weighted_matching demonstrating the problem with the algorithm on filtered graphs

filtered_graph_maximum_weighted_matching.cpp

#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/maximum_weighted_matching.hpp>

using namespace boost;

typedef property<edge_weight_t, float, property<edge_index_t, uint64_t> >
        EdgeProperty;
typedef property<vertex_index_t, uint64_t>
        VertexProperty;
typedef adjacency_list<vecS, vecS, undirectedS,
        VertexProperty, EdgeProperty>
        Graph;
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef graph_traits<Graph>::edge_descriptor edge_descriptor;

struct Predicate {

    Predicate() = default;

    explicit Predicate(Graph &graph) : graph(graph) {}

    bool operator()(const vertex_descriptor &vertex_descriptor) const {
        if (get(vertex_index, graph, vertex_descriptor) != filtered_vertex) {
            return true;
        } else {
            return false;
        }
    }

    bool operator()(const edge_descriptor &edge_descriptor) const {
        if (get(vertex_index, graph, source(edge_descriptor, graph)) !=
            filtered_vertex &&
            get(vertex_index, graph, target(edge_descriptor, graph)) !=
            filtered_vertex) {
            return true;
        } else {
            return false;
        }
    }

    Graph graph;
    uint64_t filtered_vertex = 6;
};

int main() {
    Graph graph(0);
    const uint64_t l_vertices = 4;
    const uint64_t r_vertices = 4;
    const uint64_t n_vertices = l_vertices + r_vertices;
    for (uint64_t i = 0; i < n_vertices; i++) {
        add_vertex(VertexProperty{i}, graph);
    }

    const std::map<std::pair<uint64_t, uint64_t>, float> edge_weights =
            {
                    {{0, 4}, 1.98f},
                    {{0, 5}, 1.23f},
                    {{0, 6}, 1.11f},
                    {{0, 7}, 1.09f},
                    {{1, 4}, 1.08f},
                    {{1, 5}, 1.93f},
                    {{1, 6}, 1.42f},
                    {{1, 7}, 1.32f},
                    {{2, 4}, 1.19f},
                    {{2, 5}, 1.09f},
                    {{2, 6}, 1.99f},
                    {{2, 7}, 1.52f},
                    {{3, 4}, 1.27f},
                    {{3, 5}, 1.23f},
                    {{3, 6}, 1.37f},
                    {{3, 7}, 1.94f}
            };
    for (uint64_t i = 0; i < l_vertices; i++) {
        for (uint64_t j = l_vertices; j < n_vertices; j++) {
            add_edge(i,
                     j,
                     EdgeProperty{
                             edge_weights.at({i, j}) * 100.f,
                             i * l_vertices + j},
                     graph);
        }
    }

    Predicate predicate(graph);
    filtered_graph<Graph, Predicate, Predicate> fgraph(graph,
                                                       predicate,
                                                       predicate);

    write_graphviz(std::cout, fgraph,
                   make_label_writer(
                           boost::get(
                                   boost::vertex_index,
                                   fgraph)),
                   make_label_writer(
                           boost::get(
                                   boost::edge_index,
                                   fgraph)));
    std::cout << std::endl;

    std::vector<vertex_descriptor> mate(n_vertices);
    maximum_weighted_matching(fgraph, &mate[0]);

    std::cout << "Found a weighted matching:" << std::endl;
    std::cout << "Matching size is "
              << matching_size(fgraph, &mate[0])
              << ", total weight is "
              << matching_weight_sum(fgraph, &mate[0])
              << std::endl;
    std::cout << std::endl;

    std::cout << "The matching is:" << std::endl;
    graph_traits<filtered_graph<Graph, Predicate, Predicate> >::vertex_iterator
            vi, vi_end;
    for (tie(vi, vi_end) = vertices(fgraph); vi != vi_end; vi++)
        if (mate[*vi] != graph_traits<Graph>::null_vertex()
            && *vi < mate[*vi])
            std::cout << "{" << *vi << ", " << mate[*vi] << "}" << std::endl;
    std::cout << std::endl;
}