Zoltan2
Loading...
Searching...
No Matches
Zoltan2_GreedyMWM.hpp
Go to the documentation of this file.
1// @HEADER
2// *****************************************************************************
3// Zoltan2: A package of combinatorial algorithms for scientific computing
4//
5// Copyright 2012 NTESS and the Zoltan2 contributors.
6// SPDX-License-Identifier: BSD-3-Clause
7// *****************************************************************************
8// @HEADER
9
14#ifndef ZOLTAN2_GREEDYMWM_HPP__
15#define ZOLTAN2_GREEDYMWM_HPP__
16namespace Zoltan2 {
17
19//
20// Greedy algorithm for maximum-weight matching.
21// This is an 1/2-approximation, but requires a sort.
22// Linear-time approximation algorithms should be considered
23// in the future, e.g., the Path Growing Algorithm by
24// Drake & Hogardy, and the Suitor algorithm by Manne & Halappanavar.
25// The algorithm runs in serial; the graph must be gathered to
26// the process before entry.
28
29#include <vector>
30#include <algorithm>
31
32// This struct should be local to GreedyMWM(), but compiler complains.
33template <typename vtx_t, typename wgt_t>
35 vtx_t i;
36 vtx_t j;
37 wgt_t val;
38};
39
40template <typename vtx_t, typename wgt_t>
43{
44 return (a.val > b.val); // descending order
45}
46
47
48template <typename vtx_t, typename wgt_t>
50 int *idx, // Index into compressed sparse edge list;
51 // idx[i] is index into adj of first edge for vertex i
52 vtx_t *adj, // Edge list in compressed sparse format
53 wgt_t *wgt, // weights for each edge
54 vtx_t tnVtx, // number of vertices
55 vtx_t *match // output result: vtx i matches with vtx match[i]
56)
57{
58 typedef GMWM_triplet<vtx_t, wgt_t> triplet_t;
59 vtx_t nmatch=0;
60 std::vector<triplet_t> edges(idx[tnVtx]);
61
62 // Make vector of triplets (edges)
63 size_t k=0;
64 for (int i=0; i<tnVtx; i++){
65 for (int jj=idx[i]; jj<idx[i+1]; jj++){
66 int j = adj[jj];
67 if (i<=j){ // We need each edge only once.
68 edges[k].i = i;
69 edges[k].j = j;
70 edges[k].val = wgt[k];
71 }
72 k++;
73 }
74 }
75
76 // Sort edges by weight
77 std::sort (edges.begin(), edges.end(), compare_triplets<vtx_t,wgt_t>);
78
79 // Greedy loop over sorted edges
80 // std::cout << "After sort:" << std::endl;
81 for (typename std::vector<triplet_t>::iterator it=edges.begin();
82 it!=edges.end(); ++it){
83
84 // std::cout << "edge (" << it->i << ", " << it->j << ", "
85 // << it->val << ")" << std::endl;
86
87 if ((match[it->i] == it->i) && (match[it->j] == it->j )){
88 match[it->i] = it->j;
89 match[it->j] = it->i;
90 nmatch++;
91 }
92 }
93 return nmatch;
94}
95}
96
97
98#endif
Created by mbenlioglu on Aug 31, 2020.
static bool compare_triplets(GMWM_triplet< vtx_t, wgt_t > a, GMWM_triplet< vtx_t, wgt_t > b)
vtx_t GreedyMWM(int *idx, vtx_t *adj, wgt_t *wgt, vtx_t tnVtx, vtx_t *match)