[[433885]]

大家好，我是程序員幽鬼。

最近，我在思考在軟件工程中遇到的許多重要問題可以歸結為幾個簡單的問題。只要看看任何關于算法的書，其中的大部分都會是排序或搜索集合的一些變體。谷歌的存在是因為“哪些文檔包含這些短語?”是一個真正難以解決的問題(好吧，這極大地簡化了 Google 產(chǎn)品的龐大范圍，但基本思想仍然成立)。

01 什么是拓撲排序?

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

The dependency graph of cake

該圖的一種可能的拓撲順序是：

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

但是，還有其他可能的拓撲順序：

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

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

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

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

02 構建依賴圖

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

我們已經(jīng)足夠了解開始編寫代碼所需的內(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é)點、“依賴”邊和“依賴于”邊?，F(xiàn)在讓我們考慮創(chuàng)建用于向圖形添加新依賴關系的 API。所有我們需要的是一個聲明的方法，一些節(jié)點依賴于另一個，就像這樣：graph.DependOn("flour", "grain")。有幾種情況我們要明確禁止。首先，一個節(jié)點不能依賴于自己，其次，如果flour依賴于grain，那么grain一定不能依賴于flour，否則我們會創(chuàng)建一個無限的依賴循環(huán)。有了這個，讓我們編寫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{}{} 
} 

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

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 對圖表進行排序

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

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

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 
} 

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

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

在 dependents 中查找節(jié)點 A 的條目。這為我們提供了依賴于 A 的節(jié)點集 。

對于這些節(jié)點中的每一個，在 dependencies 中找到條目。從 nodeset 中刪除A。

在 dependents 中刪除節(jié)點 A 的條目。

執(zhí)行逆操作，在 dependencies 中查找節(jié)點 A 等。

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

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) 
} 

最后，我們可以實現(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 
} 

這種方法清楚地概述了我們對圖進行拓撲排序的策略：

• 克隆圖，以便我們可以對其進行轉(zhuǎn)變。
• 反復將圖的葉子收集到輸出的“層”中。
• 收集后刪除每一層。
• 當圖為空時，返回收集的圖層。

現(xià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)在我們有了一個依賴圖，可以用來對幾乎任何東西進行拓撲排序。您可以在 GitHub 上找到[1]這篇文章的完整代碼。這個實現(xiàn)有一些明顯的限制，我想挑戰(zhàn)你改進它，以便它可以：

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

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

參考資料

[1]在 GitHub 上找到: https://github.com/kendru/darwin/tree/main/go/depgraph

本文轉(zhuǎn)載自微信公眾號「幽鬼」，可以通過以下二維碼關注。轉(zhuǎn)載本文請聯(lián)系幽鬼公眾號。