在 Go 中對依賴圖進行排序

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

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

01 什麼是拓撲排序?

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

圖片

The dependency graph of cake

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

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

但是,還有其他可能的拓撲順序:

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

我們也可以把麪粉放在雞蛋後面,因爲唯一依賴雞蛋的就是蛋糕。由於我們可以重新排列項目,我們還可以並行完成其中一些項目,同時保持任何項目都不會出現在依賴於它的任何東西之前。例如,通過添加一層嵌套,我們可以表明內部切片中的所有內容都獨立於該切片中的其他任何內容:

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

從這個圖中,我們得到了一個很好的 “執行計劃”,用於爲蛋糕準備依賴項。首先,我們需要找到一些土壤和水。接下來,我們種植穀物。然後,我們同時養一些雞和做麪粉,收集雞蛋。最後,我們可以做蛋糕了!對於小於四歲的人來說,這似乎是一項艱鉅的工作,但好的事情需要時間。

02 構建依賴圖

現在我們瞭解了要做什麼,讓我們考慮如何編寫一些能夠構建這種依賴項列表的代碼。我們當然需要跟蹤元素本身,我們需要跟蹤什麼取決於什麼。爲了使兩者都 “取決於什麼X?” 和 “X取決於什麼?” 高效,我們將跟蹤兩個方向的依賴關係。

我們已經足夠了解開始編寫代碼所需的內容:

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

這種數據結構應該適合我們的目的,因爲它包含我們需要的所有信息:節點、“依賴”邊和 “依賴於” 邊。現在讓我們考慮創建用於向圖形添加新依賴關係的 API。所有我們需要的是一個聲明的方法,一些節點依賴於另一個,就像這樣:graph.DependOn("flour", "grain")。有幾種情況我們要明確禁止。首先,一個節點不能依賴於自己,其次,如果flour依賴於grain,那麼grain一定不能依賴於flour,否則我們會創建一個無限的依賴循環。有了這個,讓我們編寫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{}{}
}

一旦我們實現,這將有效地爲我們的圖表添加依賴關係Graph.DependsOn()。我們可以很容易地判斷一個節點是否直接依賴於其他某個節點,但我們也想知道是否存在傳遞依賴。例如,由於flour依賴於grain並且grain依賴於soil,因此也flour依賴於soil。這將要求我們獲取節點的直接依賴項,然後對於這些依賴項中的每一個,獲取其依賴項等等,直到我們停止發現新的依賴項。用計算機科學術語來說,我們正在計算一個固定點,以在我們的圖上找到 “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 對圖表進行排序

現在我們有了一個圖數據結構,可以考慮如何按照拓撲順序將節點取出。如果我們可以發現葉節點—即,節點本身對其他節點沒有依賴關係—那麼我們可以重複獲取葉子並將它們從圖中移除,直到圖爲空。在第一次迭代中,我們將找到獨立的元素,然後在隨後的每次迭代中,我們將找到僅依賴於已刪除元素的節點。最終結果將是一個按拓撲排序的獨立 “層” 節點的切片。

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

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
}

最後一塊拼圖實際上是計算圖的拓撲排序層。這也是最複雜的一塊。我們將遵循的一般策略是迭代地收集葉子並將它們從圖中刪除,直到圖爲空。由於我們將對圖進行變異,因此我們希望對其進行克隆,以便在執行排序後原始圖仍然完好無損,因此我們將繼續實施該克隆:

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

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

  1. dependents 中查找節點 A 的條目。這爲我們提供了依賴於 A 的節點集 。

  2. 對於這些節點中的每一個,在 dependencies 中找到條目。從 nodeset 中刪除A

  3. dependents 中刪除節點 A 的條目。

  4. 執行逆操作,在 dependencies 中查找節點 A 等。

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

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

最後,我們可以實現 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
}

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

  1. 克隆圖,以便我們可以對其進行轉變。

  2. 反覆將圖的葉子收集到輸出的 “層” 中。

  3. 收集後刪除每一層。

  4. 當圖爲空時,返回收集的圖層。

現在我們可以回到最初的蛋糕製作問題,以確保我們的圖爲我們解決了這個問題:

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
}

所有這些工作都不是小菜一碟,但現在我們有了一個依賴圖,可以用來對幾乎任何東西進行拓撲排序。您可以在 GitHub 上找到 [1] 這篇文章的完整代碼。這個實現有一些明顯的限制,我想挑戰你改進它,以便它可以:

原文鏈接: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


本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/42fDp-ri1CcEVNQLyp8KQQ