Chris@0: <?php
Chris@0: 
Chris@0: namespace Drupal\Tests\Component\Graph;
Chris@0: 
Chris@0: use Drupal\Component\Graph\Graph;
Chris@0: use PHPUnit\Framework\TestCase;
Chris@0: 
Chris@0: /**
Chris@0:  * @coversDefaultClass \Drupal\Component\Graph\Graph
Chris@0:  * @group Graph
Chris@0:  */
Chris@0: class GraphTest extends TestCase {
Chris@0: 
Chris@0:   /**
Chris@0:    * Test depth-first-search features.
Chris@0:    */
Chris@0:   public function testDepthFirstSearch() {
Chris@0:     // The sample graph used is:
Chris@0:     // 1 --> 2 --> 3     5 ---> 6
Chris@0:     //       |     ^     ^
Chris@0:     //       |     |     |
Chris@0:     //       |     |     |
Chris@0:     //       +---> 4 <-- 7      8 ---> 9
Chris@0:     $graph = $this->normalizeGraph([
Chris@0:       1 => [2],
Chris@0:       2 => [3, 4],
Chris@0:       3 => [],
Chris@0:       4 => [3],
Chris@0:       5 => [6],
Chris@0:       7 => [4, 5],
Chris@0:       8 => [9],
Chris@0:       9 => [],
Chris@0:     ]);
Chris@0:     $graph_object = new Graph($graph);
Chris@0:     $graph = $graph_object->searchAndSort();
Chris@0: 
Chris@0:     $expected_paths = [
Chris@0:       1 => [2, 3, 4],
Chris@0:       2 => [3, 4],
Chris@0:       3 => [],
Chris@0:       4 => [3],
Chris@0:       5 => [6],
Chris@0:       7 => [4, 3, 5, 6],
Chris@0:       8 => [9],
Chris@0:       9 => [],
Chris@0:     ];
Chris@0:     $this->assertPaths($graph, $expected_paths);
Chris@0: 
Chris@0:     $expected_reverse_paths = [
Chris@0:       1 => [],
Chris@0:       2 => [1],
Chris@0:       3 => [2, 1, 4, 7],
Chris@0:       4 => [2, 1, 7],
Chris@0:       5 => [7],
Chris@0:       7 => [],
Chris@0:       8 => [],
Chris@0:       9 => [8],
Chris@0:     ];
Chris@0:     $this->assertReversePaths($graph, $expected_reverse_paths);
Chris@0: 
Chris@0:     // Assert that DFS didn't created "missing" vertexes automatically.
Chris@0:     $this->assertFalse(isset($graph[6]), 'Vertex 6 has not been created');
Chris@0: 
Chris@0:     $expected_components = [
Chris@0:       [1, 2, 3, 4, 5, 7],
Chris@0:       [8, 9],
Chris@0:     ];
Chris@0:     $this->assertComponents($graph, $expected_components);
Chris@0: 
Chris@0:     $expected_weights = [
Chris@0:       [1, 2, 3],
Chris@0:       [2, 4, 3],
Chris@0:       [7, 4, 3],
Chris@0:       [7, 5],
Chris@0:       [8, 9],
Chris@0:     ];
Chris@0:     $this->assertWeights($graph, $expected_weights);
Chris@0:   }
Chris@0: 
Chris@0:   /**
Chris@0:    * Normalizes a graph.
Chris@0:    *
Chris@0:    * @param $graph
Chris@0:    *   A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
Chris@0:    *
Chris@0:    * @return array
Chris@0:    *   The normalized version of a graph.
Chris@0:    */
Chris@0:   protected function normalizeGraph($graph) {
Chris@0:     $normalized_graph = [];
Chris@0:     foreach ($graph as $vertex => $edges) {
Chris@0:       // Create vertex even if it hasn't any edges.
Chris@0:       $normalized_graph[$vertex] = [];
Chris@0:       foreach ($edges as $edge) {
Chris@0:         $normalized_graph[$vertex]['edges'][$edge] = TRUE;
Chris@0:       }
Chris@0:     }
Chris@0:     return $normalized_graph;
Chris@0:   }
Chris@0: 
Chris@0:   /**
Chris@0:    * Verify expected paths in a graph.
Chris@0:    *
Chris@0:    * @param $graph
Chris@0:    *   A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
Chris@0:    * @param $expected_paths
Chris@0:    *   An associative array containing vertices with their expected paths.
Chris@0:    */
Chris@0:   protected function assertPaths($graph, $expected_paths) {
Chris@0:     foreach ($expected_paths as $vertex => $paths) {
Chris@0:       // Build an array with keys = $paths and values = TRUE.
Chris@0:       $expected = array_fill_keys($paths, TRUE);
Chris@0:       $result = isset($graph[$vertex]['paths']) ? $graph[$vertex]['paths'] : [];
Chris@0:       $this->assertEquals($expected, $result, sprintf('Expected paths for vertex %s: %s, got %s', $vertex, $this->displayArray($expected, TRUE), $this->displayArray($result, TRUE)));
Chris@0:     }
Chris@0:   }
Chris@0: 
Chris@0:   /**
Chris@0:    * Verify expected reverse paths in a graph.
Chris@0:    *
Chris@0:    * @param $graph
Chris@0:    *   A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
Chris@0:    * @param $expected_reverse_paths
Chris@0:    *   An associative array containing vertices with their expected reverse
Chris@0:    *   paths.
Chris@0:    */
Chris@0:   protected function assertReversePaths($graph, $expected_reverse_paths) {
Chris@0:     foreach ($expected_reverse_paths as $vertex => $paths) {
Chris@0:       // Build an array with keys = $paths and values = TRUE.
Chris@0:       $expected = array_fill_keys($paths, TRUE);
Chris@0:       $result = isset($graph[$vertex]['reverse_paths']) ? $graph[$vertex]['reverse_paths'] : [];
Chris@0:       $this->assertEquals($expected, $result, sprintf('Expected reverse paths for vertex %s: %s, got %s', $vertex, $this->displayArray($expected, TRUE), $this->displayArray($result, TRUE)));
Chris@0:     }
Chris@0:   }
Chris@0: 
Chris@0:   /**
Chris@0:    * Verify expected components in a graph.
Chris@0:    *
Chris@0:    * @param $graph
Chris@0:    *   A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort().
Chris@0:    * @param $expected_components
Chris@0:    *   An array containing of components defined as a list of their vertices.
Chris@0:    */
Chris@0:   protected function assertComponents($graph, $expected_components) {
Chris@0:     $unassigned_vertices = array_fill_keys(array_keys($graph), TRUE);
Chris@0:     foreach ($expected_components as $component) {
Chris@0:       $result_components = [];
Chris@0:       foreach ($component as $vertex) {
Chris@0:         $result_components[] = $graph[$vertex]['component'];
Chris@0:         unset($unassigned_vertices[$vertex]);
Chris@0:       }
Chris@0:       $this->assertEquals(1, count(array_unique($result_components)), sprintf('Expected one unique component for vertices %s, got %s', $this->displayArray($component), $this->displayArray($result_components)));
Chris@0:     }
Chris@0:     $this->assertEquals([], $unassigned_vertices, sprintf('Vertices not assigned to a component: %s', $this->displayArray($unassigned_vertices, TRUE)));
Chris@0:   }
Chris@0: 
Chris@0:   /**
Chris@0:    * Verify expected order in a graph.
Chris@0:    *
Chris@0:    * @param $graph
Chris@0:    *   A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
Chris@0:    * @param $expected_orders
Chris@0:    *   An array containing lists of vertices in their expected order.
Chris@0:    */
Chris@0:   protected function assertWeights($graph, $expected_orders) {
Chris@0:     foreach ($expected_orders as $order) {
Chris@0:       $previous_vertex = array_shift($order);
Chris@0:       foreach ($order as $vertex) {
Chris@0:         $this->assertTrue($graph[$previous_vertex]['weight'] < $graph[$vertex]['weight'], sprintf('Weights of %s and %s are correct relative to each other', $previous_vertex, $vertex));
Chris@0:       }
Chris@0:     }
Chris@0:   }
Chris@0: 
Chris@0:   /**
Chris@0:    * Helper function to output vertices as comma-separated list.
Chris@0:    *
Chris@0:    * @param $paths
Chris@0:    *   An array containing a list of vertices.
Chris@0:    * @param $keys
Chris@0:    *   (optional) Whether to output the keys of $paths instead of the values.
Chris@0:    */
Chris@0:   protected function displayArray($paths, $keys = FALSE) {
Chris@0:     if (!empty($paths)) {
Chris@0:       return implode(', ', $keys ? array_keys($paths) : $paths);
Chris@0:     }
Chris@0:     else {
Chris@0:       return '(empty)';
Chris@0:     }
Chris@0:   }
Chris@0: 
Chris@0: }