src/test/java/test/GraphTest.java

package test;

import org.testng.Assert;
import org.testng.TestNGException;
import org.testng.annotations.Test;
import org.testng.internal.Graph;
import org.testng.internal.Tarjan;

import java.util.List;


/**
 * This class
 *
 * @author cbeust
 */
public class GraphTest {

  @Test
  public void sort() {
    Graph<String> g = new Graph<>();
    g.addNode("3");
    g.addNode("1");
    g.addNode("2.2");
    g.addNode("independent");
    g.addNode("2.1");
    g.addNode("2");

    g.addPredecessor("3", "2");
    g.addPredecessor("3", "2.1");
    g.addPredecessor("3", "2.2");
    g.addPredecessor("2", "1");
    g.addPredecessor("2.1", "1");
    g.addPredecessor("2.2", "1");

    g.topologicalSort();
    List<String> l = g.getStrictlySortedNodes();
    int i = 0;
    Assert.assertTrue("1".equals(l.get(i)));
    i++;
    Assert.assertTrue("2".equals(l.get(i)) || "2.1".equals(l.get(i)) || "2.2".equals(l.get(i)));
    i++;
    Assert.assertTrue("2".equals(l.get(i)) || "2.1".equals(l.get(i)) || "2.2".equals(l.get(i)));
    i++;
    Assert.assertTrue("2".equals(l.get(i)) || "2.1".equals(l.get(i)) || "2.2".equals(l.get(i)));
    i++;
    Assert.assertTrue("3".equals(l.get(i)));

    Assert.assertTrue(1 == g.getIndependentNodes().size());
  }

  @Test(expectedExceptions = org.testng.TestNGException.class)
  public void cycleShouldFail() {
    Graph<String> g = createCyclicGraph();
    g.topologicalSort();
  }

  @Test
  public void cycleShouldBeCorrect() {
    Graph<String> g = null;
    try {
      g = createCyclicGraph();
      g.topologicalSort();
    }
    catch(TestNGException ex) {
      Tarjan<String> t = new Tarjan<>(g, "1");
      Assert.assertEquals(t.getCycle().size(), 3);
    }

  }

  private Graph<String> createCyclicGraph() {
    Graph<String> g = new Graph<>();
    g.addNode("3");
    g.addNode("2");
    g.addNode("1");

    g.addPredecessor("3", "2");
    g.addPredecessor("2", "1");
    g.addPredecessor("1", "3");

    return g;
  }

  @Test
  public void findPredecessors() {
    Graph<String> g = new Graph<>();
    g.addNode("3");
    g.addNode("1");
    g.addNode("2.2");
    g.addNode("independent");
    g.addNode("2.1");
    g.addNode("2");

    // 1 ->  2.1, 2.2, 2.3 --> 3
    g.addPredecessor("3", "2");
    g.addPredecessor("3", "2.1");
    g.addPredecessor("3", "2.2");
    g.addPredecessor("2", "1");
    g.addPredecessor("2.1", "1");
    g.addPredecessor("2.2", "1");

    // Invoke sort to make sure there is no side effect
    g.topologicalSort();

    //
    // Test findPredecessors
    //
    {
      List<String> predecessors = g.findPredecessors("2");
      Assert.assertTrue(predecessors.size() == 1);
      Assert.assertTrue(predecessors.get(0).equals("1"));
    }

    {
      List<String> predecessors = g.findPredecessors("3");

      Assert.assertTrue(predecessors.size() == 4);
      Assert.assertTrue(predecessors.get(0).equals("1"));
      Assert.assertTrue(predecessors.get(1).equals("2.1")
        || predecessors.get(1).equals("2.2")
        || predecessors.get(1).equals("2"));
      Assert.assertTrue(predecessors.get(2).equals("2.1")
        || predecessors.get(2).equals("2.2")
        || predecessors.get(2).equals("2"));
      Assert.assertTrue(predecessors.get(3).equals("2.1")
        || predecessors.get(3).equals("2.2")
        || predecessors.get(3).equals("2"));
    }
  }

  // Using an earlier implementation of Graph.findPrecessors, finding
  // predecessors in certain kinds of graphs where many nodes have the
  // same predecessors could be very slow, since the old implementation
  // would explore the same nodes repeatedly.  This situation could
  // happen when test methods are organized in several groups, with
  // dependsOnGroups annotations so that each method in one group depends
  // on all of the methods in another group.  If there were several
  // such groups depending on each other in a chain, the combinatorics
  // of the old method became excessive.  This test builds a 72-node graph that
  // emulates this situation, then call Graph.findPredecessors.  The old
  // implementation run this in 70+ seconds on my computer, the new implementation
  // takes a few milliseconds.  In practice, with larger graphs, the former
  // slowness could get very extreme, taking hours or more to complete
  // in some real user situations.
  //
  @Test(timeOut = 5000) // If this takes more than 5 seconds we've definitely regressed.
  public void findPredecessorsTiming() {
    Graph<String> g = new Graph<>();

    final String rootNode = "myroot";
    final String independentNode = "independent";
    g.addNode(rootNode);
    g.addNode(independentNode);

    final int maxDepth = 7;
    final int nodesPerDepth = 10; // must be < 100
    //
    // Add maxDepth groups of new nodes, where each group contains nodesPerDepth
    // nodes, and each node in a group a depth N has each node in the group
    // at depth (N-1) as a predecessor.
    //
    for (int depth = 1; depth <= maxDepth; depth++) {
      for (int i = 0; i < nodesPerDepth; i++) {
        String newNode = String.valueOf(i + (100 * depth));
        g.addNode(newNode);
        if (depth == 1) {
          continue;
        }
        for (int j = 0; j < nodesPerDepth; j++) {
          String prevNode = String.valueOf(j + (100 * (depth - 1)));
          g.addPredecessor(newNode, prevNode);
        }
      }
    }

    // Finally, make all of the nodes in the group at depth maxDepth
    // be predecessors of rootNode.
    //
    for (int i = 0; i < nodesPerDepth; i++) {
      String node = String.valueOf(i + (100 * maxDepth));
      g.addPredecessor(rootNode, node);
    }

    // Now we're done building the graph, which has (maxDepth * nodesPerDepth) + 2
    // nodes.  rootNode has all of the other nodes except independentNode
    // as predecessors.

    //
    // Test findPredecessors
    //
    {
      List<String> predecessors = g.findPredecessors(rootNode);
      Assert.assertTrue(predecessors.size() == (maxDepth * nodesPerDepth));
    }
  }
}