Open
Description
For maximum_weighted_matching the order in which edges are added to the graph makes a difference. For one order it works perfectly, but for the other the algorithm never terminates. Here is a modified version of the example to show the problem:
//=======================================================================
// Copyright (c) 2018 Yi Ji
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//
//=======================================================================
#include <iostream>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/maximum_weighted_matching.hpp>
using namespace boost;
typedef property< edge_weight_t, int, property< edge_index_t, int > >
EdgeProperty;
typedef adjacency_list< vecS, vecS, undirectedS, no_property, EdgeProperty >
my_graph;
int main(int argc, const char* argv[])
{
graph_traits< my_graph >::vertex_iterator vi, vi_end;
const int n_vertices = 10;
my_graph g(n_vertices);
// vertices can be refered by integers because my_graph use vector to store
// them
// NOT WORKING
add_edge(8, 2, EdgeProperty(10000-1002), g);
add_edge(1, 4, EdgeProperty(10000-502), g);
add_edge(9, 3, EdgeProperty(10000-1007), g);
add_edge(2, 6, EdgeProperty(10000-1), g);
add_edge(9, 7, EdgeProperty(10000-1002), g);
add_edge(0, 5, EdgeProperty(10000-1504), g);
add_edge(9, 4, EdgeProperty(10000-1006), g);
add_edge(9, 5, EdgeProperty(10000-1005), g);
add_edge(9, 6, EdgeProperty(10000-1004), g);
add_edge(0, 6, EdgeProperty(10000-1505), g);
add_edge(1, 7, EdgeProperty(10000-506), g);
add_edge(0, 3, EdgeProperty(10000-1502), g);
add_edge(0, 4, EdgeProperty(10000-1503), g);
add_edge(2, 4, EdgeProperty(10000-3), g);
add_edge(1, 6, EdgeProperty(10000-504), g);
add_edge(8, 5, EdgeProperty(10000-1004), g);
add_edge(1, 3, EdgeProperty(10000-501), g);
add_edge(4, 7, EdgeProperty(10000-4), g);
add_edge(3, 7, EdgeProperty(10000-5), g);
add_edge(3, 6, EdgeProperty(10000-3), g);
add_edge(8, 3, EdgeProperty(10000-1006), g);
add_edge(1, 5, EdgeProperty(10000-503), g);
add_edge(8, 6, EdgeProperty(10000-1003), g);
add_edge(2, 7, EdgeProperty(10000-1), g);
add_edge(0, 8, EdgeProperty(10000-2508), g);
add_edge(0, 9, EdgeProperty(10000-2509), g);
add_edge(5, 7, EdgeProperty(10000-3), g);
add_edge(1, 2, EdgeProperty(10000-505), g);
add_edge(2, 5, EdgeProperty(10000-2), g);
add_edge(8, 4, EdgeProperty(10000-1005), g);
// WORKING - same edges, different order
// add_edge(0, 3, EdgeProperty(10000-1502), g);
// add_edge(0, 4, EdgeProperty(10000-1503), g);
// add_edge(0, 5, EdgeProperty(10000-1504), g);
// add_edge(0, 6, EdgeProperty(10000-1505), g);
// add_edge(0, 8, EdgeProperty(10000-2508), g);
// add_edge(0, 9, EdgeProperty(10000-2509), g);
// add_edge(1, 2, EdgeProperty(10000-505), g);
// add_edge(1, 3, EdgeProperty(10000-501), g);
// add_edge(1, 4, EdgeProperty(10000-502), g);
// add_edge(1, 5, EdgeProperty(10000-503), g);
// add_edge(1, 6, EdgeProperty(10000-504), g);
// add_edge(1, 7, EdgeProperty(10000-506), g);
// add_edge(2, 4, EdgeProperty(10000-3), g);
// add_edge(2, 5, EdgeProperty(10000-2), g);
// add_edge(2, 6, EdgeProperty(10000-1), g);
// add_edge(2, 7, EdgeProperty(10000-1), g);
// add_edge(3, 6, EdgeProperty(10000-3), g);
// add_edge(3, 7, EdgeProperty(10000-5), g);
// add_edge(4, 7, EdgeProperty(10000-4), g);
// add_edge(5, 7, EdgeProperty(10000-3), g);
// add_edge(8, 2, EdgeProperty(10000-1002), g);
// add_edge(8, 3, EdgeProperty(10000-1006), g);
// add_edge(8, 4, EdgeProperty(10000-1005), g);
// add_edge(8, 5, EdgeProperty(10000-1004), g);
// add_edge(8, 6, EdgeProperty(10000-1003), g);
// add_edge(9, 3, EdgeProperty(10000-1007), g);
// add_edge(9, 4, EdgeProperty(10000-1006), g);
// add_edge(9, 5, EdgeProperty(10000-1005), g);
// add_edge(9, 6, EdgeProperty(10000-1004), g);
// add_edge(9, 7, EdgeProperty(10000-1002), g);
std::vector< graph_traits< my_graph >::vertex_descriptor > mate1(
n_vertices),
mate2(n_vertices);
maximum_weighted_matching(g, &mate1[0]);
std::cout << "Found a weighted matching:" << std::endl;
std::cout << "Matching size is " << matching_size(g, &mate1[0])
<< ", total weight is " << matching_weight_sum(g, &mate1[0])
<< std::endl;
std::cout << std::endl;
std::cout << "The matching is:" << std::endl;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
if (mate1[*vi] != graph_traits< my_graph >::null_vertex()
&& *vi < mate1[*vi])
std::cout << "{" << *vi << ", " << mate1[*vi] << "}" << std::endl;
std::cout << std::endl;
}