1
0
Fork 0
maximum-weight-matching/cpp/run_matching.cpp

316 lines
8.5 KiB
C++

/*
* Calculate maximum weighted matching of graphs in DIMACS format.
*/
#include <cstdlib>
#include <cassert>
#include <cerrno>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <vector>
#include "mwmatching.h"
namespace { // anonymous namespace
typedef long long IntWeight;
typedef double FloatWeight;
template <typename WeightType>
using WeightedEdgeList = std::vector<mwmatching::Edge<WeightType>>;
using EdgeList = std::vector<mwmatching::VertexPair>;
/*
* Graph defined by a list of weighted edges.
* Weights are either integers or floating point numbers.
*/
struct Graph
{
bool is_int_weight;
WeightedEdgeList<IntWeight> int_edges;
WeightedEdgeList<FloatWeight> float_edges;
};
/*
* Matching defined by a list of matched edges.
* The weight of the matching is either an integer or floating point number.
*/
struct Matching
{
bool is_int_weight;
IntWeight int_weight;
FloatWeight float_weight;
EdgeList pairs;
};
/* Parse an integer edge weight. */
bool parse_int_weight(const std::string& s, long long& v)
{
const char *p = s.c_str();
char *q;
errno = 0;
v = std::strtoll(p, &q, 10);
return (q != p && q[0] == '\0' && errno == 0);
}
/* Parse a floating point edge weight. */
bool parse_float_weight(const std::string& s, double& v)
{
const char *p = s.c_str();
char *q;
errno = 0;
v = std::strtod(p, &q);
return (q != p && q[0] == '\0' && errno == 0);
}
/* Read a graph in DIMACS edge list format. */
int read_dimacs_graph(std::istream& input, Graph& graph)
{
graph.is_int_weight = true;
graph.int_edges.clear();
graph.float_edges.clear();
while (!input.eof()) {
std::string line;
std::getline(input, line);
if (!input) {
if (input.eof()) {
break;
} else {
return -1;
}
}
line.erase(0, line.find_first_not_of(" \n\r\t"));
line.erase(line.find_last_not_of(" \n\r\t") + 1);
if (line.empty()) {
// skip empty line
} else if (line[0] == 'c') {
// skip comment line
} else if (line[0] == 'p') {
// handle problem line
std::istringstream is(line);
std::string cmd, fmt;
is >> cmd >> fmt;
if (!is || cmd != "p" || fmt != "edge") {
std::cerr << "ERROR: Expected DIMACS edge format but got '"
<< line << "'" << std::endl;
return -1;
}
} else if (line[0] == 'e') {
// handle edge
std::istringstream is(line);
std::string cmd, weight;
unsigned int x, y;
IntWeight wi;
FloatWeight wf;
is >> cmd >> x >> y >> weight;
if (!is || cmd != "e" || x < 1 || y < 1) {
std::cerr << "ERROR: Expected edge but got '"
<< line << "'" << std::endl;
return -1;
}
if (graph.is_int_weight && parse_int_weight(weight, wi)) {
wf = wi;
graph.int_edges.emplace_back(x, y, wi);
} else {
if (!parse_float_weight(weight, wf)) {
std::cerr << "ERROR: Expected edge but got '"
<< line << "'" << std::endl;
return -1;
}
graph.is_int_weight = false;
}
graph.float_edges.emplace_back(x, y, wf);
} else {
std::cerr << "ERROR: Unknown line format '" << line << "'"
<< std::endl;
return -1;
}
}
if (graph.is_int_weight) {
graph.float_edges.clear();
} else {
graph.int_edges.clear();
}
return 0;
}
/* Write matching in DIMACS format. */
void write_dimacs_matching(std::ostream& f, const Matching& matching)
{
f << "s ";
if (matching.is_int_weight) {
f << matching.int_weight;
} else {
f.precision(12);
f << matching.float_weight;
}
f << std::endl;
for (auto pair : matching.pairs) {
f << "m " << pair.first << " " << pair.second << std::endl;
}
}
/* Solve a maximum-weight matching problem. */
template <typename WeightType>
EdgeList run_matching(const WeightedEdgeList<WeightType>& edges, bool maxcard)
{
if (maxcard) {
return mwmatching::maximum_weight_matching(
mwmatching::adjust_weights_for_maximum_cardinality_matching(edges));
} else {
return mwmatching::maximum_weight_matching(edges);
}
}
/* Calculate the total weight of the matched edges. */
template <typename WeightType>
WeightType matching_weight(const WeightedEdgeList<WeightType>& edges,
const EdgeList& pairs)
{
unsigned int num_vertex = 0;
for (const mwmatching::Edge<WeightType>& edge : edges) {
if (edge.vt.first >= num_vertex) {
num_vertex = edge.vt.first + 1;
}
if (edge.vt.second >= num_vertex) {
num_vertex = edge.vt.second + 1;
}
}
std::vector<mwmatching::VertexId> mate(num_vertex);
for (const mwmatching::VertexPair& pair : pairs) {
assert(mate[pair.first] == 0);
assert(mate[pair.second] == 0);
mate[pair.first] = pair.second;
mate[pair.second] = pair.first;
}
WeightType weight = 0;
for (const mwmatching::Edge<WeightType>& edge : edges) {
if (mate[edge.vt.first] == edge.vt.second) {
weight += edge.weight;
}
}
return weight;
}
void usage()
{
std::cerr
<< std::endl
<< "Calculate maximum weighted matching of a graph in DIMACS format."
<< std::endl << std::endl
<< "Usage: run_matching [--maxcard] < inputfile.edge" << std::endl
<< " or: run_matching [--maxcard] inputfile.edge" << std::endl
<< std::endl
<< " --maxcard Calculate a maximum cardinality matching"
<< std::endl
<< " inputfile.edge Input file in DIMACS edge-list format"
<< std::endl << std::endl;
}
}; // anonymous namespace
int main(int argc, const char **argv)
{
std::string input_file;
bool maxcard = false;
bool end_options = false;
for (int i = 1; i < argc; i++) {
if (!end_options && argv[i][0] == '-') {
if (std::string("--help") == argv[i]
|| std::string("-h") == argv[i]) {
usage();
return 0;
} else if (std::string("--maxcard") == argv[i]) {
maxcard = true;
} else if (std::string("--") == argv[i]) {
end_options = true;
} else {
std::cerr << "ERROR: Unknown option " << argv[i] << std::endl;
usage();
return 1;
}
} else {
if (!input_file.empty()) {
std::cerr << "ERROR: Multiple input files not supported."
<< std::endl;
usage();
return 1;
}
input_file = argv[i];
}
}
Graph graph;
if (input_file.empty()) {
if (read_dimacs_graph(std::cin, graph) != 0) {
if (!std::cin) {
std::cerr << "ERROR: Can not read from stdin ("
<< std::strerror(errno) << ")" << std::endl;
}
return 1;
}
} else {
std::ifstream f(input_file);
if (!f) {
std::cerr << "ERROR: Can not open '" << input_file << "' ("
<< std::strerror(errno) << ")" << std::endl;
return 1;
}
if (read_dimacs_graph(f, graph) != 0) {
if (!f) {
std::cerr << "ERROR: Can not read from '" << input_file
<< "' (" << std::strerror(errno) << ")" << std::endl;
}
return 1;
}
}
Matching matching;
matching.is_int_weight = graph.is_int_weight;
if (graph.is_int_weight) {
matching.pairs = run_matching(graph.int_edges, maxcard);
matching.int_weight = matching_weight(graph.int_edges,
matching.pairs);
} else {
matching.pairs = run_matching(graph.float_edges, maxcard);
matching.float_weight = matching_weight(graph.float_edges,
matching.pairs);
}
write_dimacs_matching(std::cout, matching);
return 0;
}