当前位置：首页 > 编程日记 > 正文

极小连通子图和极大连通子图_强连通分量与拓扑排序

编程日记 2024-04-27 08:00:00

前言

由于GacUI里面开始多处用上拓扑排序，我决定把之前瞎JB搞出来的算法换掉，换成个正式的。之前我自己弄了个写起来很简单的算法，然后每一处需要用到的地方我就重新做一遍。当然这样肯定也是不行的，我觉得也差不多积累到重构的临界点，于是重构一把。

我的需求是要在做拓扑排序的同时，识别出图的强连通分量。于是在经过短暂的考察之后，我选择了 Kosaraju's algorithm 。这个算法设计的很精妙，虽然很简单，但是令我回味无穷。该算法claim说自己是线性的，虽然也没错，但是实际上为了构造出这个数据结构，本身花费的时间已经超过线性了，所以整个算下来并不是线性的。

GacUI需要用到拓扑排序的地方很多，包括但不限于：

CodePack.exe

一个把一堆C++代码打包成几个成对的h和cpp代码的工具。这里就需要拓扑排序。因为在配置文件里（譬如说这个），我只定义了哪一些文件需要合并。而最后文件与文件的#include关系，是自动算出来的。拓扑排序在这里起到的作用，就是如果排序不成功，那我就要输出错误信息。

现在我输出错误信息只是告诉说你错了，并不能告诉你是谁跟谁搞在一起导致出错的。强连通分量在这里就起到了很好的效果，他识别出了循环引用的最小的集合，那么我就可以把这个集合输出到错误信息里，这样你就知道配置文件里面哪里写的不对。

Workflow 编译器

Workflow脚本语言支持C#那样子的class和struct。class可以继承，struct可以在成员里面引用别的struct。如果我们把class a继承自class b，和struct a用了struct b，都看成a依赖b的话，那么所有的class或者所有的struct就构成了一个图。这个图必须是偏序结构的，否则就意味着，要么你循环继承class，要么你虚幻嵌套struct，这都是错误的。

那强连通分量是什么作用呢？其实仍然是为了输出错误信息。如果你有一个很大的Workflow程序，我告诉你某个class循环继承了自己，看起来其实不是很友好。如果我可以告诉你到底是哪几个class互相继承，你改起代码来自然就方便多了。每一个强连通分量都代表了一个错误信息，很方便。

Workflow C++代码生成器

Workflow生成C++代码还有一些额外的要求。譬如说你在GacUI里面，指明了一个窗口的ref.CodeBehind属性为true，那么GacUI就会为你这个窗口单独生成一对C++文件，否则就全部加进大文件里。这样可以有效减少文件数量。你需要单独生成文件的理由，自然是你需要把自己的C++代码合并进这个窗口生成的C++代码里，就像流行的GUI库编辑器做的那样。典型的有事件处理函数，或者是你自己用C++添加的成员等等。

这就带来了两个问题。第一个问题是，如果你有三个窗口，a继承出b，而b继承出c。本来abc都是生成到同一个文件里面的，但是后来你给b加上了ref.CodeBehind=true，这会导致c也必须生成到一个独立的文件。因为如果ac在一个文件，b在另一个文件的话，你就没法正确#include。

显然，你ref.CodeBehind=true的一些窗口，使得ref.CodeBehind=false的一些窗口不一定可以全部放到一个头文件里。在这里识别出强连通分量就可以很好地减少分裂的头文件数量。当然并不是每一个强连通分量就是一个文件，这样也是很多余的。具体的办法我还没开始想，不过肯定是水到渠成的问题，因为明显只要对每一个强连通分量按照一定的规则染色，就搞定了。

第二个问题是，Workflow的类可以有嵌套类，嵌套类也会影响生成文件的安排，但是就算你只有一个文件，还会带来另一个问题。譬如说我有这样的C++代码：

class Fuck : public Bitch::Dung
{
public: class Shit{};
};class Bitch : public Fuck::Shit
{
public: class Dung{};
};

你会发现，不管你怎么调整顺序，不管你怎么向前声明，你都没办法让他编译通过。当然C#是不会有这个问题的，以C#和COM作为模板的Workflow自然也不会有这个问题。但是你真的这么写了，我就没办法替你生成C++代码。

那么自然，Workflow的C++代码生成器必须在这个时候报错。这里我们仍然要进行拓扑排序，但是图的每一个节点，其实就是每一个top level class和所有内部类的集合。在这里自然就是{Fuck, Fuck::Shit}以及{Bitch, Bitch::Dung}。在检查继承关系之后，我们发现这两个节点是循环引用的，因此会被分配到同一个强连通分量里。如果排序的结果，有一个强连通分量有超过一个节点的话，那么就意味着这种代码没办法生成C++代码，因此就可以抱错了。报错的时候，我又可以生成好看的错误信息了。

实现

其他的我就不说了，还有很多。如果你们好好看了上面的维基百科的链接，就知道Kosaraju算法是表达为递归的。在敲代码之前，我也考虑过到底要不要把递归化为循环，让爆栈不那么容易发生。后来想想算了，因为这里的递归的层数，跟你C++代码#include的层数，和类继承的层数是一致的。如果你的Workflow类一共继承了1000层，那你也不要怪我GacGen.exe崩溃，我不管的（逃。因此我毅然选择了递归。

Vlpp里面一共有三个文件：PartialOrdering.h、PartialOrdering.cpp和TestPartialOrdering.cpp。大家有兴趣的话就去看，里面有实现以及测试用例。

经过我的估算，这个类的三个主要函数的worst case复杂度分别是：

InitWithGroup：O(ElgV)
InitWithFunc：O(V² + ElgV)
Sort：O(V+E)

总的来说，整个东西的复杂度还是会被控制在O(nlgn)或者O(n²)，还行。

之前瞎JB搞得算法的worst case是O(n³lgn)，看起来很吓人，不过因为我处理的图都是稀疏图，所以平均下来也不会这么难看。既然已经把靠谱的算法做进GacUI了，那么接下来就是把每一处用到垃圾拓扑排序的地方删掉，用新写的算法替换上。

尾声

写代码真是开心啊，每天都可以找到缺陷可以改进，每天都有代码可以写。希望有我同样热情的人，好好学习，不要被一些投机倒把的CS学生，把你们的大学学籍给挤掉，每一个喜欢编程的同学最终都能读上CS专业。

https://www.dkcj.cn/info/5290.html

极小连通子图和极大连通子图_强连通分量与拓扑排序

前言

CodePack.exe

Workflow 编译器

Workflow C++代码生成器

实现

尾声

相关文章：

INTERVAL数据类型-007学习笔记

scrapy模拟用户登录

linux 系统调用 open函数使用

配置zendframework开始工作（加入环境变量）

mysql计算两gps坐标的距离_mysql 计算两坐标间的距离

（转）mxArray数据类型

Bootstrap笔记（记录不会的知识）

linux 系统调用 read,write和lseek 使用

简单有趣的matlab小程序_超实用有趣的五个小程序推荐

一些linux下的性能监测工具

uva 10183 How many Fibs?

2018/11/29 一个64位操作系统的设计与实现 02 (安装nasm)

a-awk 计算数值最大，最小，平均值并保留指定位数

第18章：MYSQL分区

mysql属性配置提高查询_MYSQL性能优化-安装时优化参数配置提高服务性能

c++引用的自我见解

c# yield关键字原理

linux进程间通信：命名管道FIFO

mysql 账户管理_如何用MySQL 命令来实现账户管理

Can't connect to MySQL server on '127.0.0.1' (10061) (code 2003)解决方法

学习MongoDB （1）：配置安装

跨域策略文件crossdomain.xml文件

linux进程间通信：FIFO应用 /var/log/ 系统日志的模拟实现

context.xml mysql_在tomcat下context.xml中配置各种数据库连接池(示例代码)

Planetary.js：帮助你构建超炫的互动球体效果

JAVA条件表达式的陷阱

腾讯Bugly异常崩溃SDK接入

linux进程间通信：FIFO实现进程间的双向通信

load python txt文件_详解Python中numpy.loadtxt()读取txt文件

线程之线程标识