class GraphUnitTest

class GraphUnitTest extends DrupalUnitTestCase {
    public static function getInfo() {
        return array(
            'name' => 'Graph',
            'description' => 'Graph handling unit tests.',
            'group' => 'System',
        );
    }
    function setUp() {
        require_once DRUPAL_ROOT . '/includes/graph.inc';
        parent::setUp();
    }
    
    /**
     * Test depth-first-search features.
     */
    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);
    }
    
    /**
     * Return a normalized version of a graph.
     */
    function normalizeGraph($graph) {
        $normalized_graph = array();
        foreach ($graph as $vertex => $edges) {
            // Create vertex even if it hasn't any edges.
            $normalized_graph[$vertex] = array();
            foreach ($edges as $edge) {
                $normalized_graph[$vertex]['edges'][$edge] = TRUE;
            }
        }
        return $normalized_graph;
    }
    
    /**
     * Verify expected paths in a graph.
     *
     * @param $graph
     *   A graph array processed by drupal_depth_first_search().
     * @param $expected_paths
     *   An associative array containing vertices with their expected paths.
     */
    function assertPaths($graph, $expected_paths) {
        foreach ($expected_paths as $vertex => $paths) {
            // Build an array with keys = $paths and values = TRUE.
            $expected = array_fill_keys($paths, TRUE);
            $result = isset($graph[$vertex]['paths']) ? $graph[$vertex]['paths'] : array();
            $this->assertEqual($expected, $result, format_string('Expected paths for vertex @vertex: @expected-paths, got @paths', array(
                '@vertex' => $vertex,
                '@expected-paths' => $this->displayArray($expected, TRUE),
                '@paths' => $this->displayArray($result, TRUE),
            )));
        }
    }
    
    /**
     * Verify expected reverse paths in a graph.
     *
     * @param $graph
     *   A graph array processed by drupal_depth_first_search().
     * @param $expected_reverse_paths
     *   An associative array containing vertices with their expected reverse
     *   paths.
     */
    function assertReversePaths($graph, $expected_reverse_paths) {
        foreach ($expected_reverse_paths as $vertex => $paths) {
            // Build an array with keys = $paths and values = TRUE.
            $expected = array_fill_keys($paths, TRUE);
            $result = isset($graph[$vertex]['reverse_paths']) ? $graph[$vertex]['reverse_paths'] : array();
            $this->assertEqual($expected, $result, format_string('Expected reverse paths for vertex @vertex: @expected-paths, got @paths', array(
                '@vertex' => $vertex,
                '@expected-paths' => $this->displayArray($expected, TRUE),
                '@paths' => $this->displayArray($result, TRUE),
            )));
        }
    }
    
    /**
     * Verify expected components in a graph.
     *
     * @param $graph
     *   A graph array processed by drupal_depth_first_search().
     * @param $expected_components
     *   An array containing of components defined as a list of their vertices.
     */
    function assertComponents($graph, $expected_components) {
        $unassigned_vertices = array_fill_keys(array_keys($graph), TRUE);
        foreach ($expected_components as $component) {
            $result_components = array();
            foreach ($component as $vertex) {
                $result_components[] = $graph[$vertex]['component'];
                unset($unassigned_vertices[$vertex]);
            }
            $this->assertEqual(1, count(array_unique($result_components)), format_string('Expected one unique component for vertices @vertices, got @components', array(
                '@vertices' => $this->displayArray($component),
                '@components' => $this->displayArray($result_components),
            )));
        }
        $this->assertEqual(array(), $unassigned_vertices, format_string('Vertices not assigned to a component: @vertices', array(
            '@vertices' => $this->displayArray($unassigned_vertices, TRUE),
        )));
    }
    
    /**
     * Verify expected order in a graph.
     *
     * @param $graph
     *   A graph array processed by drupal_depth_first_search().
     * @param $expected_orders
     *   An array containing lists of vertices in their expected order.
     */
    function assertWeights($graph, $expected_orders) {
        foreach ($expected_orders as $order) {
            $previous_vertex = array_shift($order);
            foreach ($order as $vertex) {
                $this->assertTrue($graph[$previous_vertex]['weight'] < $graph[$vertex]['weight'], format_string('Weights of @previous-vertex and @vertex are correct relative to each other', array(
                    '@previous-vertex' => $previous_vertex,
                    '@vertex' => $vertex,
                )));
            }
        }
    }
    
    /**
     * Helper function to output vertices as comma-separated list.
     *
     * @param $paths
     *   An array containing a list of vertices.
     * @param $keys
     *   (optional) Whether to output the keys of $paths instead of the values.
     */
    function displayArray($paths, $keys = FALSE) {
        if (!empty($paths)) {
            return implode(', ', $keys ? array_keys($paths) : $paths);
        }
        else {
            return '(empty)';
        }
    }

}