内蒙古建设厅网站查询,衡东网站建设,php cms网站,西安旅游攻略ppt该项目是一个基于链式前向星存图、boost#xff08;boost::hash、asio线程池#xff09;以及emhash7/8的非官方实现#xff0c;实现了最小反馈弧集问题的三种近似算法。该问题是在有向图中找到最小的反馈弧集#xff0c;其中反馈弧集是指一组弧#xff0c;使得从这些反馈弧…该项目是一个基于链式前向星存图、boostboost::hash、asio线程池以及emhash7/8的非官方实现实现了最小反馈弧集问题的三种近似算法。该问题是在有向图中找到最小的反馈弧集其中反馈弧集是指一组弧使得从这些反馈弧的尾部到头部的路径构成一个环。
算法实现
该项目基于C实现了三种近似算法
GreedyFAS 这是一种基于贪心策略的算法用贪心法生成一个线性排列将该线性排列中的后向边集作为结果返回。
贪心策略 查找源头点若查到源头点则排到序列s1末尾并移除该点重复直到没有源头点查找汇集点若查到汇集点则排到序列s2头部并移除该点重复直到没有汇集点若既没有源头点也没有汇集点则定义delta值出度-入度将delta最大的点排到s1末尾。计算剩余点的delta将delta值最大的点排在s1末尾并移除该点。返回{s1,s2} - 最小线性排列 SortFAS 该算法根据序号的自然顺序生成初始最小线性排列问题LA不断调整LA使后向边的数量尽可能少。 PageRankFAS 该算法是一种启发式算法来自于论文[1] Geladaris V , Lionakis P , Tollis I G . Computing a Feedback Arc Set Using PageRank[J]. 2022用于计算有向图中的最小反馈弧集 (FAS)。该算法的工作原理如下 检测图是否有环如果存在环执行以下循环 识别有向图中的强连接分量si, i0,1,…遍历强连通分量si对于每个强连通分量si执行 如果si的大小为1跳过该强连通分量的处理选择si中的一个随机节点v从v开始遍历创建si的线图L(si)计算L(si)的PageRank选择L(si)中PageRank值最大的节点找到si中对应的边e添加到最小反馈弧集。在si中删除边e 如果仍有环重复执行1和2直到图不存在环为止。 PageRankFAS 算法的输入是一个有向图 G由顶点 V 和边 E 组成。输出是 G 的反馈弧集。
该算法可以用于可用于计算有向图中的最小反馈弧集FAS这是一个与可视化分层结构相关的具有挑战性的问题。它比现有的启发式方法更好并将FAS大小平均减少了50以上。尽管由于生成的折线图的大小对于较大的网图它的执行时间可能会增加但即使对于在多达 4,000 个节点的图形绘制应用程序中使用的大型图形它的运行速度也非常快。因此这种方法对于研究需要计算 FAS 或涉及有向图例如排名算法或网络流量分析等的类似优化任务的研究人员可能很有用。
本项目的实现是基于C语言可以直接下载源代码并编译运行。详细的使用方法请参考项目中的 README 文件。
运行项目
如果您想尝试这些算法需要克隆该项目然后先安装Boost和gtest库再使用cmake编译运行该项目 打开终端并输入以下命令来更新软件包列表 sudo apt-get update输入以下命令来安装Boost库和gtest库 sudo apt-get install libboost-all-dev libgtest-dev输入以下命令编译项目 cmake -B build cmake --build build输入以下命令运行项目 ./build/FASSolver [path/to/graph] [alorigthm (greedy | sort | pagerank)]数据集
简单图 graphs/simple.txt 0,1
1,2
2,3
3,0
3,1
4,5
5,6
6,4大型图
graphs/wordassociation-2011.txt: 10,617 个顶点和 72,172 条有向边graphs/enron.txt: 69,244 个顶点和 276,143 条有向边
运行结果
简单图: graphs/simple.txt GreedyFAS 2
2,3
6,4graphs/simple.txt SortFAS 2
2,3
5,6graphs/simple.txt PageRankFAS 2
1,2
4,5大型图
graphs/wordassociation-2011.txt GreedyFAS: 13634条反馈弧, 耗时0.701sSortFAS: 13510条反馈弧, 耗时0.817sPageRankFAS: 12086条反馈弧, 耗时68.856s graphs/enron.txt GreedyFAS: 38850条反馈弧, 耗时10.989sSortFAS: 36548条反馈弧, 耗时14.281sPageRankFAS: 33796条反馈弧, 耗时1398.224s
