public function SqlGroupGraphStorage::getPath in Subgroup (Graph) 1.0.x

Use the Breadth-first search algoritm to find the path between groups.

Parameters

int $parent_group_id: The ID of the parent group.

int $child_group_id: The ID of the child group.

Return value

array[] An nested array containing a path between the groups.

Overrides GroupGraphStorageInterface::getPath

File

src/Graph/SqlGroupGraphStorage.php, line 569

Class

SqlGroupGraphStorage: SQL based storage of the group relationship graph.

Namespace

Drupal\ggroup\Graph

Code

public function getPath($parent_group_id, $child_group_id) {
  if (!$this
    ->isAncestor($parent_group_id, $child_group_id)) {
    return [];
  }
  $visited = [];
  $solutions = [];

  // Enqueue the origin vertex and mark as visited.
  $queue = new \SplQueue();
  $queue
    ->enqueue($child_group_id);
  $visited[$child_group_id] = TRUE;

  // This is used to track the path back from each node.
  $paths = [];
  $paths[$child_group_id][] = $child_group_id;

  // While queue is not empty and destination not found.
  while (!$queue
    ->isEmpty() && $queue
    ->bottom() != $parent_group_id) {
    $child_id = $queue
      ->dequeue();

    // Make sure the mapping info for the child is loaded.
    $this
      ->loadMap($child_id);

    // Get parents for child in queue.
    if (isset($this->directAncestors[$child_id])) {
      $parent_ids = $this->directAncestors[$child_id];
      foreach ($parent_ids as $parent_id) {
        if ((int) $parent_id === (int) $parent_group_id) {

          // Add this path to the list of solutions.
          $solution = $paths[$child_id];
          $solution[] = $parent_id;
          $solutions[] = $solution;
        }
        else {
          if (!isset($visited[$parent_id])) {

            // If not yet visited, enqueue parent id and mark as visited.
            $queue
              ->enqueue($parent_id);
            $visited[$parent_id] = TRUE;

            // Add parent to current path.
            $paths[$parent_id] = $paths[$child_id];
            $paths[$parent_id][] = $parent_id;
          }
        }
      }
    }
  }
  return $solutions;
}

You are here