图分割算法之贪心算法

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;
}

3 执行结果

        

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2660074.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

单文件超过4GB就无法拷贝到U盘?这个你一定要知道

前言 随着现在科技发展&#xff0c;小伙伴们所使用的数据也越变越大。还记得WindowsXP流行的时候&#xff0c;XP的镜像文件仅为几百MB大小。 但是现在随便一个系统就有可能超过4GB。 如果单个文件超过4GB就有可能没办法拷贝进U盘&#xff0c;在这里就需要给小伙伴们普及一下U…

用ChatGPT挑选钻石!著名珠宝商推出-珠宝GPT

根据Salesforce最新发布的第五版《互联网购物报告》显示&#xff0c;ChatGPT等生成式AI的出现、快速发展&#xff0c;对零售行业和购物者产生了较大影响。可有效简化业务流程实现降本增效&#xff0c;并改善购物体验。 著名珠宝商James Allen为了积极拥抱生成式AI全面提升销售…

vue2使用svg图片

1、安装依赖包&#xff1a; npm install svg-sprite-loader --save-dev 2、新建assets/icons/svg中放置svg图片和index.js文件 svgo.yml文件 index.js import Vue from vue import SvgIcon from /components/SvgIcon// svg component// register globally Vue.component(sv…

antd中DatePicker禁选范围如何设置

1、解决日期禁选问题 在官方api中也提到&#xff0c;可以设置disabledDate来实现日期的禁选 语法&#xff1a; js中定义disabledData函数 const disabledDate (current) > { 设置禁选范围 } 在DatePicker 标签中引入 同时我们要知道antd是默认使用moment.js来实现日期格式…

【ES】es介绍

倒排索引&#xff08;Inverted Index&#xff09;和正排索引&#xff08;Forward Index&#xff09; 正排索引是一种以文档为单位的索引结构&#xff0c;它将文档中的每个单词或词组与其所在的文档进行映射关系的建立。正排索引通常用于快速检索指定文档的内容&#xff0c;可以…

Python列表数据处理全攻略(三):常用内置方法轻松掌握

文章目录 引言Python列表常用内置方法count()功能介绍语法示例注意事项 index()功能介绍语法示例注意事项&#xff1a; insert()功能介绍语法示例注意事项总结 结束语 引言 亲爱的读者&#xff0c;你好&#xff01;Python的列表在数据结构中占据着核心地位&#xff0c;对于学习…

k8s-cni网络 10

Flannel vxlan模式跨主机通信原理 在同一个节点上的pod 流量通过cni网桥可以直接进行转发&#xff1b; 在需要跨主机访问时&#xff0c;数据包通过flannel(隧道) 知道另一边的mac地址&#xff0c;就可以拿到另一边的ip地址&#xff0c;然后构建常规的以太网数据包&#xff0c;…

github登录需要双因素认证(Two-factor authentication)

前言 这是我在这个网站整理的笔记,有错误的地方请指出&#xff0c;关注我&#xff0c;接下来还会持续更新。 作者&#xff1a;神的孩子都在歌唱 github登录需要双因素认证&#xff08;Two-factor authentication&#xff09; 今天登录github发现需要绑定双因素才能够登录 我们…

具有权威性的工信部证书怎么考

工信部证书的考试流程如下&#xff1a; 选择正规报考机构&#xff1a;选择一家权威的培训机构或考试中心&#xff0c;确保其具有相应的资质和经验。 提交个人报考资料&#xff1a;根据考试机构的要求&#xff0c;提交相关的个人报考资料&#xff0c;如身份证、学历证明、工作…

【单片机项目实战】温度控制系统

本项目的主要作用是实现温度调控&#xff0c;通过设定一个预定的温度值&#xff0c;实现实时检测外界温度&#xff0c;当外界温度小于预定值时&#xff0c;电机正转&#xff0c;实现降温效果&#xff1b;当外界温度大于预定值时&#xff0c;电机反转&#xff0c;实现升温效果&a…

SpringBoot多线程与任务调度总结

一、前言 多线程与任务调度是java开发中必须掌握的技能&#xff0c;在springBoot的开发中&#xff0c;多线程和任务调度变得越来越简单。实现方式可以通过实现ApplicationRunner接口&#xff0c;重新run的方法实现多线程。任务调度则可以使用Scheduled注解 二、使用示例 Slf…

TiDB SQL调优案例TiFlash

背景 早上收到某系统的告警tidb节点挂掉无法访问&#xff0c;情况十万火急。登录中控机查了一下display信息&#xff0c;4个TiDB、Prometheus、Grafana全挂了&#xff0c;某台机器hang死无法连接&#xff0c;经过快速重启后集群恢复&#xff0c;经排查后是昨天上线的某个SQL导…

2022年全球软件质量效能大会(QECon北京站2022)-核心PPT资料下载

一、峰会简介 当前&#xff0c;新一轮科技革命和产业变革正在重塑全球经济格局&#xff0c;以云计算为代表的新一代信息技术创新活跃&#xff0c;与实体经济深度融合&#xff0c;推动泛在连接、数据驱动、智能引领的数字经济新形式孕育而生。 新兴技术的出现给测试乃至整个软…

小米路由器2(R2D) 安装 MIXBOX

1. 先刷开发版 ROM http://www1.miwifi.com/miwifi_download.html 进入上述网页&#xff0c;找到 R2D 点击下载 开发版 ROM 教程 看 下载按钮上边的 “刷机教程” 刷机教程 2. 开启SSH工具 登录自己的小米账号后&#xff0c;里面会显示出 自己的 root密码&#xff1b; 默认…

记一次修复外网无法访问vmware里面的虚拟机的网络端口的问题

发现一个奇怪的网络问题&#xff0c;vmware里一个程序的端口通过vmnat穿透出来&#xff0c;然后这个端口就能够通过局域网被其他机器访问&#xff0c;但是另一个网段就没法访问这个端口。使用主机上的其他程序使用开启同样的端口&#xff0c;另一个网段的机器却可以访问。我想不…

Android Security PIN 相关代码

开发项目遇到一个问题&#xff0c;具体描述及复制步骤如下&#xff1a; 就是开启"Enhanced PIN privacy"(增强的PIN隐私)的时候输入秘密的时候还是会显示数字 如下图&#xff0c;应该是直接是“.” 不应该出现PIN 密码 想要的效果如下图&#xff1a; 设置的步骤如下图…

中职网络安全Server2002——Web隐藏信息获取

B-2&#xff1a;Web隐藏信息获取 任务环境说明&#xff1a; 服务器场景名&#xff1a;Server2002&#xff08;关闭链接&#xff09;服务器场景用户名&#xff1a;未知 有问题需要环境加q 通过本地PC中渗透测试平台Kali使用Nmap扫描目标靶机HTTP服务子目录&#xff0c;将扫描子…

用户规模破亿!基于文心一言的创新应用已超4000个

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

Matter协议解析记录

目录 目录 1、Matter 协议发展 1.1、什么是Matter 1.2、Matter能做什么 2、整体介绍 3、架构介绍 3.1、Matter网络拓扑结构 3.2、功能解析 3.2.1、Fabric引用和Fabric标识符 3.2.2、供应商标识符&#xff08;Vendor ID&#xff0c;VID&#xff09; 3.2.3、产品标识符…

类。。。。

定义一个person类&#xff0c;包含私有成员&#xff0c;int *age,string &name,一个stu类&#xff0c;包含私有成员double *sore,person p1,写出person类和stu类的特殊成员函数&#xff0c;并写一个stu的函数&#xff0c;显示所有信息。 #include <iostream>using n…