Conversation
|
Does the increase in runtime performance really justify the templated implementation? Can't you just branch on a sortSuitor variable at runtime? Also, the sortEdgesByWeight method is not appropriate for |
angriman
force-pushed
the
suitor-matcher
branch
2 times, most recently
from
a0d0702 to
a2ab952
Compare
I removed the templated implementation, it that was not really necessary.
I moved it in |
angriman
force-pushed
the
suitor-matcher
branch
7 times, most recently
from
2c15bad to
6d06bd7
Compare
michitux
left a comment
michitux
left a comment
There was a problem hiding this comment.
In general this looks good now, I have just a few small comments that you may implement or not.
Do you have any idea how fast sorting neighbors by id with your new function is compared to the existing sortEdges functionality? My suspicion would be that due to increased locality it may be faster in practice, in particular when multiple cores are used. If it should be faster, I would suggest to replace the existing sortEdges method by your new method.
| * @return @a edge weight to the i-th (outgoing) neighbor of @a u, or @c +inf if no such | ||
| * neighbor exists. | ||
| */ | ||
| edgeweight getIthNeighborWeight(node u, index i) const { |
There was a problem hiding this comment.
Is it intentional that this method is not added to the Python interface?
There was a problem hiding this comment.
getIthNeighbor does not have a Python interface, so we either provide a Python interface for both or for none.
include/networkit/graph/Graph.hpp
Outdated
| const auto sortAdjacencyArrays = [&](node u, std::vector<node> &adjList, | ||
| std::vector<edgeweight> &weights, | ||
| std::vector<edgeid> &edgeIds) -> void { | ||
| std::vector<index> indices(adjList.size()); |
There was a problem hiding this comment.
Would it be faster to have one indices vector per thread that is only re-allocated when a node with a larger degree is encountered? The design with the new indices vector for every call is definitely clearer, what I'm wondering though is what impact this memory allocation has on performance.
There was a problem hiding this comment.
Although the code slightly changed in the most recent version, I think time can still be safed if resize is only done if adjList.size() > indices.size(). Reasoning: resize calls erase on indices if adjList.size() < indices.size(), while iota is called anyways afterwards.
There was a problem hiding this comment.
Now resize is called only when necessary.
angriman
force-pushed
the
suitor-matcher
branch
3 times, most recently
from
fb93872 to
5e36a9e
Compare
angriman
force-pushed
the
suitor-matcher
branch
3 times, most recently
from
aa7dacf to
ce447c7
Compare
angriman
force-pushed
the
suitor-matcher
branch
2 times, most recently
from
7900784 to
6f915a7
Compare
5 participants
This PR brings the 1/2-approximation algorithm for maximum (weighted) matching by Manne and Halappanavar (New Effective Multithreaded Matching Algorithms, IPDPS 2014).
There are two versions of the algorithm, one of which only supports graphs where the adjacency lists of every vertex are sorted by edge weight in decreasing order. To this end I also added a new
sortEdgesByWeightmethod inGraph, which allows to sort the edges of a graph by edge weight in increasing or decreasing order. This method uses a new genericsortEdgesmethod inGraph, which allows to sort the edges of a graph according to a custom criterion.I am a bit hesitant to add the new sorting methods to
Graph, they are probably too specific. An alternative idea is to implement them inGraphTools.