库图标我在傍晚醒来，决定了-这是所有时间，现在是时候在我的图书馆中制作一个新功能了。并检查图表以修复和加快周期。到早上午餐时，我做了一个新功能，改进了代码，以方便的形式制作了图形表示形式，并遇到了在图形中查找所有简单循环的问题。我ing着一杯冷水，打开Google，输入“在图中搜索所有简单的循环”，然后看到...

我没看到什么……虽然只有凌晨四点。指向算法link1，link2的几个链接，以及许多提示，~~该睡觉了~~图中可能有很多循环，通常情况下问题无法解决。关于这个话题的另一个问题是关于哈布雷的问题，这个问题的答案也没有挽救我- 我已经知道了深入的搜索。

但是，一旦我解决了问题，那么即使NP也会解决P中的一个难题，我喝的水会更多，而不是咖啡，而且水也不会突然结束。而且我知道，在我的任务框架内，应该有可能在短时间内找到所有循环，而无需超级计算机-对我而言不是数量级。

让我们脱离侦探，了解我为什么需要它。

这是什么图书馆？

名为DITranquility的库是用Swift编写的，其任务是注入依赖项。该库以爆炸式的方式处理依赖项注入的任务，具有其他Swift库无法做到的功能，并且速度很快。

但是，为什么我要养成在依赖关系图中检查循环的习惯？

为了杀手f-如果该库以爆炸的形式完成主要功能，那么您正在寻找改进和改进它的方法。一个主要的功能是检查依赖关系图的正确性-它是一组不同的检查，可让您避免在运行时出现问题，从而节省了开发时间。周期检查在所有检查中都脱颖而出，因为此操作需要更长的时间。直到最近，还没有文明的时间。

, , , . , "Graph API" . "Graph API" — , :

- . , , , .
, - — graphvis.
.

— , ...

, :

MacBook pro 2019, 2,6 GHz 6-Core i7, 32 Gb, Xcode 11.4, Swift 5.2
Swift 300+ ( )
900
2000
40
7000

debug , release, debug.

, 95 .

3 , .

1.

. , .

, . Graph API , , . . , , , .

, , — . , , , :

— , .
— ,
—

, , , . , — , . — ?

, - :

Graph:
    vertices: [Vertex]
    adjacencyList: [[Edge]]

Vertex:
    more information about vertex

Edge:
    toIndices: [Int]
    information about edge

Vertex , Edge , , .

, . , , , , .

2.

, 4 , , , , , — " , , ". :

func findAllCycles() -> [Cycle] {
  result: [Cycle] = []
  for index in vertices {
    result += findCycles(from: index)
  }

  return result
}

func findCycles(from index: Int) -> [Cycle] {
  result: [Cycle] = []
  dfs(startIndex: index, currentIndex: index, visitedIndices: [], result: &result)

  return result
}

func dfs(startIndex: Int,
         currentIndex: Int,
         // visitedIndices   
         visitedIndices: Set<Int>,
         // result   -  
         result: ref [Cycle]) {
  if currentIndex == startIndex && !visitedIndices.isEmpty {
    result.append(cycle)
    return
  }

  if visitedIndices.contains(currentIndex) {
    return
  }

  visitedIndices += [currentIndex]

  for toIndex in adjacencyList[currentIndex] {
    dfs(startIndex: startIndex, currentIndex: toIndex, visitedIndices: visitedIndices, result: &result)
  }
}

, 10 … , , — - ...

, — ? , ? , dfs , 30 . 900 * 1000000 = 900.000.000 dfs…

? , , … ZZzzz...

3.

, , , , , - … , , , !

, , , , . — , , . , , , - :

func findAllCycles() -> [Cycle] {
  globalVisitedIndices: Set<Int> = []
  result: [Cycle] = []
  for index in vertices {
    if globalVisitedIndices.containts(index) {
      continue
    }
    result += findCycles(from: index, globalVisitedIndices: &globalVisitedIndices)
  }

  return result
}

func findCycles(from index: Int, globalVisitedIndices: ref Set<Int>) -> [Cycle] {
  result: [Cycle] = []
  dfs(currentIndex: index, visitedIndices: [], globalVisitedIndices, &globalVisitedIndices, result: &result)

  return result
}

func dfs(currentIndex: Int,
         // visitedIndices   
         visitedIndices: Set<Int>,
         // globalVisitedIndices   -  
         globalVisitedIndices: ref Set<Int>,
         // result   -  
         result: ref [Cycle]) {

  if visitedIndices.contains(currentIndex) {
    //  visitedIndices ,   ,     
    result.append(cycle)
    return
  }

  visitedIndices += [currentIndex]

  for toIndex in adjacencyList[currentIndex] {
    dfs(currentIndex: toIndex, visitedIndices: visitedIndices, globalVisitedIndices: &globalVisitedIndices, result: &result)
  }
}

" , " … . 10 , , , , :

, , , .
"" — , .

, . , , .

4.

, . , , , , , , . , ? . , , run… , — , … , … … , . :

if visitedIndices.contains(currentIndex) {

, , . :

B->E->C , if . , :

A->B->E->C->B!.. C, . A->B->D->A.

A->C->B->D->A , C .

, dfs , .

5.

, . , , , dfs 30 , 1-2 . :

"Big" - , A.

! Big C, , A B, , C , , A.

? , , , . . O(N^2) , .

, :

func findAllCycles() -> [Cycle] {
  reachableIndices: [Set<Int>] = findAllReachableIndices()
  result: [Cycle] = []
  for index in vertices {
    result += findCycles(from: index, reachableIndices: &reachableIndices)
  }

  return result
}

func findAllReachableIndices() -> [Set<Int>] {
  reachableIndices: [Set<Int>] = []
  for index in vertices {
    reachableIndices[index] = findAllReachableIndices(for: index)
  }
  return reachableIndices
}

func findAllReachableIndices(for startIndex: Int) -> Set<Int> {
  visited: Set<Int> = []
  stack: [Int] = [startIndex]
  while fromIndex = stack.popFirst() {
    visited.insert(fromIndex)

    for toIndex in adjacencyList[fromIndex] {
      if !visited.contains(toIndex) {
        stack.append(toIndex)
      }
    }
  }

  return visited
}

func findCycles(from index: Int, reachableIndices: ref [Set<Int>]) -> [Cycle] {
  result: [Cycle] = []
  dfs(startIndex: index, currentIndex: index, visitedIndices: [], reachableIndices: &reachableIndices, result: &result)

  return result
}

func dfs(startIndex: Int,
         currentIndex: Int,
         visitedIndices: Set<Int>,
         reachableIndices: ref [Set<Int>],
         result: ref [Cycle]) {
  if currentIndex == startIndex && !visitedIndices.isEmpty {
    result.append(cycle)
    return
  }

  if visitedIndices.contains(currentIndex) {
    return
  }

  if !reachableIndices[currentIndex].contains(startIndex) {
    return
  }

  visitedIndices += [currentIndex]

  for toIndex in adjacencyList[currentIndex] {
    dfs(startIndex: startIndex, currentIndex: toIndex, visitedIndices: visitedIndices, result: &result)
  }
}

, , , 5 — . — 15 , 6-7 . , , , — .

6. ?

, , — - . , , - .

, , , .

— " , , , ?". . 5 .

, 250, , , :

func findAllCycles() -> [Cycle] {
  reachableIndices: [Set<Int>] = findAllReachableIndices()
  result: [Cycle] = []
  for index in vertices {
    result += findCycles(from: index, reachableIndices: &reachableIndices)
  }

  return result
}

func findAllReachableIndices() -> [Set<Int>] {
  reachableIndices: [Set<Int>] = []
  for index in vertices {
    reachableIndices[index] = findAllReachableIndices(for: index)
  }
  return reachableIndices
}

func findAllReachableIndices(for startIndex: Int) -> Set<Int> {
  visited: Set<Int> = []
  stack: [Int] = [startIndex]
  while fromIndex = stack.popFirst() {
    visited.insert(fromIndex)

    for toIndex in adjacencyList[fromIndex] {
      if !visited.contains(toIndex) {
        stack.append(toIndex)
      }
    }
  }

  return visited
}

func findCycles(from index: Int, reachableIndices: ref [Set<Int>]) -> [Cycle] {
  result: [Cycle] = []
  dfs(startIndex: index, currentIndex: index, visitedIndices: [], reachableIndices: &reachableIndices, result: &result)

  return result
}

func dfs(startIndex: Int,
         currentIndex: Int,
         visitedIndices: Set<Int>,
         reachableIndices: ref [Set<Int>],
         result: ref [Cycle]) {
  if currentIndex == startIndex && !visitedIndices.isEmpty {
    result.append(cycle)
    return
  }

  if visitedIndices.contains(currentIndex) {
    return
  }

  if currentIndex < startIndex || !reachableIndices[currentIndex].contains(startIndex) {
    return
  }

  visitedIndices += [currentIndex]

  for toIndex in adjacencyList[currentIndex] {
    dfs(startIndex: startIndex, currentIndex: toIndex, visitedIndices: visitedIndices, result: &result)
  }
}

: if currentIndex < startIndex.

, run, , — … 6 ? , … .

, , , . — , A, , A . A, .

, , /.

— , . 5-10% .

6.

5-6 , , ! . , Swift , .

, , 6 … , . — " ? ...". — . — , .

3 , , . , Apple , (, , ). Swift popLast(), . .

( Swift)

var visited: Set<Int> = []
var stack: [Int] = [startVertexIndex]
while let fromIndex = stack.first {
  stack.removeFirst()

  visited.insert(fromIndex)
  for toIndex in graph.adjacencyList[fromIndex].flatMap({ $0.toIndices }) {
    if !visited.contains(toIndex) {
      stack.append(toIndex)
    }
  }
}

return visited

c ( Swift)

var visited: Set<Int> = []
var stack: [Int] = [startVertexIndex]
while let fromIndex = stack.popLast() {
  visited.insert(fromIndex)
  for toIndex in graph.adjacencyList[fromIndex].flatMap({ $0.toIndices }) {
    if !visited.contains(toIndex) {
      stack.insert(toIndex, at: 0)
    }
  }
}

return visited

, , — , Swift 5-10%.

? — 95 , 2.5-3 , .

, , — .

, , 15 , .

— , , , .

Swift .

, , , .

, "" -. , - :

graphvis — .
— , , , .
, .

P.S. 5 , . , 1.5 — 4.5 . .

P.P.S. , . , , //.

UPD: . dot , .

.

UPD: banshchikov Donald B. Johnson. swift.

, .

:

_
(debug)	2.4-2.5	36.2-44.5
()	0.25-0.33	32.1-36.4
	6920*	5736
*	5736	5736

仅针对搜索循环测量时间。第三方库可将输入数据转换为方便的数据，但这种转换应不超过0.1秒。如您所见，时间相差一个数量级（释放时相差两个）。如此大的差异不能归因于非最佳实现。

如我所写，在库中，边不仅仅是从一个顶点到另一个顶点的过渡。此类信息无法传递给第三方实现，因此找到的循环数不匹配。因此，在结果中搜索沿顶点的所有唯一循环（不包括边），以确保结果匹配。

我如何寻找简单的循环

这是什么图书馆？

但是，为什么我要养成在依赖关系图中检查循环的习惯？

1.

2.

3.

4.

5.

6. ?

6.

More articles: