极小连通子图和极大连通子图_强连通分量与拓扑排序
前言
由于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专业。