強連通分量與拓撲排序

來自專欄 vczh的日常183 人贊了文章

前言

由於GacUI裡面開始多處用上拓撲排序，我決定把之前瞎JB搞出來的演算法換掉，換成個正式的。之前我自己弄了個寫起來很簡單的演算法，然後每一處需要用到的地方我就重新做一遍。當然這樣肯定也是不行的，我覺得也差不多積累到重構的臨界點，於是重構一把。

我的需求是要在做拓撲排序的同時，識別出圖的強連通分量。於是在經過短暫的考察之後，我選擇了 Kosarajus 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(V2 + ElgV)
• Sort：O(V+E)

總的來說，整個東西的複雜度還是會被控制在O(nlgn)或者O(n2)，還行。

之前瞎JB搞得演算法的worst case是O(n3lgn)，看起來很嚇人，不過因為我處理的圖都是稀疏圖，所以平均下來也不會這麼難看。既然已經把靠譜的演算法做進GacUI了，那麼接下來就是把每一處用到垃圾拓撲排序的地方刪掉，用新寫的演算法替換上。

尾聲

寫代碼真是開心啊，每天都可以找到缺陷可以改進，每天都有代碼可以寫。希望有我同樣熱情的人，好好學習，不要被一些投機倒把的CS學生，把你們的大學學籍給擠掉，每一個喜歡編程的同學最終都能讀上CS專業。