在 Go 中對(duì)依賴(lài)圖進(jìn)行排序

01 什么是拓?fù)渑判颍?/span>

在我的職業(yè)生涯中，我一次又一次遇到的常見(jiàn)問(wèn)題之一就是對(duì)依賴(lài)圖的節(jié)點(diǎn)進(jìn)行拓?fù)渑判颉Q句話說(shuō)，給定一些有向無(wú)環(huán)圖 — 想想可以依賴(lài)于其他軟件包或大型公司項(xiàng)目中的任務(wù)的軟件包 — 對(duì)它們進(jìn)行排序，以便列表中的任何項(xiàng)目都不會(huì)依賴(lài)于列表中后面出現(xiàn)的任何內(nèi)容。假設(shè)我們正在制作蛋糕，在開(kāi)始之前，我們需要一些原料。讓我們來(lái)簡(jiǎn)化一下，說(shuō)我們只需要雞蛋和面粉。嗯，要吃雞蛋，我們需要雞（相信我，我在這里不是開(kāi)玩笑），要吃面粉，我們需要谷物。雞也需要谷物作為飼料，谷物需要土壤和水才能生長(zhǎng)。我們考慮表達(dá)所有這些依賴(lài)關(guān)系的圖表：

該圖的一種可能的拓?fù)漤樞蚴牵?/p>

[]string{"soil",?"water",?"grain",?"chickens",?"flour",?"eggs",?"cake"}

但是，還有其他可能的拓?fù)漤樞颍?/p>

[]string{"water",?"soil",?"grain",?"flour",?"chickens",?"eggs",?"cake"}

我們也可以把面粉放在雞蛋后面，因?yàn)槲ㄒ灰蕾?lài)雞蛋的就是蛋糕。由于我們可以重新排列項(xiàng)目，我們還可以并行完成其中一些項(xiàng)目，同時(shí)保持任何項(xiàng)目都不會(huì)出現(xiàn)在依賴(lài)于它的任何東西之前。例如，通過(guò)添加一層嵌套，我們可以表明內(nèi)部切片中的所有內(nèi)容都獨(dú)立于該切片中的其他任何內(nèi)容：

[][]string{
????{"soil",?"water"},
????{"grain"},
????{"chickens",?"flour"},
????{"eggs"},
????{"cake"},
}

從這個(gè)圖中，我們得到了一個(gè)很好的“執(zhí)行計(jì)劃”，用于為蛋糕準(zhǔn)備依賴(lài)項(xiàng)。首先，我們需要找到一些土壤和水。接下來(lái)，我們種植谷物。然后，我們同時(shí)養(yǎng)一些雞和做面粉，收集雞蛋。最后，我們可以做蛋糕了！對(duì)于小于四歲的人來(lái)說(shuō)，這似乎是一項(xiàng)艱巨的工作，但好的事情需要時(shí)間。

02 構(gòu)建依賴(lài)圖

現(xiàn)在我們了解了要做什么，讓我們考慮如何編寫(xiě)一些能夠構(gòu)建這種依賴(lài)項(xiàng)列表的代碼。我們當(dāng)然需要跟蹤元素本身，我們需要跟蹤什么取決于什么。為了使“取決于什么X？” 和“X取決于什么？”?兩者都高效，我們將跟蹤兩個(gè)方向的依賴(lài)關(guān)系。

我們已經(jīng)足夠了解開(kāi)始編寫(xiě)代碼所需的內(nèi)容：

//?A?node?in?this?graph?is?just?a?string,?so?a?nodeset?is?a?map?whose
//?keys?are?the?nodes?that?are?present.
type?nodeset?map[string]struct{}

//?depmap?tracks?the?nodes?that?have?some?dependency?relationship?to
//?some?other?node,?represented?by?the?key?of?the?map.
type?depmap?map[string]nodeset

type?Graph?struct?{
?nodes?nodeset

?//?Maintain?dependency?relationships?in?both?directions.?These
?//?data?structures?are?the?edges?of?the?graph.

?//?`dependencies`?tracks?child?->?parents.
?dependencies?depmap
?//?`dependents`?tracks?parent?->?children.
?dependents?depmap
?//?Keep?track?of?the?nodes?of?the?graph?themselves.
}

func?New()?*Graph?{
?return?&Graph{
??dependencies:?make(depmap),
??dependents:???make(depmap),
??nodes:????????make(nodeset),
?}
}

這種數(shù)據(jù)結(jié)構(gòu)應(yīng)該適合我們的目的，因?yàn)樗覀冃枰乃行畔ⅲ汗?jié)點(diǎn)、“依賴(lài)”邊和“依賴(lài)于”邊?，F(xiàn)在讓我們考慮創(chuàng)建用于向圖形添加新依賴(lài)關(guān)系的 API。所有我們需要的是一個(gè)聲明的方法，一些節(jié)點(diǎn)依賴(lài)于另一個(gè)，就像這樣：graph.DependOn("flour", "grain")。有幾種情況我們要明確禁止。首先，一個(gè)節(jié)點(diǎn)不能依賴(lài)于自己，其次，如果flour依賴(lài)于grain，那么grain一定不能依賴(lài)于flour，否則我們會(huì)創(chuàng)建一個(gè)無(wú)限的依賴(lài)循環(huán)。有了這個(gè)，讓我們編寫(xiě)Graph.DependOn()方法。

func?(g?*Graph)?DependOn(child,?parent?string)?error?{
?if?child?==?parent?{
??return?errors.New("self-referential?dependencies?not?allowed")
?}

?//?The?Graph.DependsOn()?method?doesn't?exist?yet.
?//?We'll?write?it?next.
?if?g.DependsOn(parent,?child)?{
??return?errors.New("circular?dependencies?not?allowed")
?}

?//?Add?nodes.
?g.nodes[parent]?=?struct{}{}
?g.nodes[child]?=?struct{}{}

?//?Add?edges.
?addNodeToNodeset(g.dependents,?parent,?child)
?addNodeToNodeset(g.dependencies,?child,?parent)

?return?nil
}

func?addNodeToNodeset(dm?depmap,?key,?node?string)?{
?nodes,?ok?:=?dm[key]
?if?!ok?{
??nodes?=?make(nodeset)
??dm[key]?=?nodes
?}
?nodes[node]?=?struct{}{}
}

一旦我們實(shí)現(xiàn)，這將有效地為我們的圖表添加依賴(lài)關(guān)系Graph.DependsOn()。我們可以很容易地判斷一個(gè)節(jié)點(diǎn)是否直接依賴(lài)于其他某個(gè)節(jié)點(diǎn)，但我們也想知道是否存在傳遞依賴(lài)。例如，由于flour依賴(lài)于grain并且grain依賴(lài)于soil，因此也flour依賴(lài)于soil。這將要求我們獲取節(jié)點(diǎn)的直接依賴(lài)項(xiàng)，然后對(duì)于這些依賴(lài)項(xiàng)中的每一個(gè)，獲取其依賴(lài)項(xiàng)等等，直到我們停止發(fā)現(xiàn)新的依賴(lài)項(xiàng)。用計(jì)算機(jī)科學(xué)術(shù)語(yǔ)來(lái)說(shuō)，我們正在計(jì)算一個(gè)固定點(diǎn)，以在我們的圖上找到“DependsOn”關(guān)系的傳遞閉包。

func?(g?*Graph)?DependsOn(child,?parent?string)?bool?{
?deps?:=?g.Dependencies(child)
?_,?ok?:=?deps[parent]
?return?ok
}

func?(g?*Graph)?Dependencies(child?string)?nodeset?{
?if?_,?ok?:=?g.nodes[root];?!ok?{
??return?nil
?}
?
?out?:=?make(nodeset)
?searchNext?:=?[]string{root}
?for?len(searchNext)?>?0?{
??//?List?of?new?nodes?from?this?layer?of?the?dependency?graph.?This?is
??//?assigned?to?`searchNext`?at?the?end?of?the?outer?"discovery"?loop.
??discovered?:=?[]string{}
??for?_,?node?:=?range?searchNext?{
???//?For?each?node?to?discover,?find?the?next?nodes.
???for?nextNode?:=?range?nextFn(node)?{
????//?If?we?have?not?seen?the?node?before,?add?it?to?the?output?as?well
????//?as?the?list?of?nodes?to?traverse?in?the?next?iteration.
????if?_,?ok?:=?out[nextNode];?!ok?{
?????out[nextNode]?=?struct{}{}
?????discovered?=?append(discovered,?nextNode)
????}
???}
??}
??searchNext?=?discovered
?}
?
?return?out
}

03 對(duì)圖表進(jìn)行排序

現(xiàn)在我們有了一個(gè)圖數(shù)據(jù)結(jié)構(gòu)，可以考慮如何按照拓?fù)漤樞驅(qū)⒐?jié)點(diǎn)取出。如果我們可以發(fā)現(xiàn)葉節(jié)點(diǎn)—即，節(jié)點(diǎn)本身對(duì)其他節(jié)點(diǎn)沒(méi)有依賴(lài)關(guān)系—那么我們可以重復(fù)獲取葉子并將它們從圖中移除，直到圖為空。在第一次迭代中，我們將找到獨(dú)立的元素，然后在隨后的每次迭代中，我們將找到僅依賴(lài)于已刪除元素的節(jié)點(diǎn)。最終結(jié)果將是一個(gè)按拓?fù)渑判虻莫?dú)立“層”節(jié)點(diǎn)的切片。

獲取圖的葉子很簡(jiǎn)單。我們只需要找到在 dependencies 中沒(méi)有條目的節(jié)點(diǎn)。這意味著它們不依賴(lài)于任何其他節(jié)點(diǎn)。

func?(g?*Graph)?Leaves()?[]string?{
?leaves?:=?make([]string,?0)

?for?node?:=?range?g.nodes?{
??if?_,?ok?:=?g.dependencies[node];?!ok?{
???leaves?=?append(leaves,?node)
??}
?}

?return?leaves
}

最后一塊拼圖實(shí)際上是計(jì)算圖的拓?fù)渑判驅(qū)印＿@也是最復(fù)雜的一塊。我們將遵循的一般策略是迭代地收集葉子并將它們從圖中刪除，直到圖為空。由于我們將對(duì)圖進(jìn)行變異，因此我們希望對(duì)其進(jìn)行克隆，以便在執(zhí)行排序后原始圖仍然完好無(wú)損，因此我們將繼續(xù)實(shí)施該克?。?/p>

func?copyNodeset(s?nodeset)?nodeset?{
?out?:=?make(nodeset,?len(s))
?for?k,?v?:=?range?s?{
??out[k]?=?v
?}
?return?out
}

func?copyDepmap(m?depmap)?depmap?{
?out?:=?make(depmap,?len(m))
?for?k,?v?:=?range?m?{
??out[k]?=?copyNodeset(v)
?}
?return?out
}

func?(g?*Graph)?clone()?*Graph?{
?return?&Graph{
??dependencies:?copyDepmap(g.dependencies),
??dependents:???copyDepmap(g.dependents),
??nodes:????????copyNodeset(g.nodes),
?}
}

我們還需要能夠從圖中刪除一個(gè)節(jié)點(diǎn)和所有邊。刪除節(jié)點(diǎn)很簡(jiǎn)單，就像從每個(gè)節(jié)點(diǎn)刪除出站邊一樣。然而，我們跟蹤兩個(gè)方向的每條邊的事實(shí)意味著我們必須做一些額外的工作來(lái)刪除入站記錄。我們將用于刪除所有邊的策略如下：

1. 在 dependents 中查找節(jié)點(diǎn) A 的條目。這為我們提供了依賴(lài)于 A 的節(jié)點(diǎn)集 。
2. 對(duì)于這些節(jié)點(diǎn)中的每一個(gè)，在 dependencies 中找到條目。從 nodeset 中刪除A。
3. 在 dependents 中刪除節(jié)點(diǎn) A 的條目。
4. 執(zhí)行逆操作，在 dependencies 中查找節(jié)點(diǎn) A 等。

借助一個(gè)允許我們從 depmap 條目中刪除節(jié)點(diǎn)的小實(shí)用程序，我們可以編寫(xiě)從圖中完全刪除節(jié)點(diǎn)的方法。

func?removeFromDepmap(dm?depmap,?key,?node?string)?{
?nodes?:=?dm[key]
?if?len(nodes)?==?1?{
??//?The?only?element?in?the?nodeset?must?be?`node`,?so?we
??//?can?delete?the?entry?entirely.
??delete(dm,?key)
?}?else?{
??//?Otherwise,?remove?the?single?node?from?the?nodeset.
??delete(nodes,?node)
?}
}

func?(g?*Graph)?remove(node?string)?{
?//?Remove?edges?from?things?that?depend?on?`node`.
?for?dependent?:=?range?g.dependents[node]?{
??removeFromDepmap(g.dependencies,?dependent,?node)
?}
?delete(g.dependents,?node)

?//?Remove?all?edges?from?node?to?the?things?it?depends?on.
?for?dependency?:=?range?g.dependencies[node]?{
??removeFromDepmap(g.dependents,?dependency,?node)
?}
?delete(g.dependencies,?node)

?//?Finally,?remove?the?node?itself.
?delete(g.nodes,?node)
}

最后，我們可以實(shí)現(xiàn) Graph.TopoSortedLayers()：

func?(g?*Graph)?TopoSortedLayers()?[][]string?{
?layers?:=?[][]string{}

?//?Copy?the?graph
?shrinkingGraph?:=?g.clone()
?for?{
??leaves?:=?shrinkingGraph.Leaves()
??if?len(leaves)?==?0?{
???break
??}

??layers?=?append(layers,?leaves)
??for?_,?leafNode?:=?range?leaves?{
???shrinkingGraph.remove(leafNode)
??}
?}

?return?layers
}

這種方法清楚地概述了我們對(duì)圖進(jìn)行拓?fù)渑判虻牟呗裕?/p>

1. 克隆圖，以便我們可以對(duì)其進(jìn)行轉(zhuǎn)變。
2. 反復(fù)將圖的葉子收集到輸出的“層”中。
3. 收集后刪除每一層。
4. 當(dāng)圖為空時(shí)，返回收集的圖層。

現(xiàn)在我們可以回到最初的蛋糕制作問(wèn)題，以確保我們的圖為我們解決了這個(gè)問(wèn)題：

package?main

import?(
?"fmt"
?"strings"

?"github.com/kendru/darwin/go/depgraph"
)

func?main()?{
?g?:=?depgraph.New()
?g.DependOn("cake",?"eggs")
?g.DependOn("cake",?"flour")
?g.DependOn("eggs",?"chickens")
?g.DependOn("flour",?"grain")
?g.DependOn("chickens",?"grain")
?g.DependOn("grain",?"soil")
?g.DependOn("grain",?"water")
?g.DependOn("chickens",?"water")

?for?i,?layer?:=?range?g.TopoSortedLayers()?{
??fmt.Printf("%d:?%s\n",?i,?strings.Join(layer,?",?"))
?}
?//?Output:
?//?0:?soil,?water
?//?1:?grain
?//?2:?flour,?chickens
?//?3:?eggs
?//?4:?cake
}

所有這些工作都不是小菜一碟，但現(xiàn)在我們有了一個(gè)依賴(lài)圖，可以用來(lái)對(duì)幾乎任何東西進(jìn)行拓?fù)渑判?。您可?span style="font-weight: bold;color: rgb(60, 112, 198);">在 GitHub 上找到^[1]這篇文章的完整代碼。這個(gè)實(shí)現(xiàn)有一些明顯的限制，我想挑戰(zhàn)你改進(jìn)它，以便它可以：

• 存儲(chǔ)不是簡(jiǎn)單字符串的節(jié)點(diǎn)
• 允許單獨(dú)添加節(jié)點(diǎn)和邊/依賴(lài)信息
• 產(chǎn)生用于調(diào)試的字符串輸出

原文鏈接：https://kendru.github.io/go/2021/10/26/sorting-a-dependency-graph-in-go/

參考資料