test/com/facebook/buck/graph/AbstractBottomUpTraversalTest.java

/*
 * Copyright 2012-present Facebook, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may
 * not use this file except in compliance with the License. You may obtain
 * a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations
 * under the License.
 */

package com.facebook.buck.graph;

import static org.junit.Assert.assertEquals;

import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;

import org.junit.Test;

import java.util.List;
import java.util.Set;

public class AbstractBottomUpTraversalTest {

  @Test
  public void testCrissCrossTraversal() {
    // Build up a graph as follows:
    //     A
    //   /   \
    //  B     C
    //  | \ / |
    //  | / \ |
    //  D     E
    //    \ /
    //     F
    MutableDirectedGraph<String> mutableGraph = new MutableDirectedGraph<String>();
    final Set<String> nodes = ImmutableSet.of("A", "B", "C", "D", "E", "F");
    for (String node : nodes) {
      mutableGraph.addNode(node);
    }
    mutableGraph.addEdge("A", "B");
    mutableGraph.addEdge("A", "C");
    mutableGraph.addEdge("B", "D");
    mutableGraph.addEdge("B", "E");
    mutableGraph.addEdge("C", "D");
    mutableGraph.addEdge("C", "E");
    mutableGraph.addEdge("D", "F");
    mutableGraph.addEdge("E", "F");

    ImmutableDirectedAcyclicGraph<String> immutableGraph =
        new DefaultImmutableDirectedAcyclicGraph<String>(mutableGraph);

    AbstractBottomUpTraversal<String, List<String>> traversal =
        new AbstractBottomUpTraversal<String, List<String>>(immutableGraph) {

      private final List<String> visitedNodes = Lists.newLinkedList();

      @Override
      public void visit(String node) {
        visitedNodes.add(node);
      }

      @Override
      public List<String> getResult() {
        return visitedNodes;
      }
    };
    traversal.traverse();
    List<String> visitedNodes = traversal.getResult();

    assertEquals("F", visitedNodes.get(0));
    assertEquals(ImmutableSet.of("D", "E"), ImmutableSet.copyOf(visitedNodes.subList(1, 3)));
    assertEquals(ImmutableSet.of("B", "C"), ImmutableSet.copyOf(visitedNodes.subList(3, 5)));
    assertEquals("A", visitedNodes.get(5));

    assertEquals(nodes, ImmutableSet.copyOf(visitedNodes));
  }

  @Test
  public void testNodeNotVisitedBeforeItsDependencies() {
    // Build up a graph as follows:
    //         V
    //        / \
    //       W   A
    //      /
    //     X
    //    /
    //   Y
    //  /
    // Z
    MutableDirectedGraph<String> mutableGraph = new MutableDirectedGraph<String>();
    final Set<String> nodes = ImmutableSet.of("A", "V", "W", "X", "Y", "Z");
    for (String node : nodes) {
      mutableGraph.addNode(node);
    }
    mutableGraph.addEdge("V", "W");
    mutableGraph.addEdge("W", "X");
    mutableGraph.addEdge("X", "Y");
    mutableGraph.addEdge("Y", "Z");
    mutableGraph.addEdge("V", "A");

    ImmutableDirectedAcyclicGraph<String> immutableGraph =
        new DefaultImmutableDirectedAcyclicGraph<String>(mutableGraph);
    AbstractBottomUpTraversal<String, List<String>> traversal =
        new AbstractBottomUpTraversal<String, List<String>>(immutableGraph) {

      private final List<String> visitedNodes = Lists.newLinkedList();

      @Override
      public void visit(String node) {
        visitedNodes.add(node);
      }

      @Override
      public List<String> getResult() {
        return visitedNodes;
      }
    };
    traversal.traverse();

    List<String> visitedNodes = traversal.getResult();
    assertEquals("Z and A have no depdencies, so they should be visited first.",
        ImmutableSet.of("Z", "A"),
        ImmutableSet.copyOf(visitedNodes.subList(0, 2)));
    assertEquals("Y", visitedNodes.get(2));
    assertEquals("X", visitedNodes.get(3));
    assertEquals("W", visitedNodes.get(4));
    assertEquals("V should be visited last, after all of its dependencies.",
        "V",
        visitedNodes.get(5));

    assertEquals(nodes, ImmutableSet.copyOf(visitedNodes));
  }
}