رمز المكتبة استيقظت في وقت متأخر بعد الظهر وقررت - لقد حان الوقت دائمًا لإنشاء ميزة جديدة في مكتبتي . واحد وتحقق من الرسم البياني لدورات لإصلاح وتسريع. في غداء الصباح ، قمت بعمل ميزة جديدة ، وقمت بتحسين الرمز ، وتمثيل الرسم البياني في شكل مناسب ، وتوصلت إلى مشكلة العثور على جميع الدورات البسيطة في الرسم البياني. احتجت كوبًا من الماء البارد ، فتحت Google ، وكتبت "البحث عن جميع الدورات البسيطة في رسم بياني" ورأيت ...

لم أر الكثير ... على الرغم من أنها كانت الساعة الرابعة صباحا فقط. زوجان من وصلات إلى الخوارزميات LINK1 ، LINK2 ، والكثير من التلميحات التي~~إنه وقت النوم~~يمكن أن يكون هناك العديد من الدورات في الرسم البياني ، وفي الحالة العامة ، لا يمكن حل المشكلة. وسؤال آخر حول حبري حول هذا الموضوع ، لم يخلصني الجواب عليه أيضًا - لقد عرفت بالفعل البحث بعمق.

ولكن بمجرد حلها ، حتى NP سيحل مشكلة صعبة في P ، كلما شربت الماء أكثر ، وليس القهوة - ولا يمكن أن تنتهي فجأة. وأدركت أنه في إطار مهمتي ، يجب أن يكون من الممكن العثور على جميع الدورات في وقت قصير ، بدون أجهزة كمبيوتر فائقة العمق - وليس ترتيب الحجم بالنسبة لي.

دعونا نتطرق قليلا من المخبر ، ونفهم لماذا أحتاج إليه.

ما هذه المكتبة؟

تمت كتابة المكتبة المسماة DITranquility في Swift ومهمتها حقن التبعيات . تتواءم المكتبة مع مهمة حقن التبعية مع الانفجار ، ولديها قدرات لا تستطيع مكتبات Swift الأخرى القيام بها ، وبسرعة جيدة.

ولكن لماذا يجب أن أعتاد على التحقق من وجود حلقات في الرسم البياني للتبعية؟

من أجل killerfichi - إذا كانت المكتبة تقوم بالوظيفة الرئيسية مع ضجة ، فأنت تبحث عن طرق لتحسينها وجعلها أفضل. يقوم killefic بفحص الرسم البياني للتبعية للتأكد من صحته - إنه مجموعة من الفحوصات المختلفة التي تسمح لك بتجنب المشاكل أثناء التنفيذ ، مما يوفر وقت التطوير. ويبرز التحقق من الدورات بشكل منفصل بين جميع الفحوصات ، حيث تستغرق هذه العملية وقتًا أطول. وحتى وقت قريب ، المزيد من الوقت غير المتحضر.

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