Skip to content

Instantly share code, notes, and snippets.

@count0

count0/weighted_matching_bug.cpp

Created January 20, 2020 16:11
Show Gist options
  • Save count0/551867e10973d4b2dc047b8528908281 to your computer and use it in GitHub Desktop.
Save count0/551867e10973d4b2dc047b8528908281 to your computer and use it in GitHub Desktop.
Download ZIP
Segfault bug example for maximum_weighted_matching()
Raw
weighted_matching_bug.cpp
//=======================================================================
// 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, float, 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 = 77;
my_graph g(n_vertices);
// Below is the coappearance graph of characters in the novel Les
// Miserables. Frome D. E. Knuth, The Stanford GraphBase: A Platform for
// Combinatorial Computing, Addison-Wesley, Reading, MA (1993).
add_edge(1, 0, EdgeProperty(1), g);
add_edge(2, 0, EdgeProperty(1), g);
add_edge(3, 0, EdgeProperty(1), g);
add_edge(3, 2, EdgeProperty(1), g);
add_edge(4, 0, EdgeProperty(1), g);
add_edge(5, 0, EdgeProperty(1), g);
add_edge(6, 0, EdgeProperty(1), g);
add_edge(7, 0, EdgeProperty(1), g);
add_edge(8, 0, EdgeProperty(1), g);
add_edge(9, 0, EdgeProperty(1), g);
add_edge(11, 10, EdgeProperty(1), g);
add_edge(11, 3, EdgeProperty(1), g);
add_edge(11, 2, EdgeProperty(1), g);
add_edge(11, 0, EdgeProperty(1), g);
add_edge(12, 11, EdgeProperty(1), g);
add_edge(13, 11, EdgeProperty(1), g);
add_edge(14, 11, EdgeProperty(1), g);
add_edge(15, 11, EdgeProperty(1), g);
add_edge(17, 16, EdgeProperty(1), g);
add_edge(18, 16, EdgeProperty(1), g);
add_edge(18, 17, EdgeProperty(1), g);
add_edge(19, 16, EdgeProperty(1), g);
add_edge(19, 17, EdgeProperty(1), g);
add_edge(19, 18, EdgeProperty(1), g);
add_edge(20, 16, EdgeProperty(1), g);
add_edge(20, 17, EdgeProperty(1), g);
add_edge(20, 18, EdgeProperty(1), g);
add_edge(20, 19, EdgeProperty(1), g);
add_edge(21, 16, EdgeProperty(1), g);
add_edge(21, 17, EdgeProperty(1), g);
add_edge(21, 18, EdgeProperty(1), g);
add_edge(21, 19, EdgeProperty(1), g);
add_edge(21, 20, EdgeProperty(1), g);
add_edge(22, 16, EdgeProperty(1), g);
add_edge(22, 17, EdgeProperty(1), g);
add_edge(22, 18, EdgeProperty(1), g);
add_edge(22, 19, EdgeProperty(1), g);
add_edge(22, 20, EdgeProperty(1), g);
add_edge(22, 21, EdgeProperty(1), g);
add_edge(23, 16, EdgeProperty(1), g);
add_edge(23, 17, EdgeProperty(1), g);
add_edge(23, 18, EdgeProperty(1), g);
add_edge(23, 19, EdgeProperty(1), g);
add_edge(23, 20, EdgeProperty(1), g);
add_edge(23, 21, EdgeProperty(1), g);
add_edge(23, 22, EdgeProperty(1), g);
add_edge(23, 12, EdgeProperty(1), g);
add_edge(23, 11, EdgeProperty(1), g);
add_edge(24, 23, EdgeProperty(1), g);
add_edge(24, 11, EdgeProperty(1), g);
add_edge(25, 24, EdgeProperty(1), g);
add_edge(25, 23, EdgeProperty(1), g);
add_edge(25, 11, EdgeProperty(1), g);
add_edge(26, 24, EdgeProperty(1), g);
add_edge(26, 11, EdgeProperty(1), g);
add_edge(26, 16, EdgeProperty(1), g);
add_edge(26, 25, EdgeProperty(1), g);
add_edge(27, 11, EdgeProperty(1), g);
add_edge(27, 23, EdgeProperty(1), g);
add_edge(27, 25, EdgeProperty(1), g);
add_edge(27, 24, EdgeProperty(1), g);
add_edge(27, 26, EdgeProperty(1), g);
add_edge(28, 11, EdgeProperty(1), g);
add_edge(28, 27, EdgeProperty(1), g);
add_edge(29, 23, EdgeProperty(1), g);
add_edge(29, 27, EdgeProperty(1), g);
add_edge(29, 11, EdgeProperty(1), g);
add_edge(30, 23, EdgeProperty(1), g);
add_edge(31, 30, EdgeProperty(1), g);
add_edge(31, 11, EdgeProperty(1), g);
add_edge(31, 23, EdgeProperty(1), g);
add_edge(31, 27, EdgeProperty(1), g);
add_edge(32, 11, EdgeProperty(1), g);
add_edge(33, 11, EdgeProperty(1), g);
add_edge(33, 27, EdgeProperty(1), g);
add_edge(34, 11, EdgeProperty(1), g);
add_edge(34, 29, EdgeProperty(1), g);
add_edge(35, 11, EdgeProperty(1), g);
add_edge(35, 34, EdgeProperty(1), g);
add_edge(35, 29, EdgeProperty(1), g);
add_edge(36, 34, EdgeProperty(1), g);
add_edge(36, 35, EdgeProperty(1), g);
add_edge(36, 11, EdgeProperty(1), g);
add_edge(36, 29, EdgeProperty(1), g);
add_edge(37, 34, EdgeProperty(1), g);
add_edge(37, 35, EdgeProperty(1), g);
add_edge(37, 36, EdgeProperty(1), g);
add_edge(37, 11, EdgeProperty(1), g);
add_edge(37, 29, EdgeProperty(1), g);
add_edge(38, 34, EdgeProperty(1), g);
add_edge(38, 35, EdgeProperty(1), g);
add_edge(38, 36, EdgeProperty(1), g);
add_edge(38, 37, EdgeProperty(1), g);
add_edge(38, 11, EdgeProperty(1), g);
add_edge(38, 29, EdgeProperty(1), g);
add_edge(39, 25, EdgeProperty(1), g);
add_edge(40, 25, EdgeProperty(1), g);
add_edge(41, 24, EdgeProperty(1), g);
add_edge(41, 25, EdgeProperty(1), g);
add_edge(42, 41, EdgeProperty(1), g);
add_edge(42, 25, EdgeProperty(1), g);
add_edge(42, 24, EdgeProperty(1), g);
add_edge(43, 11, EdgeProperty(1), g);
add_edge(43, 26, EdgeProperty(1), g);
add_edge(43, 27, EdgeProperty(1), g);
add_edge(44, 28, EdgeProperty(1), g);
add_edge(44, 11, EdgeProperty(1), g);
add_edge(45, 28, EdgeProperty(1), g);
add_edge(47, 46, EdgeProperty(1), g);
add_edge(48, 47, EdgeProperty(1), g);
add_edge(48, 25, EdgeProperty(1), g);
add_edge(48, 27, EdgeProperty(1), g);
add_edge(48, 11, EdgeProperty(1), g);
add_edge(49, 26, EdgeProperty(1), g);
add_edge(49, 11, EdgeProperty(1), g);
add_edge(50, 49, EdgeProperty(1), g);
add_edge(50, 24, EdgeProperty(1), g);
add_edge(51, 49, EdgeProperty(1), g);
add_edge(51, 26, EdgeProperty(1), g);
add_edge(51, 11, EdgeProperty(1), g);
add_edge(52, 51, EdgeProperty(1), g);
add_edge(52, 39, EdgeProperty(1), g);
add_edge(53, 51, EdgeProperty(1), g);
add_edge(54, 51, EdgeProperty(1), g);
add_edge(54, 49, EdgeProperty(1), g);
add_edge(54, 26, EdgeProperty(1), g);
add_edge(55, 51, EdgeProperty(1), g);
add_edge(55, 49, EdgeProperty(1), g);
add_edge(55, 39, EdgeProperty(1), g);
add_edge(55, 54, EdgeProperty(1), g);
add_edge(55, 26, EdgeProperty(1), g);
add_edge(55, 11, EdgeProperty(1), g);
add_edge(55, 16, EdgeProperty(1), g);
add_edge(55, 25, EdgeProperty(1), g);
add_edge(55, 41, EdgeProperty(1), g);
add_edge(55, 48, EdgeProperty(1), g);
add_edge(56, 49, EdgeProperty(1), g);
add_edge(56, 55, EdgeProperty(1), g);
add_edge(57, 55, EdgeProperty(1), g);
add_edge(57, 41, EdgeProperty(1), g);
add_edge(57, 48, EdgeProperty(1), g);
add_edge(58, 55, EdgeProperty(1), g);
add_edge(58, 48, EdgeProperty(1), g);
add_edge(58, 27, EdgeProperty(1), g);
add_edge(58, 57, EdgeProperty(1), g);
add_edge(58, 11, EdgeProperty(1), g);
add_edge(59, 58, EdgeProperty(1), g);
add_edge(59, 55, EdgeProperty(1), g);
add_edge(59, 48, EdgeProperty(1), g);
add_edge(59, 57, EdgeProperty(1), g);
add_edge(60, 48, EdgeProperty(1), g);
add_edge(60, 58, EdgeProperty(1), g);
add_edge(60, 59, EdgeProperty(1), g);
add_edge(61, 48, EdgeProperty(1), g);
add_edge(61, 58, EdgeProperty(1), g);
add_edge(61, 60, EdgeProperty(1), g);
add_edge(61, 59, EdgeProperty(1), g);
add_edge(61, 57, EdgeProperty(1), g);
add_edge(61, 55, EdgeProperty(1), g);
add_edge(62, 55, EdgeProperty(1), g);
add_edge(62, 58, EdgeProperty(1), g);
add_edge(62, 59, EdgeProperty(1), g);
add_edge(62, 48, EdgeProperty(1), g);
add_edge(62, 57, EdgeProperty(1), g);
add_edge(62, 41, EdgeProperty(1), g);
add_edge(62, 61, EdgeProperty(1), g);
add_edge(62, 60, EdgeProperty(1), g);
add_edge(63, 59, EdgeProperty(1), g);
add_edge(63, 48, EdgeProperty(1), g);
add_edge(63, 62, EdgeProperty(1), g);
add_edge(63, 57, EdgeProperty(1), g);
add_edge(63, 58, EdgeProperty(1), g);
add_edge(63, 61, EdgeProperty(1), g);
add_edge(63, 60, EdgeProperty(1), g);
add_edge(63, 55, EdgeProperty(1), g);
add_edge(64, 55, EdgeProperty(1), g);
add_edge(64, 62, EdgeProperty(1), g);
add_edge(64, 48, EdgeProperty(1), g);
add_edge(64, 63, EdgeProperty(1), g);
add_edge(64, 58, EdgeProperty(1), g);
add_edge(64, 61, EdgeProperty(1), g);
add_edge(64, 60, EdgeProperty(1), g);
add_edge(64, 59, EdgeProperty(1), g);
add_edge(64, 57, EdgeProperty(1), g);
add_edge(64, 11, EdgeProperty(1), g);
add_edge(65, 63, EdgeProperty(1), g);
add_edge(65, 64, EdgeProperty(1), g);
add_edge(65, 48, EdgeProperty(1), g);
add_edge(65, 62, EdgeProperty(1), g);
add_edge(65, 58, EdgeProperty(1), g);
add_edge(65, 61, EdgeProperty(1), g);
add_edge(65, 60, EdgeProperty(1), g);
add_edge(65, 59, EdgeProperty(1), g);
add_edge(65, 57, EdgeProperty(1), g);
add_edge(65, 55, EdgeProperty(1), g);
add_edge(66, 64, EdgeProperty(1), g);
add_edge(66, 58, EdgeProperty(1), g);
add_edge(66, 59, EdgeProperty(1), g);
add_edge(66, 62, EdgeProperty(1), g);
add_edge(66, 65, EdgeProperty(1), g);
add_edge(66, 48, EdgeProperty(1), g);
add_edge(66, 63, EdgeProperty(1), g);
add_edge(66, 61, EdgeProperty(1), g);
add_edge(66, 60, EdgeProperty(1), g);
add_edge(67, 57, EdgeProperty(1), g);
add_edge(68, 25, EdgeProperty(1), g);
add_edge(68, 11, EdgeProperty(1), g);
add_edge(68, 24, EdgeProperty(1), g);
add_edge(68, 27, EdgeProperty(1), g);
add_edge(68, 48, EdgeProperty(1), g);
add_edge(68, 41, EdgeProperty(1), g);
add_edge(69, 25, EdgeProperty(1), g);
add_edge(69, 68, EdgeProperty(1), g);
add_edge(69, 11, EdgeProperty(1), g);
add_edge(69, 24, EdgeProperty(1), g);
add_edge(69, 27, EdgeProperty(1), g);
add_edge(69, 48, EdgeProperty(1), g);
add_edge(69, 41, EdgeProperty(1), g);
add_edge(70, 25, EdgeProperty(1), g);
add_edge(70, 69, EdgeProperty(1), g);
add_edge(70, 68, EdgeProperty(1), g);
add_edge(70, 11, EdgeProperty(1), g);
add_edge(70, 24, EdgeProperty(1), g);
add_edge(70, 27, EdgeProperty(1), g);
add_edge(70, 41, EdgeProperty(1), g);
add_edge(70, 58, EdgeProperty(1), g);
add_edge(71, 27, EdgeProperty(1), g);
add_edge(71, 69, EdgeProperty(1), g);
add_edge(71, 68, EdgeProperty(1), g);
add_edge(71, 70, EdgeProperty(1), g);
add_edge(71, 11, EdgeProperty(1), g);
add_edge(71, 48, EdgeProperty(1), g);
add_edge(71, 41, EdgeProperty(1), g);
add_edge(71, 25, EdgeProperty(1), g);
add_edge(72, 26, EdgeProperty(1), g);
add_edge(72, 27, EdgeProperty(1), g);
add_edge(72, 11, EdgeProperty(1), g);
add_edge(73, 48, EdgeProperty(1), g);
add_edge(74, 48, EdgeProperty(1), g);
add_edge(74, 73, EdgeProperty(1), g);
add_edge(75, 69, EdgeProperty(1), g);
add_edge(75, 68, EdgeProperty(1), g);
add_edge(75, 25, EdgeProperty(1), g);
add_edge(75, 48, EdgeProperty(1), g);
add_edge(75, 41, EdgeProperty(1), g);
add_edge(75, 70, EdgeProperty(1), g);
add_edge(75, 71, EdgeProperty(1), g);
add_edge(76, 64, EdgeProperty(1), g);
add_edge(76, 65, EdgeProperty(1), g);
add_edge(76, 66, EdgeProperty(1), g);
add_edge(76, 63, EdgeProperty(1), g);
add_edge(76, 62, EdgeProperty(1), g);
add_edge(76, 48, EdgeProperty(1), g);
add_edge(76, 58, EdgeProperty(1), g);
// our maximum weighted matching and result
std::vector<graph_traits<my_graph>::vertex_descriptor> mate1(n_vertices), mate2(n_vertices);
maximum_weighted_matching(g, &mate1[0]); // <- This segfaults with the above graph, due to a stack overflow.
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;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment