图分割算法之贪心算法

1 贪心算法的思想

Linear Deterministic Greedy partitioning (LDG)考虑在分割的时候将邻居结点放置在一起，以减少切割边。它采用贪心算法将一个结点放置在包含其邻居最多的子图中，同时保证每个子图的结点负载均衡，整个算法流程图如下其中 C 表示每个分区的期望值，w(i) 表示当前子图在平衡状态下剩余容量，g(v,Pi) 表示再考虑负载的情况下结点 v 和子图 Pi 中结点邻居个数的交集，该打分函数作为将结点 v 分配到最大分数的子图中

2 代码设计

父类设计Partitioner

#ifndef PARTITION_H
#define PARTITION_H
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>class Partitioner 
{
public:/// <summary>/// 图分区的构造函数/// </summary>/// <param name="adjMatrix_">临界矩阵</param>Partitioner(std::vector<std::vector<int>> adjMatrix_);/// <summary>/// 图分割算法/// </summary>/// <param name="partNums">分区个数</param>virtual void execute(int partNums) = 0;/// <summary>/// 评估图分割算法/// </summary>virtual void evaluate() = 0;/// <summary>/// 返回分区结果/// </summary>std::vector<int> getResults() const;/// <summary>/// 获取顶点总数/// </summary>int getNumVertics() const;/// <summary>/// 获取图的便的总数/// </summary>int getNumEdges() const;private:protected:/// <summary>/// 邻接表存储的图数据/// </summary>std::vector<std::vector<int>> adjMatrix;/// <summary>/// 分区结果/// </summary>std::vector<int> partResults;int numVertices;int numEdges;};#endif // !PARTITION_H#include "Partitioner.h"Partitioner::Partitioner(std::vector<std::vector<int>> adjMatrix_) : adjMatrix(adjMatrix_)
{numVertices = adjMatrix_.size();numEdges = 0;std::for_each(adjMatrix_.begin(), adjMatrix_.end(), [&](const std::vector<int>& edges) {numEdges += edges.size();});
}std::vector<int> Partitioner::getResults() const
{return partResults;
}int Partitioner::getNumVertics() const
{return numVertices;
}int Partitioner::getNumEdges() const
{return numEdges;
}

LDGPartitioner的设计

#ifndef LDG_PARTITIONER_H
#define LDG_PARTITIONER_H#include "Partitioner.h"
#include <unordered_set>class LDGPartitioner : public Partitioner
{
public:LDGPartitioner(std::vector<std::vector<int>> adjMatrix_) : Partitioner(adjMatrix_) {};void execute(int partNums) override;void evaluate() override;private:/// <summary>/// 计算节点index的邻居和已分配的邻居相交的元素个数/// </summary>/// <param name="index">节点的下表</param>/// <param name="curVec">已分配的邻居</param>/// <returns></returns>int intersect(const int index, const std::unordered_set<int>& curVec);/// <summary>/// 已分配的集合/// </summary>std::vector<std::unordered_set<int>> curParts;
};#endif // !LDG_PARTITIONER_H#include "LDGPartitioner.h"void LDGPartitioner::execute(int partNums)
{//初始化std::vector<int> order(numVertices); //节点id的集合curParts.resize(numVertices);partResults.resize(numVertices);// 随机打乱idstd::iota(order.begin(), order.end(), 0);std::random_shuffle(order.begin(),order.end());//将前partNums的节点分配给每个分区作为第一个元素for (int i = 0; i < partNums; i++){curParts[i].insert(order[i]);partResults[order[i]] = i;}// 每个分区的期望值double expectant = static_cast<double>(numVertices / partNums);//便利剩余的元素for (int ii = partNums; ii < numVertices; ii++){//当前节点的idint vertex = order[ii];// 每个分区的得分std::vector<double> scores(partNums, 0);for (int jj = 0; jj < partNums; jj++) {double curSize = curParts[jj].size();double weight = static_cast<double>(1 - (curSize / expectant));double neighbors = intersect(vertex, curParts[jj]);scores[jj] = neighbors * weight;}//节点需要分配给得分最高的节点int maxIndex = std::distance(scores.begin(), std::max_element(scores.begin(), scores.end()));curParts[maxIndex].insert(vertex);partResults[vertex] = maxIndex;}
}void LDGPartitioner::evaluate()
{
}int LDGPartitioner::intersect(const int index,const std::unordered_set<int>& curVec)
{int count = 0;for (const auto& element : adjMatrix[index]){if (curVec.count(element))count++;}return count;
}

主函数测试：

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>#include <memory>#include "LDGPartitioner.h"using namespace std;// 定义图的邻接表类型
typedef vector<vector<int>> AdjacencyList;int main() {// 构造示例图的邻接表AdjacencyList graph = {{1, 2, 4},{0, 2, 4},{0, 1, 3},{2, 4},{0, 1, 3}};//Partitioner* ptr = new LDGPartitioner(graph);unique_ptr<Partitioner> ptr = make_unique<LDGPartitioner>(graph);ptr->execute(3);// 初始化划分vector<int> partition = ptr->getResults();// 输出划分结果for (int i = 0; i < partition.size(); i++) {cout << "Vertex " << i << " belongs to Partition " << partition[i] << endl;}return 0;
}