Ich bin am späten Nachmittag aufgewacht und habe beschlossen, dass es Zeit ist, eine neue Funktion in meiner Bibliothek zu erstellen . Und zum einen und überprüfen Sie die Grafik auf Zyklen, um sie zu reparieren und zu beschleunigen. Bis zum Mittagessen am Morgen habe ich eine neue Funktion erstellt, den Code verbessert, die Diagrammdarstellung in einer praktischen Form erstellt und bin auf das Problem gekommen, alle einfachen Zyklen im Diagramm zu finden. Ich nippte an einer Tasse kaltem Wasser, öffnete Google, tippte "Suche nach allen einfachen Zyklen in einer Grafik" ein und sah ...

Ich habe nicht viel gesehen ... obwohl es erst 4 Uhr morgens war. Ein paar Links zu den Algorithmen link1 , link2 und viele Hinweise daraufEs ist Zeit zu schlafenDas Diagramm kann viele Zyklen enthalten, und im allgemeinen Fall ist das Problem nicht lösbar. Und noch eine Frage zu Habré zu diesem Thema, deren Antwort mich auch nicht rettete - ich wusste bereits gründlich über die Suche Bescheid.

Aber sobald ich gelöst habe, wird sogar NP ein schwieriges Problem in P lösen , je mehr ich Wasser trinke, nicht Kaffee - und es kann nicht abrupt enden. Und ich wusste, dass es im Rahmen meiner Aufgabe möglich sein sollte, alle Zyklen in kurzer Zeit ohne Supercomputer zu finden - nicht in der Größenordnung für mich.

Lassen Sie uns ein wenig vom Detektiv abschweifen und verstehen, warum ich es brauche.

Was ist diese Bibliothek?

Die Bibliothek mit dem Namen DITranquility ist in Swift geschrieben und hat die Aufgabe , Abhängigkeiten einzufügen . Die Bibliothek bewältigt die Aufgabe der Abhängigkeitsinjektion mit einem Knall, verfügt über Funktionen, die andere Swift-Bibliotheken nicht können, und erledigt dies mit guter Geschwindigkeit.

Aber warum sollte ich es mir zur Gewohnheit machen, im Abhängigkeitsdiagramm nach Schleifen zu suchen?

Um Killerfichi willen - wenn die Bibliothek die Hauptfunktionalität mit einem Knall erledigt, suchen Sie nach Möglichkeiten, sie zu verbessern und zu verbessern. Ein Killefic überprüft das Abhängigkeitsdiagramm auf Richtigkeit. Es handelt sich um eine Reihe verschiedener Überprüfungen, mit denen Sie Probleme zur Laufzeit vermeiden können, was Entwicklungszeit spart. Die Prüfung auf Zyklen fällt bei allen Prüfungen getrennt auf, da dieser Vorgang viel länger dauert. Und bis vor kurzem unzivilisiert mehr Zeit.

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

, .

:

Die Zeit wurde nur für die Suche nach Zyklen gemessen. Eine Bibliothek eines Drittanbieters konvertiert die Eingabedaten in eine praktische, eine solche Konvertierung sollte jedoch nicht länger als 0,1 Sekunden dauern. Und wie Sie sehen können, unterscheidet sich die Zeit um eine Größenordnung (und in der Veröffentlichung um zwei). Und ein so großer Unterschied kann nicht auf eine nicht optimale Implementierung zurückgeführt werden.

• Wie ich in meiner Bibliothek schrieb, sind Kanten nicht nur ein Übergang von einem Scheitelpunkt zum anderen. Solche Informationen können nicht an eine Implementierung eines Drittanbieters weitergegeben werden, sodass die Anzahl der gefundenen Schleifen nicht übereinstimmt. Aus diesem Grund werden die Ergebnisse nach allen eindeutigen Zyklen entlang der Scheitelpunkte mit Ausnahme der Kanten durchsucht, um sicherzustellen, dass das Ergebnis übereinstimmt.