{
  "id": "enwiki-001270153872",
  "slug": "rocha-thatte-cycle-detection-algorithm",
  "title": "Rocha–Thatte cycle detection algorithm",
  "qid": "",
  "lead": "Rocha–Thatte algorithm is a distributed algorithm in graph theory for detecting cycles on large-scale directed graphs based on the bulk synchronous message passing abstraction. This algorithm for detecting cycles by message passing is suitable to be implemented in distributed graph processing systems, and it is also suitable for implementations in systems for disk-based computations, such as the GraphChi, where the computation is mainly based on secondary memory. Disk-based computations are necessary when we have a single computer for processing large-scale graphs, and the computation exceeds the primary memory capacity.",
  "body": "Rocha–Thatte algorithm is a distributed algorithm in graph theory for detecting cycles on large-scale directed graphs based on the bulk synchronous message passing abstraction. This algorithm for detecting cycles by message passing is suitable to be implemented in distributed graph processing systems, and it is also suitable for implementations in systems for disk-based computations, such as the GraphChi, where the computation is mainly based on secondary memory. Disk-based computations are necessary when we have a single computer for processing large-scale graphs, and the computation exceeds the primary memory capacity. in two cases: if v = v_1 , then v has detected a cycle, which is reported; if v = v_i for some i \\in {2, 3, \\ldots , k} , then v has detected a sequence that contains the cycle (v = v_i, v_{i+1}, \\ldots , v_k, v_{k+1} = v) ; in this case, the sequence is discarded, since the cycle must have been detected in an earlier iteration; to be precise, this cycle must have been detected in iteration k - i + 1 . Every cycle (v_1, v_2, \\ldots , v_k, v_{k+1} = v_1) is detected by all v_i, i = 1 to k in the same iteration; it is reported by the vertex \\min\\{v_1, \\ldots , v_k\\} . The figure below presents an example of the execution of the algorithm. In iteration i=3 , all the three vertices detect the cycle (2, 3, 4) . The algorithm ensures that the cycle is reported only once by emitting the detected cycle only from the vertex with the least identifier value in the ordered sequence, which is the vertex 2 in the example. The total number of iterations of the algorithm is the number of vertices in the longest path in the graph, plus a few more steps for deactivating the final vertices. During the analysis of the total number of iterations, we ignore the few extra iterations needed for deactivating the final vertices and detecting the end of the computation, since it is O(1) iterations. In practice, the actual number of these final few iterations depends on the framework being used to implement the algorithm.",
  "categories": [
    "23221441",
    "23933915",
    "48254571",
    "61223453"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1270153872",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1737172653.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001270153872",
    "type": "webpage",
    "title": "Rocha–Thatte cycle detection algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/rocha-thatte-cycle-detection-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001270153872",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1270153872",
    "note": "Immutable snapshot enwiki-001270153872"
  }
}