vacilando / php-tarjan Goto Github PK

// Class usage:
// $tarjanLoopDetector = new TarjanLoopDetector($adjacencyMatrix);
// $tarjanLoopDetector->setLoopVertexSeparator('-');  // unnecessary
// $tarjanLoopDetector->setMaxLoopLength(3); // unnecessary
// $loops = $tarjanLoopDetector->php_tarjan_entry();
// $result = [];
// foreach ($loops as $loop) {
//  $result []= explode($tarjanLoopDetector->getLoopVertexSeparator(), $loop);
// }

<?php

/**
 * Code origin:
 * https://www.vacilando.org/article/php-implementation-tarjans-cycle-detection-algorithm
 * https://github.com/Vacilando/php-tarjan
 *
 * Adjacency Matrix:
 * https://www.geeksforgeeks.org/graph-and-its-representations/
 */
class TarjanLoopDetector
{

  private $cycles = [];
  private $marked = [];
  private $marked_stack = [];
  private $point_stack = [];
  private $G = [];
  private $loopVertexSeparator = '|';
  private $maxLoopLength = null; // For example 3

  public function __construct($adjacencyMatrix)
  {
    $this->G = $adjacencyMatrix;
  }

  public function setLoopVertexSeparator($loopVertexSeparator)
  {
    $this->loopVertexSeparator = $loopVertexSeparator;
  }

  public function getLoopVertexSeparator()
  {
    return $this->loopVertexSeparator;
  }

  /**
   * Set a value to Limit the length of loops to keep in the results
   * @param $maxLoopLength
   * @return void
   */
  public function setMaxLoopLength($maxLoopLength)
  {
    $this->maxLoopLength = (int)$maxLoopLength;
  }

  public function getMaxLoopLength()
  {
    return $this->maxLoopLength;
  }

  public function php_tarjan_entry()
  {
    foreach ($this->G as $x => $data) {
      $this->marked[$x] = FALSE;
    }

    foreach ($this->G as $i => $data) {
      $this->php_tarjan($i, $i);
      while (!empty($this->marked_stack)) {
        $this->marked[array_pop($this->marked_stack)] = FALSE;
      }
      //echo '<br>'.($i+1).' / '.count($this->G); // Enable if you wish to follow progression through the array rows.
    }

    $this->cycles = array_keys($this->cycles);

    return $this->cycles;
  }

  /*
   * Recursive function to detect strongly connected components (cycles, loops).
   */
  private function php_tarjan($s, $v)
  {

    $f = FALSE;
    $this->point_stack[] = $v;
    $this->marked[$v] = TRUE;
    $this->marked_stack[] = $v;

    foreach ($this->G[$v] as $w) {
      if ($w < $s) {
        $this->G[$w] = array(); // Users note: Why is this array modified?
      } else if ($w == $s) {
        if ($this->maxLoopLength == null || count($this->point_stack) == $this->maxLoopLength) {
          // Collect cycles of a given length only.
          // Add new cycles as array keys to avoid duplication. Way faster than using array_search.
          $this->cycles[implode($this->loopVertexSeparator, $this->point_stack)] = TRUE;
        }
        $f = TRUE;
      } else if ($this->marked[$w] === FALSE) {
        if ($this->maxLoopLength == null || count($this->point_stack) < $this->maxLoopLength) {
          // Collect cycles up to $this->maxLoopLength.
          $g = $this->php_tarjan($s, $w);
        }
        if (!empty($f) or !empty($g)) {
          $f = TRUE;
        }
      }
    }

    if ($f === TRUE) {
      while (end($this->marked_stack) != $v) {
        $this->marked[array_pop($this->marked_stack)] = FALSE;
      }
      array_pop($this->marked_stack);
      $this->marked[$v] = FALSE;
    }

    array_pop($this->point_stack);
    return $f;
  }

}