function GraphUnitTest::testDepthFirstSearch

Test depth-first-search features.

File

drupal/modules/simpletest/tests/graph.test, line 28

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(),
  ));
  drupal_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);
}