-
Notifications
You must be signed in to change notification settings - Fork 9
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Maximum weight matching algorithms #25
Maximum weight matching algorithms #25
Conversation
4777ce6
to
9e30b82
Compare
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Thank you very much, this in an impressive contribution, both in terms of code and text, highly appreciated!
benchmark/CMakeLists.txt
Outdated
benchmarkMaximumMatching.sh) | ||
|
||
koala_make_benchmark( | ||
benchmark_mv |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Well, doesn't MV solve maximum matching as well?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Renamed to MaximumWeightMatching and MaximumMatching, respectively
benchmark/CMakeLists.txt
Outdated
koala_make_benchmark( | ||
benchmark_mv | ||
benchmarkMicaliVazirani.cpp | ||
benchmarkMicaliVazirani.sh) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Please add empty line at the end
In general, please run
cpplint --linelength=100 --extensions=cpp,hpp --filter=-legal/copyright,-build/c++20,-build/include,-build/namespaces,-build/header_guard,-runtime/references,-runtime/string --recursive --exclude=./backup --exclude=./build --exclude=./input --exclude=./lib --exclude=./cpp/flow/maximum_flow/dynamic_tree/*
and fix the style errors in your files
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Fixed
static Edge reverse(const Edge& edge); | ||
static std::string edge_to_string(const Edge& e); | ||
|
||
enum Label { odd, even, free }; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Nit: ODD, EVEN, FREE + enum class instead of enum?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Postponed to refactoring
include/matching/PriorityQueues.hpp
Outdated
@@ -0,0 +1,1842 @@ | |||
#pragma once |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Just a suggestion: maybe move it to include/structures?
} | ||
auto G = Koala::DimacsGraphReader().read(path); | ||
G.indexEdges(true); | ||
Koala::MaximumWeightMatching* maximum_matching; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Please see e.g. benchmarkIndependentSet - I guess it's slightly cleaner to run run_algorithm<T>(G)
with a proper T depending on the input params. At least you'd avoid unnecessary raw pointers.
auto matching = maximum_matching->getMatching(); | ||
int weight = 0; | ||
for (auto [u, v] : matching) { | ||
std::cout << u << " " << v << std::endl; | ||
if (v != NetworKit::none) { | ||
assert(matching[v] == u); | ||
assert(G.hasEdge(u, v)); | ||
|
||
weight += static_cast<int>(G.weight(u, v)); | ||
} | ||
} | ||
std::cout << weight / 2 << std::endl; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Please extract it to a separate function
include/matching/PriorityQueues.hpp
Outdated
|
||
private: | ||
// Pointer to the queue which is correct in the root | ||
ConcatenableQueue* queue; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Can't you have just an object here instead of a pointer?
include/matching/PriorityQueues.hpp
Outdated
Node* parent; | ||
Node* children[3]; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
With parent/children we can be more lax, but please hide new/delete from the user of this structure as deep as possible,
The algorithm implementations are mostly final. The code for data structures has to probably be split into different files and cleaned up a bit. Should they be moved to the structures directory or remain in matching since most are kind of specific to the algorithms? So far the implemented algorithms for maximum weight matching are Edmonds n^4, Gabow n^3, Galil/Micali/Gabow nm*logn and Gabow n^(3/4)m logN. There's also an implementation for Micali-Vazirani maximum cardinality matching algorithm that's needed for the Gabow scaling algorithm.