function GraphTest::testDepthFirstSearch

Tests depth-first-search features.

File

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

Class

GraphTest

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

Namespace

Code

public function testDepthFirstSearch() : void {
    // 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);
}