I'm currently working on a project with the goal to compare the boost maximum weighted matching problem with an implementation of the auction algorithm for the transportation problem on c++.
The point is that if the number of verticies start to become higher the maximum weighted matching get stuck in a infinite loop, this fact happens also with small number of verticies like 6 (3 verticies for Bidders and others 3 for Items).
Moreover if I try to rerun the application sometimes it happens that the execution of the maximum weighted matching runs until number of verticies of 12.
I though that the problem was the creation of the bipartite graph, but the is_bipartite function of boost return every time true, so I don't understand where the problem is.
#include <vector>
#include <chrono>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/maximum_weighted_matching.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/grid_graph.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/variant.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/graph/bipartite.hpp>
namespace Nodes {
struct Bidder {
int id;
int best_item = -1;
float val_first_best_item = -1.;
float val_second_best_item = -1.;
};
struct Item {
int id;
float cost = 0.;
int high_bidder = -1;
float high_bid = -1.;
};
static inline std::ostream& operator<<(std::ostream& os, Bidder const& b) {
return os << "BIDDER:" << b.id << "|best_item:" << b.best_item
<< "|best1:" << b.val_first_best_item
<< "|best2:" << b.val_second_best_item;
}
static inline std::ostream& operator<<(std::ostream& os, Item const& i) {
return os << "ITEM:" << i.id << "|cost:" << i.cost
<< "|high_bidder:" << i.high_bidder
<< "|high_bid:" << i.high_bid;
}
using VertexProp = boost::variant<Bidder, Item>;
static inline std::istream& operator>>(std::istream& is, VertexProp&) { return is; }
}
using Nodes::Bidder;
using Nodes::Item;
using Nodes::VertexProp;
struct GraphProp {
std::vector<int> bidder2item;
std::vector<int> item2bidder;
};
using EdgeProp = boost::property<boost::edge_weight_t, float, boost::property<boost::edge_index_t, float>>;
using Graph = boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, VertexProp, EdgeProp, GraphProp>;
using vertex_iterator = boost::graph_traits<Graph>::vertex_iterator;
using V = Graph::vertex_descriptor;
using E = Graph::edge_descriptor;
using VertexFilter = std::function<bool(V)>;
using EdgeFilter = std::function<bool(E)>;
using FMap = boost::filtered_graph<Graph, EdgeFilter, VertexFilter>;
Graph generateData(int N) {
Graph g;
//std::uniform_real_distribution<float> distribution(0., 20.);
for (int i = 0; i < N; ++i) boost::add_vertex(Bidder{ i }, g);
for (int i = 0; i < N; ++i) boost::add_vertex(Item{ i }, g);
GraphProp& gp = g[boost::graph_bundle];
gp.bidder2item.assign(N, -1);
gp.item2bidder.assign(N, -1);
// Every left nodes has a connection to every right nodes
for (int bidder = 0; bidder < N; ++bidder) {
for (int item = 0; item < N; ++item) {
//float value = distribution(generator);
float value = 1 + static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / (40 - 1)));
boost::add_edge(bidder, N + item, value, g);
}
}
return g;
}
void printGraph(Graph& g) {
boost::dynamic_properties dp;
dp.property("node_id", get(boost::vertex_index, g));
dp.property("label", get(boost::vertex_bundle, g));
dp.property("weight", get(boost::edge_weight, g));
write_graphviz_dp(std::cout, g, dp);
}
void maximum_weight_matching(Graph& graph, long long& time_execution, float& total_cost){
vertex_iterator vi, vi_end;
std::vector <boost::graph_traits<Graph>::vertex_descriptor> mate(boost::num_vertices(graph));
auto t_start = std::chrono::high_resolution_clock::now();
boost::maximum_weighted_matching(graph, &mate[0], boost::get(boost::vertex_index, graph));
time_execution = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - t_start).count();
total_cost = float(boost::matching_weight_sum(graph, &mate[0]));
std::cout << "The matching is:" << std::endl;
for (boost::tie(vi, vi_end) = boost::vertices(graph); vi != vi_end; ++vi)
if (mate[*vi] != boost::graph_traits< Graph>::null_vertex() && *vi < mate[*vi])
std::cout << "Bidder: " << *vi << " has item " << mate[*vi] % (boost::num_vertices(graph) / 2) << std::endl;
}
constexpr auto MIN = 3;
constexpr auto MAX = 15;
int main(int argc, const char* argv[]) {
srand((unsigned int)time(0));
for (int n_bidders_items = MIN; n_bidders_items <= MAX; ++n_bidders_items) {
std::cout << "Generation of a Bipartite Graph with " << n_bidders_items << " per part\n";
long long time_execution_mwm;
float total_cost_mwm = 0.;
Graph graph = generateData(n_bidders_items);
printGraph(graph);
//MAXIMUM WEIGHTED MATCHING
std::cout << "Execution of Maximum Weighted Matching\n";
maximum_weight_matching(graph, time_execution_mwm, total_cost_mwm);
std::cout << "Execution time of Maximum Weight Matching: " << float(time_execution_mwm) / 1000 << " milliseconds, with total cost: " << total_cost_mwm << "\n\n";
}
return 0;
}
So - I spent some (a lot of) time to review and play around. Then I remembered I'd seen it all before:
If I say so myself, that analysis is pretty thorough :)
Okay reviewing from the top.
there's a lot of unused includes, fine (I commented them out to be sure)
why is your edge_index a float? That seems wrong
you're duration_casting to milliseconds, but then still doing time_execution/1000 - that's wrong. Simplify:
(now() - start_t) / 1ms
or
(now() - start_t) / 1.s
for floating point
You regressed from using <random> to (badly) using rand(). Just don't. Did you mean std::uniform_real_distribution<float>(1, 40)?
The likely cause of big trouble:
add_edge(bidder, N + item, dist(prng), g);
This only sets one property value (the generated [1.f, 40.) value) but the properties are defined:
using EdgeProp = boost::property<boost::edge_weight_t, float,
boost::property<boost::edge_index_t, float>>;
The best you can hope this does is leave the edge index uninitialized. That's not a problem unless it's used.
there's a number of C-style casts (like float(expr)). Avoid these as they might hide problems
there's no need to specify the default vertex index
Applying some of the fixes, and some related shavings results in: https://godbolt.org/z/4fjvhEr1Y
#undef NDEBUG
//#include <boo/lexical_cast.hpp>
//#include <boost/graph/graph_utility.hpp>
//#include <boost/graph/grid_graph.hpp>
//#include <boost/property_map/function_property_map.hpp>
//#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bipartite.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/maximum_weighted_matching.hpp>
#include <boost/graph/properties.hpp>
#include <boost/variant.hpp>
#include <chrono>
using namespace std::chrono_literals;
static auto now = std::chrono::high_resolution_clock::now;
using duration = std::chrono::high_resolution_clock::duration;
#include <random>
static std::mt19937 prng{std::random_device{}()}; // seeded as well
namespace Nodes {
struct Bidder {
int id;
int best_item = -1;
float val_first_best_item = -1.;
float val_second_best_item = -1.;
};
struct Item {
int id;
float cost = 0.;
int high_bidder = -1;
float high_bid = -1.;
};
static inline std::ostream& operator<<(std::ostream& os, Bidder const& b) {
return os << "BIDDER:" << b.id << "|best_item:" << b.best_item
<< "|best1:" << b.val_first_best_item
<< "|best2:" << b.val_second_best_item;
}
static inline std::ostream& operator<<(std::ostream& os, Item const& i) {
return os << "ITEM:" << i.id << "|cost:" << i.cost
<< "|high_bidder:" << i.high_bidder
<< "|high_bid:" << i.high_bid;
}
using VertexProp = boost::variant<Bidder, Item>;
static inline std::istream& operator>>(std::istream& is, VertexProp&) {
return is;
}
} // namespace Nodes
using Nodes::Bidder;
using Nodes::Item;
using Nodes::VertexProp;
struct GraphProp {
std::vector<int> bidder2item;
std::vector<int> item2bidder;
};
using EdgeProp = boost::property< //
boost::edge_weight_t, float
//, boost::property<boost::edge_index_t, float>
>;
using Graph = boost::adjacency_list< //
boost::listS, boost::vecS, boost::undirectedS, VertexProp, EdgeProp,
GraphProp>;
using vertex_iterator = Graph::vertex_iterator;
using V = Graph::vertex_descriptor;
using E = Graph::edge_descriptor;
using VertexFilter = std::function<bool(V)>;
using EdgeFilter = std::function<bool(E)>;
using FMap = boost::filtered_graph<Graph, EdgeFilter, VertexFilter>;
Graph generateData(int N) {
Graph g;
for (int i = 0; i < N; ++i) add_vertex(Bidder{ i }, g);
for (int i = 0; i < N; ++i) add_vertex(Item{ i }, g);
GraphProp& gp = g[boost::graph_bundle];
gp.bidder2item.assign(N, -1);
gp.item2bidder.assign(N, -1);
std::uniform_real_distribution<float> dist(1, 40);
// Every left nodes has a connection to every right nodes
for (int bidder = 0; bidder < N; ++bidder)
for (int item = 0; item < N; ++item)
add_edge(bidder, N + item, dist(prng), g);
return g;
}
void printGraph(Graph& g) {
boost::dynamic_properties dp;
dp.property("node_id", get(boost::vertex_index, g));
dp.property("label", get(boost::vertex_bundle, g));
dp.property("weight", get(boost::edge_weight, g));
write_graphviz_dp(std::cout, g, dp);
}
float perform_matching(Graph const& graph, duration& elapsed) {
auto const N = num_vertices(graph);
std::vector<V> mate(N);
auto t_start = now();
maximum_weighted_matching(graph, &mate[0]);
elapsed = now() - t_start;
float cost = matching_weight_sum(graph, &mate[0]);
std::cout << "The matching is: ";
for (V v : boost::make_iterator_range(vertices(graph)))
if (mate[v] != Graph::null_vertex() && v < mate[v])
std::cout << "(" << v << "," << (mate[v] - (N / 2)) << ")";
// std::cout << "Bidder: " << v << " has item " << mate[v] % (N / 2) <<
// "\n";
std::cout << "\n";
return cost;
}
struct fmt {
duration const& _d;
friend std::ostream& operator<<(std::ostream& os, fmt f) {
if (f._d >=1min) return os << (f._d/1min) << "min " << (f._d % 1min) / 1s << "s";
else if (f._d >= 1s) return os << (f._d/1.0s) << "s";
else if (f._d >= 1ms) return os << (f._d/1.0ms) << "ms";
else return os << (f._d/1.0us) << "μs";
}
};
int main() {
for (unsigned n = 3; n <= 15; ++n) {
std::cout << "Generation of a Bipartite Graph with " << n
<< " per part\n";
Graph graph = generateData(n);
assert(num_vertices(graph) == 2 * n);
assert(num_edges(graph) == n*n);
//printGraph(graph);
//MAXIMUM WEIGHTED MATCHING
std::cout << "Execution of Maximum Weighted Matching\n";
duration elapsed;
float total_cost_mwm = perform_matching(graph, elapsed);
std::cout << "Execution time of Maximum Weight Matching: " << std::fixed
<< fmt{elapsed} << ", with total cost: " << total_cost_mwm
<< "\n\n";
}
}
It still has the problem.
Use brute_force_maximum_weighted_matching instead. It ... works:
Generation of a Bipartite Graph with 3 per part
Execution of Maximum Weighted Matching
The matching is: (0,1)(1,2)(2,0)
Execution time of Maximum Weight Matching: 10.615000μs, with total cost: 89.486351
Generation of a Bipartite Graph with 4 per part
Execution of Maximum Weighted Matching
The matching is: (0,3)(1,2)(2,0)(3,1)
Execution time of Maximum Weight Matching: 58.851000μs, with total cost: 119.909248
Generation of a Bipartite Graph with 5 per part
Execution of Maximum Weighted Matching
The matching is: (0,0)(1,1)(2,4)(3,2)(4,3)
Execution time of Maximum Weight Matching: 437.944000μs, with total cost: 159.292282
Generation of a Bipartite Graph with 6 per part
Execution of Maximum Weighted Matching
The matching is: (0,1)(1,4)(2,0)(3,5)(4,3)(5,2)
Execution time of Maximum Weight Matching: 3.557644ms, with total cost: 153.375183
Generation of a Bipartite Graph with 7 per part
Execution of Maximum Weighted Matching
The matching is: (0,6)(1,1)(2,2)(3,3)(4,0)(5,5)(6,4)
Execution time of Maximum Weight Matching: 18.509977ms, with total cost: 242.493790
Generation of a Bipartite Graph with 8 per part
Execution of Maximum Weighted Matching
The matching is: (0,1)(1,5)(2,0)(3,7)(4,3)(5,2)(6,6)(7,4)
Execution time of Maximum Weight Matching: 192.351818ms, with total cost: 270.717896
Generation of a Bipartite Graph with 9 per part
Execution of Maximum Weighted Matching
The matching is: (0,4)(1,2)(2,5)(3,8)(4,1)(5,3)(6,6)(7,7)(8,0)
Execution time of Maximum Weight Matching: 2.554311s, with total cost: 303.273987
Generation of a Bipartite Graph with 10 per part
Execution of Maximum Weighted Matching
The matching is: (0,9)(1,0)(2,6)(3,2)(4,1)(5,7)(6,4)(7,5)(8,8)(9,3)
Execution time of Maximum Weight Matching: 38.104204s, with total cost: 328.234894
Generation of a Bipartite Graph with 11 per part
Execution of Maximum Weighted Matching
The matching is: (0,5)(1,9)(2,0)(3,10)(4,4)(5,7)(6,3)(7,2)(8,6)(9,8)(10,1)
Execution time of Maximum Weight Matching: 10min 32s, with total cost: 364.142242
Generation of a Bipartite Graph with 12 per part
Execution of Maximum Weighted Matching
^C
Using some napkin math, the 14-item case will take 30 days, 15 would run 1.31 years on my machine. Not the best solution
Up the precision. You use float. They're the type with the least possible precision. Replacing with long double still only works some of the time. At least with some luck you'll see that the timing is saner:
Generation of a Bipartite Graph with 13 per part
Execution of Maximum Weighted Matching
The matching is: (0,1)(1,11)(2,7)(3,0)(4,2)(5,10)(6,12)(7,5)(8,4)(9,9)(10,8)(11,3)(12,6)
Execution time of Maximum Weight Matching: 518.419000μs, with total cost: 478.816739
You can try the multiprecision route as described in the answer linked above
Finally, the sane approach is likely to use integral weights. Scaling the weights by, say 10'000: https://godbolt.org/z/7ETs4rK9a
//#include <boo/lexical_cast.hpp>
//#include <boost/graph/graph_utility.hpp>
//#include <boost/graph/grid_graph.hpp>
//#include <boost/property_map/function_property_map.hpp>
//#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bipartite.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/maximum_weighted_matching.hpp>
#include <boost/graph/properties.hpp>
#include <boost/variant.hpp>
#include <chrono>
using namespace std::chrono_literals;
static auto now = std::chrono::high_resolution_clock::now;
using duration = std::chrono::high_resolution_clock::duration;
#include <random>
static std::mt19937 prng{std::random_device{}()}; // seeded as well
namespace Nodes {
using Weight = int64_t;
struct Bidder {
int id;
int best_item = -1;
Weight val_first_best_item = -1;
Weight val_second_best_item = -1;
};
struct Item {
int id;
Weight cost = 0;
int high_bidder = -1;
Weight high_bid = -1;
};
static inline std::ostream& operator<<(std::ostream& os, Bidder const& b) {
return os << "BIDDER:" << b.id << "|best_item:" << b.best_item
<< "|best1:" << b.val_first_best_item
<< "|best2:" << b.val_second_best_item;
}
static inline std::ostream& operator<<(std::ostream& os, Item const& i) {
return os << "ITEM:" << i.id << "|cost:" << i.cost
<< "|high_bidder:" << i.high_bidder
<< "|high_bid:" << i.high_bid;
}
using VertexProp = boost::variant<Bidder, Item>;
static inline std::istream& operator>>(std::istream& is, VertexProp&) {
return is;
}
} // namespace Nodes
using Nodes::Weight;
using Nodes::Bidder;
using Nodes::Item;
using Nodes::VertexProp;
struct GraphProp {
std::vector<int> bidder2item;
std::vector<int> item2bidder;
};
using EdgeProp = boost::property< //
boost::edge_weight_t, Weight
//, boost::property<boost::edge_index_t, Weight>
>;
using Graph = boost::adjacency_list< //
boost::listS, boost::vecS, boost::undirectedS, VertexProp, EdgeProp,
GraphProp>;
using vertex_iterator = Graph::vertex_iterator;
using V = Graph::vertex_descriptor;
using E = Graph::edge_descriptor;
using VertexFilter = std::function<bool(V)>;
using EdgeFilter = std::function<bool(E)>;
using FMap = boost::filtered_graph<Graph, EdgeFilter, VertexFilter>;
Graph generateData(int N) {
Graph g;
for (int i = 0; i < N; ++i) add_vertex(Bidder{ i }, g);
for (int i = 0; i < N; ++i) add_vertex(Item{ i }, g);
GraphProp& gp = g[boost::graph_bundle];
gp.bidder2item.assign(N, -1);
gp.item2bidder.assign(N, -1);
std::uniform_int_distribution<int64_t> dist(10'000, 400'000);
// Every left nodes has a connection to every right nodes
for (int bidder = 0; bidder < N; ++bidder)
for (int item = 0; item < N; ++item)
add_edge(bidder, N + item, dist(prng), g);
return g;
}
void printGraph(Graph& g) {
boost::dynamic_properties dp;
dp.property("node_id", get(boost::vertex_index, g));
dp.property("label", get(boost::vertex_bundle, g));
dp.property("weight", get(boost::edge_weight, g));
write_graphviz_dp(std::cout, g, dp);
}
Weight perform_matching(Graph const& graph, duration& elapsed) {
auto const N = num_vertices(graph);
std::vector<V> mate(N);
auto t_start = now();
maximum_weighted_matching(graph, &mate[0]);
//brute_force_maximum_weighted_matching(graph, &mate[0]);
elapsed = now() - t_start;
Weight cost = matching_weight_sum(graph, &mate[0]);
std::cout << "The matching is: ";
for (V v : boost::make_iterator_range(vertices(graph)))
if (mate[v] != Graph::null_vertex() && v < mate[v])
std::cout << "(" << v << "," << (mate[v] - (N / 2)) << ")";
// std::cout << "Bidder: " << v << " has item " << mate[v] % (N / 2) <<
// "\n";
std::cout << "\n";
return cost;
}
struct fmt {
duration const& _d;
friend std::ostream& operator<<(std::ostream& os, fmt f) {
if (f._d >=1min) return os << (f._d/1min) << "min " << (f._d % 1min) / 1s << "s";
else if (f._d >= 1s) return os << (f._d/1.0s) << "s";
else if (f._d >= 1ms) return os << (f._d/1.0ms) << "ms";
else return os << (f._d/1.0us) << "μs";
}
};
int main() {
for (unsigned n = 3; n <= 25; ++n) {
std::cout << "Generation of a Bipartite Graph with " << n
<< " per part\n";
Graph graph = generateData(n);
assert(num_vertices(graph) == 2 * n);
assert(num_edges(graph) == n*n);
//printGraph(graph);
//MAXIMUM WEIGHTED MATCHING
std::cout << "Execution of Maximum Weighted Matching\n";
duration elapsed;
Weight total_cost_mwm = perform_matching(graph, elapsed);
std::cout << "Execution time of Maximum Weight Matching: " << std::fixed
<< fmt{elapsed} << ", with total cost: " << (total_cost_mwm/10'000.0)
<< "\n\n";
}
}
I would definitely go this route:
Generation of a Bipartite Graph with 15 per part
Execution of Maximum Weighted Matching
The matching is: (0,0)(1,11)(2,5)(3,10)(4,12)(5,8)(6,1)(7,6)(8,7)(9,4)(10,3)(11,2)(12,9)(13,14)(14,13)
Execution time of Maximum Weight Matching: 363.954000μs, with total cost: 544.213200
// ...
Generation of a Bipartite Graph with 115 per part
Execution of Maximum Weighted Matching
The matching is: (0,114)(1,58)(2,55)(3,32)(4,67)(5,76)(6,41)(7,93)(8,48)(9,9)(10,11)(11,38)(12,54)(13,111)(14,90)(15,102)(16,1)(17,113)(18,17)(19,0)(20,86)(21,80)(22,60)(23,75)(24,10)(25,101)(26,61)(27,59)(28,68)(29,100)(30,84)(31,33)(32,5)(33,72)(34,106)(35,98)(36,79)(37,12)(38,3)(39,44)(40,42)(41,78)(42,34)(43,31)(44,28)(45,56)(46,19)(47,25)(48,49)(49,4)(50,70)(51,92)(52,43)(53,45)(54,23)(55,21)(56,103)(57,96)(58,77)(59,81)(60,24)(61,29)(62,66)(63,73)(64,63)(65,16)(66,6)(67,13)(68,51)(69,39)(70,18)(71,82)(72,36)(73,22)(74,53)(75,35)(76,108)(77,105)(78,83)(79,40)(80,14)(81,37)(82,65)(83,89)(84,110)(85,91)(86,15)(87,87)(88,74)(89,95)(90,71)(91,69)(92,112)(93,20)(94,64)(95,99)(96,8)(97,47)(98,88)(99,2)(100,104)(101,94)(102,27)(103,85)(104,57)(105,7)(106,97)(107,46)(108,109)(109,50)(110,107)(111,26)(112,52)(113,30)(114,62)
Execution time of Maximum Weight Matching: 115.030287ms, with total cost: 4534.587800
Generation of a Bipartite Graph with 116 per part
Execution of Maximum Weighted Matching
The matching is: (0,5)(1,104)(2,29)(3,61)(4,90)(5,102)(6,85)(7,44)(8,21)(9,48)(10,94)(11,1)(12,9)(13,80)(14,56)(15,2)(16,60)(17,37)(18,73)(19,15)(20,105)(21,4)(22,28)(23,78)(24,114)(25,106)(26,27)(27,10)(28,26)(29,6)(30,24)(31,50)(32,82)(33,23)(34,93)(35,30)(36,38)(37,63)(38,57)(39,41)(40,16)(41,79)(42,112)(43,7)(44,46)(45,17)(46,40)(47,33)(48,8)(49,64)(50,68)(51,76)(52,96)(53,19)(54,115)(55,75)(56,13)(57,70)(58,62)(59,98)(60,99)(61,65)(62,69)(63,43)(64,35)(65,59)(66,45)(67,100)(68,109)(69,87)(70,86)(71,72)(72,108)(73,74)(74,101)(75,22)(76,11)(77,3)(78,110)(79,32)(80,89)(81,81)(82,95)(83,67)(84,54)(85,20)(86,51)(87,52)(88,66)(89,25)(90,77)(91,91)(92,47)(93,39)(94,34)(95,71)(96,49)(97,42)(98,107)(99,0)(100,31)(101,83)(102,36)(103,97)(104,18)(105,58)(106,14)(107,55)(108,103)(109,92)(110,88)(111,12)(112,111)(113,113)(114,53)(115,84)
Execution time of Maximum Weight Matching: 114.140185ms, with total cost: 4578.718400
// ...
Generation of a Bipartite Graph with 247 per part
Execution of Maximum Weighted Matching
The matching is: (0,24)(1,175)(2,102)(3,232)(4,5)(5,6)(6,229)(7,27)(8,38)(9,169)(10,228)(11,149)(12,11)(13,2)(14,192)(15,129)(16,82)(17,190)(18,113)(19,136)(20,174)(21,128)(22,161)(23,196)(24,103)(25,202)(26,23)(27,231)(28,167)(29,59)(30,22)(31,235)(32,110)(33,78)(34,171)(35,195)(36,87)(37,9)(38,131)(39,52)(40,189)(41,49)(42,108)(43,218)(44,181)(45,133)(46,95)(47,182)(48,183)(49,166)(50,241)(51,21)(52,172)(53,222)(54,42)(55,46)(56,225)(57,25)(58,176)(59,144)(60,245)(61,109)(62,73)(63,186)(64,75)(65,213)(66,104)(67,74)(68,69)(69,20)(70,127)(71,41)(72,76)(73,72)(74,97)(75,168)(76,36)(77,83)(78,163)(79,105)(80,224)(81,70)(82,178)(83,141)(84,180)(85,135)(86,32)(87,111)(88,132)(89,234)(90,28)(91,10)(92,185)(93,242)(94,43)(95,210)(96,12)(97,237)(98,60)(99,199)(100,62)(101,123)(102,48)(103,1)(104,243)(105,15)(106,134)(107,211)(108,98)(109,188)(110,0)(111,240)(112,191)(113,106)(114,67)(115,159)(116,30)(117,91)(118,233)(119,230)(120,125)(121,147)(122,164)(123,158)(124,236)(125,184)(126,153)(127,122)(128,146)(129,142)(130,63)(131,143)(132,68)(133,14)(134,170)(135,17)(136,112)(137,145)(138,120)(139,200)(140,215)(141,156)(142,177)(143,162)(144,47)(145,7)(146,34)(147,50)(148,80)(149,107)(150,4)(151,179)(152,150)(153,66)(154,71)(155,8)(156,207)(157,61)(158,205)(159,58)(160,124)(161,116)(162,101)(163,165)(164,88)(165,238)(166,64)(167,100)(168,157)(169,118)(170,84)(171,99)(172,140)(173,18)(174,217)(175,89)(176,138)(177,152)(178,51)(179,197)(180,198)(181,55)(182,204)(183,173)(184,37)(185,92)(186,151)(187,137)(188,13)(189,220)(190,148)(191,33)(192,221)(193,160)(194,29)(195,65)(196,3)(197,114)(198,53)(199,203)(200,212)(201,201)(202,154)(203,130)(204,214)(205,54)(206,219)(207,244)(208,45)(209,77)(210,193)(211,209)(212,39)(213,40)(214,206)(215,35)(216,119)(217,16)(218,246)(219,56)(220,226)(221,19)(222,94)(223,57)(224,81)(225,115)(226,85)(227,223)(228,139)(229,26)(230,90)(231,155)(232,93)(233,86)(234,121)(235,194)(236,96)(237,126)(238,187)(239,117)(240,239)(241,208)(242,44)(243,227)(244,216)(245,31)(246,79)
Execution time of Maximum Weight Matching: 1.933262s, with total cost: 9819.795300
Generation of a Bipartite Graph with 248 per part
Execution of Maximum Weighted Matching
The matching is: (0,238)(1,217)(2,140)(3,200)(4,193)(5,241)(6,134)(7,19)(8,81)(9,87)(10,118)(11,133)(12,51)(13,41)(14,63)(15,1)(16,5)(17,94)(18,110)(19,103)(20,24)(21,40)(22,155)(23,86)(24,33)(25,239)(26,128)(27,49)(28,104)(29,203)(30,165)(31,15)(32,37)(33,16)(34,84)(35,98)(36,189)(37,108)(38,219)(39,106)(40,150)(41,137)(42,244)(43,183)(44,29)(45,237)(46,213)(47,236)(48,222)(49,60)(50,162)(51,176)(52,114)(53,170)(54,44)(55,6)(56,62)(57,178)(58,220)(59,234)(60,173)(61,221)(62,231)(63,9)(64,168)(65,56)(66,233)(67,172)(68,209)(69,67)(70,167)(71,50)(72,93)(73,169)(74,210)(75,158)(76,75)(77,214)(78,247)(79,182)(80,243)(81,147)(82,188)(83,90)(84,0)(85,55)(86,61)(87,139)(88,21)(89,195)(90,192)(91,224)(92,65)(93,113)(94,196)(95,18)(96,38)(97,199)(98,131)(99,31)(100,57)(101,17)(102,70)(103,187)(104,54)(105,160)(106,130)(107,142)(108,149)(109,76)(110,43)(111,227)(112,73)(113,151)(114,232)(115,216)(116,157)(117,45)(118,135)(119,215)(120,226)(121,132)(122,208)(123,64)(124,223)(125,159)(126,10)(127,171)(128,99)(129,11)(130,127)(131,163)(132,156)(133,48)(134,23)(135,74)(136,27)(137,26)(138,115)(139,78)(140,230)(141,181)(142,198)(143,180)(144,32)(145,72)(146,22)(147,242)(148,36)(149,212)(150,7)(151,191)(152,101)(153,197)(154,143)(155,2)(156,194)(157,59)(158,119)(159,68)(160,225)(161,117)(162,96)(163,34)(164,124)(165,66)(166,14)(167,97)(168,205)(169,235)(170,3)(171,83)(172,89)(173,102)(174,8)(175,53)(176,107)(177,207)(178,12)(179,25)(180,125)(181,146)(182,112)(183,211)(184,164)(185,161)(186,218)(187,46)(188,47)(189,204)(190,77)(191,174)(192,179)(193,120)(194,190)(195,126)(196,100)(197,154)(198,145)(199,138)(200,95)(201,30)(202,185)(203,82)(204,175)(205,69)(206,28)(207,92)(208,229)(209,88)(210,80)(211,4)(212,105)(213,20)(214,52)(215,109)(216,245)(217,35)(218,58)(219,71)(220,136)(221,246)(222,177)(223,148)(224,144)(225,116)(226,91)(227,79)(228,13)(229,201)(230,166)(231,121)(232,122)(233,129)(234,39)(235,228)(236,240)(237,123)(238,141)(239,42)(240,184)(241,153)(242,111)(243,152)(244,206)(245,186)(246,85)(247,202)
Execution time of Maximum Weight Matching: 2.077972s, with total cost: 9853.318400
Generation of a Bipartite Graph with 249 per part
Execution of Maximum Weighted Matching
The matching is: (0,3)(1,137)(2,86)(3,11)(4,203)(5,132)(6,154)(7,69)(8,163)(9,81)(10,204)(11,114)(12,234)(13,202)(14,147)(15,85)(16,215)(17,45)(18,126)(19,190)(20,5)(21,54)(22,88)(23,151)(24,64)(25,68)(26,87)(27,248)(28,246)(29,123)(30,107)(31,233)(32,12)(33,108)(34,189)(35,175)(36,117)(37,143)(38,70)(39,221)(40,232)(41,56)(42,113)(43,26)(44,236)(45,152)(46,103)(47,244)(48,62)(49,167)(50,208)(51,125)(52,22)(53,160)(54,23)(55,130)(56,32)(57,218)(58,197)(59,205)(60,7)(61,165)(62,33)(63,229)(64,187)(65,185)(66,6)(67,37)(68,172)(69,127)(70,63)(71,46)(72,164)(73,96)(74,95)(75,50)(76,66)(77,166)(78,72)(79,38)(80,61)(81,79)(82,142)(83,227)(84,237)(85,59)(86,24)(87,134)(88,247)(89,27)(90,173)(91,8)(92,245)(93,104)(94,183)(95,240)(96,157)(97,105)(98,111)(99,146)(100,75)(101,133)(102,177)(103,220)(104,217)(105,211)(106,110)(107,17)(108,128)(109,124)(110,223)(111,25)(112,120)(113,14)(114,209)(115,116)(116,176)(117,115)(118,102)(119,119)(120,76)(121,199)(122,52)(123,153)(124,89)(125,10)(126,224)(127,80)(128,222)(129,9)(130,77)(131,179)(132,195)(133,136)(134,16)(135,228)(136,140)(137,231)(138,71)(139,216)(140,65)(141,138)(142,83)(143,225)(144,21)(145,100)(146,212)(147,121)(148,43)(149,55)(150,159)(151,206)(152,129)(153,155)(154,30)(155,29)(156,40)(157,188)(158,139)(159,58)(160,60)(161,182)(162,57)(163,122)(164,49)(165,67)(166,192)(167,158)(168,149)(169,15)(170,230)(171,13)(172,194)(173,91)(174,2)(175,170)(176,39)(177,28)(178,241)(179,207)(180,97)(181,101)(182,19)(183,144)(184,201)(185,1)(186,243)(187,36)(188,168)(189,161)(190,84)(191,181)(192,150)(193,141)(194,171)(195,35)(196,242)(197,112)(198,106)(199,235)(200,78)(201,4)(202,44)(203,98)(204,148)(205,186)(206,191)(207,74)(208,193)(209,239)(210,178)(211,145)(212,51)(213,156)(214,169)(215,0)(216,93)(217,219)(218,174)(219,20)(220,198)(221,90)(222,109)(223,196)(224,31)(225,118)(226,214)(227,82)(228,53)(229,92)(230,131)(231,180)(232,99)(233,41)(234,42)(235,94)(236,47)(237,135)(238,200)(239,34)(240,73)(241,162)(242,18)(243,184)(244,226)(245,238)(246,210)(247,213)(248,48)
Execution time of Maximum Weight Matching: 2.155353s, with total cost: 9897.323400
Generation of a Bipartite Graph with 250 per part
Execution of Maximum Weighted Matching
The matching is: (0,70)(1,137)(2,240)(3,35)(4,33)(5,235)(6,242)(7,130)(8,217)(9,215)(10,178)(11,16)(12,3)(13,100)(14,165)(15,197)(16,186)(17,39)(18,239)(19,103)(20,169)(21,129)(22,71)(23,86)(24,198)(25,154)(26,73)(27,206)(28,227)(29,145)(30,61)(31,248)(32,191)(33,171)(34,222)(35,128)(36,185)(37,89)(38,234)(39,168)(40,78)(41,115)(42,193)(43,247)(44,221)(45,162)(46,172)(47,7)(48,30)(49,177)(50,127)(51,184)(52,144)(53,8)(54,80)(55,60)(56,113)(57,243)(58,114)(59,146)(60,229)(61,133)(62,77)(63,118)(64,237)(65,69)(66,21)(67,45)(68,150)(69,25)(70,207)(71,32)(72,40)(73,102)(74,15)(75,66)(76,135)(77,226)(78,43)(79,194)(80,38)(81,12)(82,220)(83,151)(84,182)(85,219)(86,5)(87,0)(88,158)(89,34)(90,50)(91,245)(92,47)(93,200)(94,241)(95,112)(96,203)(97,51)(98,244)(99,131)(100,209)(101,37)(102,54)(103,101)(104,161)(105,46)(106,42)(107,120)(108,218)(109,2)(110,109)(111,166)(112,20)(113,97)(114,67)(115,213)(116,62)(117,212)(118,134)(119,249)(120,159)(121,132)(122,10)(123,68)(124,164)(125,28)(126,18)(127,110)(128,111)(129,160)(130,189)(131,149)(132,76)(133,116)(134,156)(135,142)(136,56)(137,11)(138,64)(139,53)(140,48)(141,148)(142,49)(143,19)(144,208)(145,75)(146,152)(147,119)(148,63)(149,93)(150,29)(151,58)(152,31)(153,214)(154,44)(155,91)(156,153)(157,24)(158,179)(159,108)(160,55)(161,1)(162,236)(163,124)(164,125)(165,188)(166,74)(167,90)(168,141)(169,82)(170,140)(171,96)(172,195)(173,95)(174,180)(175,126)(176,173)(177,4)(178,59)(179,143)(180,22)(181,123)(182,17)(183,176)(184,202)(185,216)(186,121)(187,122)(188,196)(189,27)(190,92)(191,187)(192,138)(193,98)(194,228)(195,23)(196,9)(197,6)(198,205)(199,117)(200,157)(201,36)(202,65)(203,139)(204,85)(205,87)(206,231)(207,147)(208,192)(209,14)(210,88)(211,246)(212,72)(213,26)(214,210)(215,233)(216,52)(217,204)(218,84)(219,181)(220,174)(221,83)(222,163)(223,238)(224,57)(225,79)(226,81)(227,223)(228,225)(229,167)(230,175)(231,230)(232,155)(233,199)(234,201)(235,105)(236,211)(237,106)(238,170)(239,136)(240,107)(241,190)(242,13)(243,183)(244,94)(245,104)(246,99)(247,224)(248,41)(249,232)
Execution time of Maximum Weight Matching: 2.147109s, with total cost: 9933.882100