001: package test;
002:
003: import java.util.List;
004:
005: import org.testng.annotations.ExpectedExceptions;
006: import org.testng.annotations.Test;
007: import org.testng.internal.Graph;
008:
009: /**
010: * This class
011: *
012: * @author cbeust
013: */
014: public class GraphTest {
015:
016: @Test
017: public void sort() {
018: Graph<String> g = new Graph<String>();
019: g.addNode("3");
020: g.addNode("1");
021: g.addNode("2.2");
022: g.addNode("independent");
023: g.addNode("2.1");
024: g.addNode("2");
025:
026: g.addPredecessor("3", "2");
027: g.addPredecessor("3", "2.1");
028: g.addPredecessor("3", "2.2");
029: g.addPredecessor("2", "1");
030: g.addPredecessor("2.1", "1");
031: g.addPredecessor("2.2", "1");
032:
033: g.topologicalSort();
034: List<String> l = g.getStrictlySortedNodes();
035: int i = 0;
036: assert "1".equals(l.get(i));
037: i++;
038: assert "2".equals(l.get(i)) || "2.1".equals(l.get(i))
039: || "2.2".equals(l.get(i));
040: i++;
041: assert "2".equals(l.get(i)) || "2.1".equals(l.get(i))
042: || "2.2".equals(l.get(i));
043: i++;
044: assert "2".equals(l.get(i)) || "2.1".equals(l.get(i))
045: || "2.2".equals(l.get(i));
046: i++;
047: assert "3".equals(l.get(i));
048:
049: assert 1 == g.getIndependentNodes().size();
050:
051: }
052:
053: @Test
054: @ExpectedExceptions({org.testng.TestNGException.class})
055: public void cycleShouldFail() {
056: Graph<String> g = new Graph<String>();
057: g.addNode("3");
058: g.addNode("2");
059: g.addNode("1");
060:
061: g.addPredecessor("3", "2");
062: g.addPredecessor("2", "1");
063: g.addPredecessor("1", "3");
064:
065: g.topologicalSort();
066: }
067:
068: @Test
069: public void findPredecessors() {
070: Graph<String> g = new Graph<String>();
071: g.addNode("3");
072: g.addNode("1");
073: g.addNode("2.2");
074: g.addNode("independent");
075: g.addNode("2.1");
076: g.addNode("2");
077:
078: // 1 -> 2.1, 2.2, 2.3 --> 3
079: g.addPredecessor("3", "2");
080: g.addPredecessor("3", "2.1");
081: g.addPredecessor("3", "2.2");
082: g.addPredecessor("2", "1");
083: g.addPredecessor("2.1", "1");
084: g.addPredecessor("2.2", "1");
085:
086: // Invoke sort to make sure there is no side effect
087: g.topologicalSort();
088:
089: //
090: // Test findPredecessors
091: //
092: {
093: List<String> predecessors = g.findPredecessors("2");
094: assert predecessors.size() == 1;
095: assert predecessors.get(0).equals("1");
096: }
097:
098: {
099: List<String> predecessors = g.findPredecessors("3");
100:
101: assert predecessors.size() == 4;
102: assert predecessors.get(0).equals("1");
103: assert predecessors.get(1).equals("2.1")
104: || predecessors.get(1).equals("2.2")
105: || predecessors.get(1).equals("2");
106: assert predecessors.get(2).equals("2.1")
107: || predecessors.get(2).equals("2.2")
108: || predecessors.get(2).equals("2");
109: assert predecessors.get(3).equals("2.1")
110: || predecessors.get(3).equals("2.2")
111: || predecessors.get(3).equals("2");
112: }
113: }
114: }
|