我目前正在进行一个项目，目标是将boost最大加权匹配问题与c++上运输问题的拍卖算法的实现进行比较。
关键是，如果垂直方向的数量开始变得更高，则最大加权匹配陷入无限循环，这种情况也会发生在少数垂直方向，如6个(投标人有3个垂直方向，其他项目有3个(。
此外，如果我试图重新运行应用程序，有时会发生最大加权匹配的执行一直运行到垂直数为12。
我以为问题是二分图的创建，但boost的is_bipartite函数每次都是真的，所以我不明白问题出在哪里。
#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 partn";
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 Matchingn";
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 << "nn";
}
return 0;
}
所以我花了一些(很多(时间复习和玩耍。然后我想起我以前都看过：
- 使用具有浮点边缘权重的cpp-boost maximum_weighted_maching算法的问题
如果我自己这么说，那分析就相当彻底了：(
一些复习笔记
好的，从头开始复习。
-
有很多未使用的include，很好(我肯定地评论了它们(
-
为什么您的
edge_index是float？这似乎是错误的 -
你是
duration_casting到毫秒，但仍然在做time_execution/1000——这是错误的。简化：(now() - start_t) / 1ms或
(now() - start_t) / 1.s对于浮点
-
你从使用
<random>倒退到(糟糕地(使用rand()。只是不要。你是说std::uniform_real_distribution<float>(1, 40)吗？ -
大麻烦的可能原因：
add_edge(bidder, N + item, dist(prng), g);这只设置一个属性值(生成的
[1.f, 40.)值(，但属性已定义：using EdgeProp = boost::property<boost::edge_weight_t, float, boost::property<boost::edge_index_t, float>>;你所能做的最好的事情就是不初始化边缘索引。除非使用，否则这不是问题。
-
有许多C样式的强制转换(如
float(expr)(。避免这些，因为它们可能隐藏问题 -
没有必要指定默认的顶点索引
应用一些修复和一些相关的刨花会导致：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 partn";
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 Matchingn";
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
<< "nn";
}
}
它仍然存在问题。
解决方法
请改用
brute_force_maximum_weighted_matching。它作品：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根据餐巾纸的数学计算，这个14项的箱子需要30天，15项在我的机器上运行1.31年。不是的最佳解决方案
提高精度。您使用
float。它们是精度最低的类型。用long double替换仍然只是部分时间有效。至少运气好的话，你会发现时机更明智：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您可以尝试上链接的答案中所述的多精度路线
最后，合理的方法可能使用积分权重。按比例缩放权重，例如
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 partn"; 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 Matchingn"; 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) << "nn"; } }
我肯定会走这条路：
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