3 namespace Drupal\Tests\Component\Graph;
5 use Drupal\Component\Graph\Graph;
6 use Drupal\Tests\UnitTestCase;
9 * @coversDefaultClass \Drupal\Component\Graph\Graph
12 class GraphTest extends UnitTestCase {
15 * Test depth-first-search features.
17 public function testDepthFirstSearch() {
18 // The sample graph used is:
19 // 1 --> 2 --> 3 5 ---> 6
23 // +---> 4 <-- 7 8 ---> 9
24 $graph = $this->normalizeGraph([
34 $graph_object = new Graph($graph);
35 $graph = $graph_object->searchAndSort();
47 $this->assertPaths($graph, $expected_paths);
49 $expected_reverse_paths = [
59 $this->assertReversePaths($graph, $expected_reverse_paths);
61 // Assert that DFS didn't created "missing" vertexes automatically.
62 $this->assertFalse(isset($graph[6]), 'Vertex 6 has not been created');
64 $expected_components = [
68 $this->assertComponents($graph, $expected_components);
77 $this->assertWeights($graph, $expected_weights);
84 * A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
87 * The normalized version of a graph.
89 protected function normalizeGraph($graph) {
90 $normalized_graph = [];
91 foreach ($graph as $vertex => $edges) {
92 // Create vertex even if it hasn't any edges.
93 $normalized_graph[$vertex] = [];
94 foreach ($edges as $edge) {
95 $normalized_graph[$vertex]['edges'][$edge] = TRUE;
98 return $normalized_graph;
102 * Verify expected paths in a graph.
105 * A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
106 * @param $expected_paths
107 * An associative array containing vertices with their expected paths.
109 protected function assertPaths($graph, $expected_paths) {
110 foreach ($expected_paths as $vertex => $paths) {
111 // Build an array with keys = $paths and values = TRUE.
112 $expected = array_fill_keys($paths, TRUE);
113 $result = isset($graph[$vertex]['paths']) ? $graph[$vertex]['paths'] : [];
114 $this->assertEquals($expected, $result, sprintf('Expected paths for vertex %s: %s, got %s', $vertex, $this->displayArray($expected, TRUE), $this->displayArray($result, TRUE)));
119 * Verify expected reverse paths in a graph.
122 * A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
123 * @param $expected_reverse_paths
124 * An associative array containing vertices with their expected reverse
127 protected function assertReversePaths($graph, $expected_reverse_paths) {
128 foreach ($expected_reverse_paths as $vertex => $paths) {
129 // Build an array with keys = $paths and values = TRUE.
130 $expected = array_fill_keys($paths, TRUE);
131 $result = isset($graph[$vertex]['reverse_paths']) ? $graph[$vertex]['reverse_paths'] : [];
132 $this->assertEquals($expected, $result, sprintf('Expected reverse paths for vertex %s: %s, got %s', $vertex, $this->displayArray($expected, TRUE), $this->displayArray($result, TRUE)));
137 * Verify expected components in a graph.
140 * A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort().
141 * @param $expected_components
142 * An array containing of components defined as a list of their vertices.
144 protected function assertComponents($graph, $expected_components) {
145 $unassigned_vertices = array_fill_keys(array_keys($graph), TRUE);
146 foreach ($expected_components as $component) {
147 $result_components = [];
148 foreach ($component as $vertex) {
149 $result_components[] = $graph[$vertex]['component'];
150 unset($unassigned_vertices[$vertex]);
152 $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)));
154 $this->assertEquals([], $unassigned_vertices, sprintf('Vertices not assigned to a component: %s', $this->displayArray($unassigned_vertices, TRUE)));
158 * Verify expected order in a graph.
161 * A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
162 * @param $expected_orders
163 * An array containing lists of vertices in their expected order.
165 protected function assertWeights($graph, $expected_orders) {
166 foreach ($expected_orders as $order) {
167 $previous_vertex = array_shift($order);
168 foreach ($order as $vertex) {
169 $this->assertTrue($graph[$previous_vertex]['weight'] < $graph[$vertex]['weight'], sprintf('Weights of %s and %s are correct relative to each other', $previous_vertex, $vertex));
175 * Helper function to output vertices as comma-separated list.
178 * An array containing a list of vertices.
180 * (optional) Whether to output the keys of $paths instead of the values.
182 protected function displayArray($paths, $keys = FALSE) {
183 if (!empty($paths)) {
184 return implode(', ', $keys ? array_keys($paths) : $paths);