Je me suis réveillé en fin d'après-midi et j'ai décidé - c'est tout le temps, il est temps de créer une nouvelle fonctionnalité dans ma bibliothèque . Et pour un et vérifiez le graphique pour les cycles à réparer et à accélérer. Au déjeuner du matin, j'ai créé une nouvelle fonctionnalité, amélioré le code, créé la représentation graphique sous une forme pratique et abordé le problème de la recherche de tous les cycles simples dans le graphique. En sirotant une tasse d'eau froide, j'ai ouvert Google, tapé "rechercher tous les cycles simples dans un graphique" et vu ...

Je n'ai pas vu grand-chose ... même s'il n'était que 4 heures du matin. Quelques liens vers des algorithmes link1 , lien2 , et beaucoup de conseils quec'est l'heure de dormirIl peut y avoir de nombreux cycles dans le graphique et, dans le cas général, le problème ne peut pas être résolu. Et une autre question sur Habré à ce sujet, dont la réponse ne m'a pas sauvé non plus - je connaissais déjà la recherche en profondeur.

Mais une fois que j'ai résolu, alors même NP résoudra un problème difficile dans P , plus je bois d'eau, pas de café - et cela ne peut pas s'arrêter brusquement. Et je savais que dans le cadre de ma tâche, il devrait être possible de trouver tous les cycles en peu de temps, sans supercalculateurs - pas l'ordre de grandeur pour moi.

Faisons une petite parenthèse avec le détective et comprenons pourquoi j'en ai besoin.

Quelle est cette bibliothèque?

La bibliothèque appelée DITranquility est écrite en Swift et sa tâche est d'injecter des dépendances . La bibliothèque fait face à la tâche d'injection de dépendances avec un bang, a des capacités que les autres bibliothèques Swift ne peuvent pas, et le fait avec une bonne vitesse.

Mais pourquoi devrais-je prendre l'habitude de vérifier les boucles dans le graphe de dépendances?

Pour le bien de killerfichi - si la bibliothèque fait la fonctionnalité principale avec un bang, alors vous cherchez des moyens de l'améliorer et de l'améliorer. Un killefic vérifie l'exactitude du graphe de dépendances - c'est un ensemble de vérifications différentes qui vous permettent d'éviter les problèmes pendant l'exécution, ce qui économise du temps de développement. Et la vérification des cycles se distingue séparément de toutes les vérifications, car cette opération prend beaucoup plus de temps. Et jusqu'à récemment, plus de temps non civilisé.

, , , . , "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 .

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(), . .

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

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.

, .

:

Le temps n'a été mesuré que pour la recherche de cycles. Une bibliothèque tierce convertit les données d'entrée en une bibliothèque pratique, mais une telle conversion ne devrait pas prendre plus de 0,1 seconde. Et comme vous pouvez le voir, le temps diffère d'un ordre de grandeur (et dans la libération de deux). Et une telle différence ne peut pas être attribuée à une mise en œuvre non optimale.

• Comme je l'ai écrit, dans ma bibliothèque, les arêtes ne sont pas simplement une transition d'un sommet à un autre. Ces informations ne peuvent pas être transmises à une implémentation tierce, de sorte que le nombre de boucles trouvées ne correspond pas. Pour cette raison, les résultats sont recherchés pour tous les cycles uniques le long des sommets, à l'exclusion des arêtes, afin de s'assurer que le résultat correspond.