10 #if !defined(CGRAPHPARTITIONER_H) 11 #error "This file can't be included from outside of CGraphPartitioner.h" 19 template <
class GRAPH_MATRIX,
typename num_t>
21 GRAPH_MATRIX& in_A, std::vector<uint32_t>& out_part1,
22 std::vector<uint32_t>& out_part2, num_t& out_cut_value,
bool forceSimetry)
28 if (in_A.cols() != int(nodeCount = in_A.rows()))
37 Adj.setSize(nodeCount, nodeCount);
38 for (
size_t i = 0; i < nodeCount; i++)
39 for (
size_t j = i; j < nodeCount; j++)
40 Adj(i, j) = Adj(j, i) = 0.5f * (in_A(i, j) + in_A(j, i));
46 GRAPH_MATRIX LAPLACIAN;
47 Adj.laplacian(LAPLACIAN);
65 for (
size_t i = 0; i < nRows; i++)
68 out_part1.push_back(i);
70 out_part2.push_back(i);
76 if (!out_part1.size() || !out_part2.size())
81 for (
int i = 0; i < Adj.cols(); i++)
82 if (i <= Adj.cols() / 2)
83 out_part1.push_back(i);
85 out_part2.push_back(i);
89 out_cut_value = nCut(Adj, out_part1, out_part2);
95 template <
class GRAPH_MATRIX,
typename num_t>
97 GRAPH_MATRIX& in_A, std::vector<std::vector<uint32_t>>& out_parts,
98 num_t threshold_Ncut,
bool forceSimetry,
bool useSpectralBisection,
99 bool recursive,
unsigned minSizeClusters,
const bool verbose)
104 std::vector<uint32_t> p1, p2;
112 if (in_A.cols() != int(nodeCount = in_A.rows()))
119 out_parts.push_back(p1);
126 Adj.setSize(nodeCount, nodeCount);
127 for (i = 0; i < nodeCount; i++)
128 for (j = i; j < nodeCount; j++)
129 Adj(i, j) = Adj(j, i) = 0.5f * (in_A(i, j) + in_A(j, i));
135 if (useSpectralBisection)
136 SpectralBisection(Adj, p1, p2, cut_value,
false);
138 exactBisection(Adj, p1, p2, cut_value,
false);
142 "Cut:%u=%u+%u,nCut=%.02f->", (
unsigned int)nodeCount,
143 (
unsigned int)p1.size(), (
unsigned int)p2.size(), cut_value);
146 if (cut_value > threshold_Ncut || p1.size() < minSizeClusters ||
147 p2.size() < minSizeClusters)
149 if (verbose) std::cout <<
"->NO!" << std::endl;
153 for (i = 0; i < nodeCount; i++) p1.push_back(i);
154 out_parts.push_back(p1);
158 if (verbose) std::cout <<
"->YES!" << std::endl;
161 std::vector<std::vector<uint32_t>> p1_parts, p2_parts;
168 GRAPH_MATRIX A_1(p1.size(), p1.size());
169 for (i = 0; i < p1.size(); i++)
170 for (j = 0; j < p1.size(); j++) A_1(i, j) = in_A(p1[i], p1[j]);
172 RecursiveSpectralPartition(
173 A_1, p1_parts, threshold_Ncut, forceSimetry,
174 useSpectralBisection, recursive, minSizeClusters);
179 GRAPH_MATRIX A_2(p2.size(), p2.size());
180 for (i = 0; i < p2.size(); i++)
181 for (j = 0; j < p2.size(); j++) A_2(i, j) = in_A(p2[i], p2[j]);
183 RecursiveSpectralPartition(
184 A_2, p2_parts, threshold_Ncut, forceSimetry,
185 useSpectralBisection, recursive, minSizeClusters);
191 for (i = 0; i < p1_parts.size(); i++)
193 for (j = 0; j < p1_parts[i].size(); j++)
194 p1_parts[i][j] = p1[p1_parts[i][j]];
195 out_parts.push_back(p1_parts[i]);
199 for (i = 0; i < p2_parts.size(); i++)
201 for (j = 0; j < p2_parts[i].size(); j++)
202 p2_parts[i][j] = p2[p2_parts[i][j]];
204 out_parts.push_back(p2_parts[i]);
211 out_parts.push_back(p1);
212 out_parts.push_back(p2);
222 template <
class GRAPH_MATRIX,
typename num_t>
224 const GRAPH_MATRIX& in_A,
const std::vector<uint32_t>& in_part1,
225 const std::vector<uint32_t>& in_part2)
228 size_t size1 = in_part1.size();
229 size_t size2 = in_part2.size();
234 for (i = 0; i < size1; i++)
235 for (j = 0; j < size2; j++) cut_AB += in_A(in_part1[i], in_part2[j]);
238 for (i = 0; i < size1; i++)
239 for (j = i; j < size1; j++)
240 if (i != j) assoc_AA += in_A(in_part1[i], in_part1[j]);
243 for (i = 0; i < size2; i++)
244 for (j = i; j < size2; j++)
245 if (i != j) assoc_BB += in_A(in_part2[i], in_part2[j]);
247 num_t assoc_AV = assoc_AA + cut_AB;
248 num_t assoc_BV = assoc_BB + cut_AB;
253 return cut_AB / assoc_AV + cut_AB / assoc_BV;
259 template <
class GRAPH_MATRIX,
typename num_t>
261 GRAPH_MATRIX& in_A, std::vector<uint32_t>& out_part1,
262 std::vector<uint32_t>& out_part2, num_t& out_cut_value,
bool forceSimetry)
267 std::vector<bool> partition, bestPartition;
268 std::vector<uint32_t> part1, part2;
269 num_t partCutValue, bestCutValue = std::numeric_limits<num_t>::max();
273 if (in_A.cols() != int(nodeCount = in_A.rows()))
281 Adj.setSize(nodeCount, nodeCount);
282 for (i = 0; i < nodeCount; i++)
283 for (j = i; j < nodeCount; j++)
284 Adj(i, j) = Adj(j, i) = 0.5f * (in_A(i, j) + in_A(j, i));
295 partition.resize(nodeCount,
false);
304 for (i = 0; i < nodeCount; i++)
313 partCutValue = nCut(Adj, part1, part2);
315 if (partCutValue < bestCutValue)
317 bestCutValue = partCutValue;
318 bestPartition = partition;
326 carry = partition[i];
327 partition[i] = !partition[i];
329 }
while (carry && i < nodeCount);
333 for (i = 0;
end && i < nodeCount; i++)
end =
end && partition[i];
338 out_cut_value = bestCutValue;
343 for (i = 0; i < nodeCount; i++)
345 if (bestPartition[i])
346 out_part2.push_back(i);
348 out_part1.push_back(i);
#define THROW_EXCEPTION(msg)
EIGEN_STRONG_INLINE bool eigenVectors(MATRIX1 &eVecs, MATRIX2 &eVals) const
[For square matrices only] Compute the eigenvectors and eigenvalues (sorted), both returned as matric...
Abstract graph and tree data structures, plus generic graph algorithms.
static void SpectralBisection(GRAPH_MATRIX &in_A, std::vector< uint32_t > &out_part1, std::vector< uint32_t > &out_part2, num_t &out_cut_value, bool forceSimetry=true)
Performs the spectral bisection of a graph.
#define ASSERT_(f)
Defines an assertion mechanism.
static num_t nCut(const GRAPH_MATRIX &in_A, const std::vector< uint32_t > &in_part1, const std::vector< uint32_t > &in_part2)
Returns the normaliced cut of a graph, given its adjacency matrix A and a bisection: ...
static void exactBisection(GRAPH_MATRIX &in_A, std::vector< uint32_t > &out_part1, std::vector< uint32_t > &out_part2, num_t &out_cut_value, bool forceSimetry=true)
Performs an EXACT minimum n-Cut graph bisection, (Use CGraphPartitioner::SpectralBisection for a fast...
std::string format(const char *fmt,...) MRPT_printf_format_check(1
A std::string version of C sprintf.
EIGEN_STRONG_INLINE void eigenValues(VECTOR &eVals) const
[For square matrices only] Compute the eigenvectors and eigenvalues (sorted), and return only the eig...
static void RecursiveSpectralPartition(GRAPH_MATRIX &in_A, std::vector< std::vector< uint32_t >> &out_parts, num_t threshold_Ncut=1, bool forceSimetry=true, bool useSpectralBisection=true, bool recursive=true, unsigned minSizeClusters=1, const bool verbose=false)
Performs the spectral recursive partition into K-parts for a given graph.
EIGEN_STRONG_INLINE double mean() const
Computes the mean of the entire matrix.