function GraphUnitTest::testDepthFirstSearch

Test depth-first-search features.

File

core/modules/simpletest/tests/graph.test, line 19

Provides unit tests for graph.inc.

Class

GraphUnitTest

Unit tests for the graph handling features.

Code

function testDepthFirstSearch() {
  // The sample graph used is:
  // 1 --> 2 --> 3     5 ---> 6
  //       |     ^     ^
  //       |     |     |
  //       |     |     |
  //       +---> 4 <-- 7      8 ---> 9
  $graph = $this->normalizeGraph(array(
    1 => array(2),
    2 => array(3, 4),
    3 => array(),
    4 => array(3),
    5 => array(6),
    7 => array(4, 5),
    8 => array(9),
    9 => array(),
  ));
  backdrop_depth_first_search($graph);

  $expected_paths = array(
    1 => array(2, 3, 4),
    2 => array(3, 4),
    3 => array(),
    4 => array(3),
    5 => array(6),
    7 => array(4, 3, 5, 6),
    8 => array(9),
    9 => array(),
  );
  $this->assertPaths($graph, $expected_paths);

  $expected_reverse_paths = array(
    1 => array(),
    2 => array(1),
    3 => array(2, 1, 4, 7),
    4 => array(2, 1, 7),
    5 => array(7),
    7 => array(),
    8 => array(),
    9 => array(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 = array(
    array(1, 2, 3, 4, 5, 7),
    array(8, 9),
  );
  $this->assertComponents($graph, $expected_components);

  $expected_weights = array(
    array(1, 2, 3),
    array(2, 4, 3),
    array(7, 4, 3),
    array(7, 5),
    array(8, 9),
  );
  $this->assertWeights($graph, $expected_weights);
}