public function GraphTest::testDepthFirstSearch in Drupal 10

Same name and namespace in other branches

1. 8 core/tests/Drupal/Tests/Component/Graph/GraphTest.php \Drupal\Tests\Component\Graph\GraphTest::testDepthFirstSearch()
2. 9 core/tests/Drupal/Tests/Component/Graph/GraphTest.php \Drupal\Tests\Component\Graph\GraphTest::testDepthFirstSearch()

Tests depth-first-search features.

File

core/tests/Drupal/Tests/Component/Graph/GraphTest.php, line 17

Class

GraphTest

@coversDefaultClass \Drupal\Component\Graph\Graph @group Graph

Namespace

Drupal\Tests\Component\Graph

Code

public function testDepthFirstSearch() {

  // The sample graph used is:
  // @code
  // 1 --> 2 --> 3     5 ---> 6
  //       |     ^     ^
  //       |     |     |
  //       |     |     |
  //       +---> 4 <-- 7      8 ---> 9
  // @endcode
  $graph = $this
    ->normalizeGraph([
    1 => [
      2,
    ],
    2 => [
      3,
      4,
    ],
    3 => [],
    4 => [
      3,
    ],
    5 => [
      6,
    ],
    7 => [
      4,
      5,
    ],
    8 => [
      9,
    ],
    9 => [],
  ]);
  $graph_object = new Graph($graph);
  $graph = $graph_object
    ->searchAndSort();
  $expected_paths = [
    1 => [
      2,
      3,
      4,
    ],
    2 => [
      3,
      4,
    ],
    3 => [],
    4 => [
      3,
    ],
    5 => [
      6,
    ],
    7 => [
      4,
      3,
      5,
      6,
    ],
    8 => [
      9,
    ],
    9 => [],
  ];
  $this
    ->assertPaths($graph, $expected_paths);
  $expected_reverse_paths = [
    1 => [],
    2 => [
      1,
    ],
    3 => [
      2,
      1,
      4,
      7,
    ],
    4 => [
      2,
      1,
      7,
    ],
    5 => [
      7,
    ],
    7 => [],
    8 => [],
    9 => [
      8,
    ],
  ];
  $this
    ->assertReversePaths($graph, $expected_reverse_paths);

  // Assert that DFS didn't created "missing" vertexes automatically.
  $this
    ->assertFalse(isset($graph[6]), 'Vertex 6 has not been created');
  $expected_components = [
    [
      1,
      2,
      3,
      4,
      5,
      7,
    ],
    [
      8,
      9,
    ],
  ];
  $this
    ->assertComponents($graph, $expected_components);
  $expected_weights = [
    [
      1,
      2,
      3,
    ],
    [
      2,
      4,
      3,
    ],
    [
      7,
      4,
      3,
    ],
    [
      7,
      5,
    ],
    [
      8,
      9,
    ],
  ];
  $this
    ->assertWeights($graph, $expected_weights);
}