Zoltan2
Loading...
Searching...
No Matches
Zoltan2_GreedyMWM.hpp
Go to the documentation of this file.
1// @HEADER
2//
3// ***********************************************************************
4//
5// Zoltan2: A package of combinatorial algorithms for scientific computing
6// Copyright 2012 Sandia Corporation
7//
8// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9// the U.S. Government retains certain rights in this software.
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//
18// 2. Redistributions in binary form must reproduce the above copyright
19// notice, this list of conditions and the following disclaimer in the
20// documentation and/or other materials provided with the distribution.
21//
22// 3. Neither the name of the Corporation nor the names of the
23// contributors may be used to endorse or promote products derived from
24// this software without specific prior written permission.
25//
26// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37//
38// Questions? Contact Karen Devine (kddevin@sandia.gov)
39// Erik Boman (egboman@sandia.gov)
40// Siva Rajamanickam (srajama@sandia.gov)
41//
42// ***********************************************************************
43//
44// @HEADER
45
50#ifndef ZOLTAN2_GREEDYMWM_HPP__
51#define ZOLTAN2_GREEDYMWM_HPP__
52namespace Zoltan2 {
53
55//
56// Greedy algorithm for maximum-weight matching.
57// This is an 1/2-approximation, but requires a sort.
58// Linear-time approximation algorithms should be considered
59// in the future, e.g., the Path Growing Algorithm by
60// Drake & Hogardy, and the Suitor algorithm by Manne & Halappanavar.
61// The algorithm runs in serial; the graph must be gathered to
62// the process before entry.
64
65#include <vector>
66#include <algorithm>
67
68// This struct should be local to GreedyMWM(), but compiler complains.
69template <typename vtx_t, typename wgt_t>
71 vtx_t i;
72 vtx_t j;
73 wgt_t val;
74};
75
76template <typename vtx_t, typename wgt_t>
79{
80 return (a.val > b.val); // descending order
81}
82
83
84template <typename vtx_t, typename wgt_t>
86 int *idx, // Index into compressed sparse edge list;
87 // idx[i] is index into adj of first edge for vertex i
88 vtx_t *adj, // Edge list in compressed sparse format
89 wgt_t *wgt, // weights for each edge
90 vtx_t tnVtx, // number of vertices
91 vtx_t *match // output result: vtx i matches with vtx match[i]
92)
93{
94 typedef GMWM_triplet<vtx_t, wgt_t> triplet_t;
95 vtx_t nmatch=0;
96 std::vector<triplet_t> edges(idx[tnVtx]);
97
98 // Make vector of triplets (edges)
99 size_t k=0;
100 for (int i=0; i<tnVtx; i++){
101 for (int jj=idx[i]; jj<idx[i+1]; jj++){
102 int j = adj[jj];
103 if (i<=j){ // We need each edge only once.
104 edges[k].i = i;
105 edges[k].j = j;
106 edges[k].val = wgt[k];
107 }
108 k++;
109 }
110 }
111
112 // Sort edges by weight
113 std::sort (edges.begin(), edges.end(), compare_triplets<vtx_t,wgt_t>);
114
115 // Greedy loop over sorted edges
116 // std::cout << "After sort:" << std::endl;
117 for (typename std::vector<triplet_t>::iterator it=edges.begin();
118 it!=edges.end(); ++it){
119
120 // std::cout << "edge (" << it->i << ", " << it->j << ", "
121 // << it->val << ")" << std::endl;
122
123 if ((match[it->i] == it->i) && (match[it->j] == it->j )){
124 match[it->i] = it->j;
125 match[it->j] = it->i;
126 nmatch++;
127 }
128 }
129 return nmatch;
130}
131}
132
133
134#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)