Function ComputeNormalizedMinGraphCut

src/colmap/math/graph_cut.cc:186–232

}

std::unordered_map<int, int> ComputeNormalizedMinGraphCut(
    const std::vector<std::pair<int, int>>& edges,
    const std::vector<int>& weights,
    const int num_parts) {
  THROW_CHECK(!edges.empty());
  THROW_CHECK_EQ(edges.size(), weights.size());
  THROW_CHECK_GT(num_parts, 0);

  MetisGraph graph(edges, weights);

  idx_t ncon = 1;
  idx_t edgecut = -1;
  idx_t nparts = num_parts;

  idx_t metisOptions[METIS_NOPTIONS];
  METIS_SetDefaultOptions(metisOptions);

  std::vector<idx_t> cut_labels(graph.nvtxs, -1);
  const int metisResult = METIS_PartGraphKway(&graph.nvtxs,
                                              /*ncon=*/&ncon,
                                              graph.xadj,
                                              graph.adjncy,
                                              /*vwgt=*/nullptr,
                                              /*vsize=*/nullptr,
                                              graph.adjwgt,
                                              &nparts,
                                              /*tpwgts=*/nullptr,
                                              /*ubvec=*/nullptr,
                                              metisOptions,
                                              &edgecut,
                                              cut_labels.data());

  if (metisResult == METIS_ERROR_INPUT) {
    LOG(FATAL_THROW) << "INTERNAL: Metis input error";
  } else if (metisResult == METIS_ERROR_MEMORY) {
    LOG(FATAL_THROW) << "INTERNAL: Metis memory error";
  } else if (metisResult == METIS_ERROR) {
    LOG(FATAL_THROW) << "INTERNAL: Metis 'some other type of error'";
  }

  std::unordered_map<int, int> labels;
  for (size_t idx = 0; idx < cut_labels.size(); ++idx) {
    labels.emplace(graph.GetVertexId(idx), cut_labels[idx]);
  }

  return labels;
}

}  // namespace colmap