Поиск пути Java в общих деревьях — часть 4/4: модульные тесты

Question

Поиск путей Java в общих деревьях. Часть 1/4: классы моделей
Поиск пути Java в общих деревьях — Часть 2/4: алгоритмы
Поиск пути Java в общих деревьях — часть 3/4: демонстрация
Поиск пути Java в общих деревьях — часть 4/4: модульные тесты (этот пост)

В этом посте представлены модульные тесты.

com.github.coderodde.pathfinding.AbstractIDDFSPathfinderTest.java:

package com.github.coderodde.pathfinding;

import static org.junit.Assert.assertEquals;
import org.junit.Test;

public abstract class AbstractIDDFSPathfinderTest extends AbstractPathfinderTest {

    protected Pathfinder iddfsPathfinder;

    @Test(expected = PathNotFoundException.class)
    public void throwsOnDepthExceeded() {
        iddfsPathfinder = 
            new BidirectionalIterativeDeepeningDepthFirstSearchPathfinder(2);

        tree.addTreeNode(0);
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        tree.addTreeNode(3);

        tree.connect(0, 1, 1.0);
        tree.connect(1, 2, 1.0);
        tree.connect(2, 3, 1.0);

        iddfsPathfinder.search(tree, 0, 3);
    }

    @Test
    public void completesProperlyOnSuffcientDepth() {
        iddfsPathfinder = 
            new BidirectionalIterativeDeepeningDepthFirstSearchPathfinder(3);

        WeightedTree.WeightedTreeNode node0 = tree.addTreeNode(0);
        WeightedTree.WeightedTreeNode node1 = tree.addTreeNode(1);
        WeightedTree.WeightedTreeNode node2 = tree.addTreeNode(2);
        WeightedTree.WeightedTreeNode node3= tree.addTreeNode(3);

        tree.connect(0, 1, 1.0);
        tree.connect(1, 2, 1.0);
        tree.connect(2, 3, 1.0);

        WeightedPath path = pathfinder.search(tree, 0, 3);

        assertEquals(4, path.getNumberOfNodes());
        assertEquals(node0, path.getNode(0));
        assertEquals(node1, path.getNode(1));
        assertEquals(node2, path.getNode(2));
        assertEquals(node3, path.getNode(3));
        assertEquals(3.0, path.getTotalCost(), 0.001);
    }
}

com.github.coderodde.pathfinding.AbstractPathfinderTest.java:

package com.github.coderodde.pathfinding;

import static org.junit.Assert.assertEquals;
import org.junit.Before;
import org.junit.Test;

public abstract class AbstractPathfinderTest {

    protected Pathfinder pathfinder;
    protected final WeightedTree tree = new WeightedTree();
    
    @Before
    public void before() {
        tree.clear();
    }
    
    @Test
    public void trivialPath() {
        tree.addTreeNode(1);
        WeightedPath path = pathfinder.search(tree, 1, 1);
        
        assertEquals(1, path.getNumberOfNodes());
        assertEquals(0.0, path.getTotalCost(), 0.001);
    }
    
    @Test
    public void singleEdgePath() {
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        tree.connect(1, 2, 3.0);
        
        WeightedPath path = pathfinder.search(tree, 1, 2);
        
        assertEquals(2, path.getNumberOfNodes());
        assertEquals(3.0, path.getTotalCost(), 0.001);
        
        assertEquals(1, path.getNode(0).getId());
        assertEquals(2, path.getNode(1).getId());
        
        assertEquals(3.0, path.getEdge(0).getWeight(), 0.001);
        assertEquals(1, path.getNode(0).getId());
        assertEquals(2, path.getNode(1).getId());
    }
    
    @Test
    public void starTree() {
        tree.addTreeNode(0);
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        tree.addTreeNode(3);
        
        tree.connect(0, 1, 1.0);
        tree.connect(0, 2, 2.0);
        tree.connect(0, 3, 3.0);
        
        WeightedPath path = pathfinder.search(tree, 1, 3);
        
        assertEquals(3, path.getNumberOfNodes());
        assertEquals(tree.getNode(1), path.getNode(0));
        assertEquals(tree.getNode(0), path.getNode(1));
        assertEquals(tree.getNode(3), path.getNode(2));
        assertEquals(4.0, path.getTotalCost(), 0.001);
    }
    
    @Test(expected = PathNotFoundException.class)
    public void throwsOnUnreachableTarget() {
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        tree.addTreeNode(3);
        
        tree.connect(1, 2, 1.0);
        
        pathfinder.search(tree, 3, 2);
    }
}

com.github.coderodde.pathfinding.BidirectionalBreadthFirstSearchPathfinderTest.java:

package com.github.coderodde.pathfinding;

public final class BidirectionalBreadthFirstSearchPathfinderTest 
        extends AbstractPathfinderTest {

    public BidirectionalBreadthFirstSearchPathfinderTest() {
        super.pathfinder = new BidirectionalBreadthFirstSearchPathfinder();
    }
}

com.github.coderodde.pathfinding.BidirectionalIterativeDeepeningDepthFirstSearchPathfinderTest.java:

package com.github.coderodde.pathfinding;

public final class BidirectionalIterativeDeepeningDepthFirstSearchPathfinderTest
        extends AbstractIDDFSPathfinderTest {

    public BidirectionalIterativeDeepeningDepthFirstSearchPathfinderTest() {
        super.pathfinder = new IterativeDeepeningDepthFirstSearchPathfinder(5);
    }
}

com.github.coderodde.pathfinding.BreadthFirstSearchPathfinderTest.java:

package com.github.coderodde.pathfinding;

public final class BreadthFirstSearchPathfinderTest 
        extends AbstractPathfinderTest {

    public BreadthFirstSearchPathfinderTest() {
        super.pathfinder = new BreadthFirstSearchPathfinder();
    }
}

com.github.coderodde.pathfinding.DepthFirstSearchPathfinderTest.java:

package com.github.coderodde.pathfinding;

public final class DepthFirstSearchPathfinderTest 
        extends AbstractPathfinderTest {

    public DepthFirstSearchPathfinderTest() {
        super.pathfinder = new DepthFirstSearchPathfinder();
    }
}

com.github.coderodde.pathfinding.IterativeDeepeningDepthFirstSearchPathfinderTest.java:

package com.github.coderodde.pathfinding;

public final class IterativeDeepeningDepthFirstSearchPathfinderTest 
        extends AbstractIDDFSPathfinderTest {
    
    public IterativeDeepeningDepthFirstSearchPathfinderTest() {
        super.pathfinder = new IterativeDeepeningDepthFirstSearchPathfinder(5);
    }
}

com.github.coderodde.pathfinding.WeightedTreeTest.java:

package com.github.coderodde.pathfinding;

import com.github.coderodde.pathfinding.WeightedTree.WeightedTreeNode;
import java.util.Set;
import org.junit.After;
import org.junit.Test;
import static org.junit.Assert.*;

public final class WeightedTreeTest {
    
    private final WeightedTree tree = new WeightedTree();
    
    @After
    public void tearDown() {
        tree.clear();
    }

    @Test
    public void addTreeNode() {
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        tree.addTreeNode(4);
        
        assertTrue(tree.containsNodeId(1));
        assertTrue(tree.containsNodeId(2));
        assertTrue(tree.containsNodeId(4));
        assertFalse(tree.containsNodeId(3));
    }
    
    @Test
    public void addExistingTreeNode() {
        WeightedTreeNode node1 = tree.addTreeNode(1);
        WeightedTreeNode node2 = tree.addTreeNode(1);
        
        assertEquals(node1, node2);
    }
    
    @Test
    public void removeTreeNode() {
        tree.addTreeNode(1);
        assertFalse(tree.removeTreeNode(2));
        assertTrue(tree.removeTreeNode(1));
        assertFalse(tree.removeTreeNode(1));
    }
    
    @Test
    public void connect() {
        tree.addTreeNode(1);
        assertFalse(tree.hasEdge(1, 2));
        tree.addTreeNode(2);
        assertFalse(tree.hasEdge(1, 2));
        assertTrue(tree.connect(2, 1, 4.0));
        assertFalse(tree.connect(1, 2, 4.0));
        assertTrue(tree.hasEdge(2, 1));
        assertTrue(tree.connect(2, 1, 5.0));
    }
    
    @Test
    public void containsNodeId() {
        assertFalse(tree.containsNodeId(1));
        tree.addTreeNode(1);
        assertTrue(tree.containsNodeId(1));
    }
    
    @Test
    public void disconnect() {
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        
        tree.connect(2, 1, 1.0);
       
        assertTrue(tree.hasEdge(1, 2));
        assertTrue(tree.disconnect(1, 2));
        assertFalse(tree.disconnect(2, 1));
    }
    
    @Test
    public void disconnectOnNonExistingNodesReturnsFalse() {
        assertFalse(tree.disconnect(1, 2));
        tree.addTreeNode(1);
        assertFalse(tree.disconnect(1, 2));
    }

    @Test
    public void hasEdge() {
        tree.addTreeNode(1);
        tree.addTreeNode(3);
        
        assertFalse(tree.hasEdge(3, 1));
        assertTrue(tree.connect(1, 3, 0.0));
        assertTrue(tree.hasEdge(3, 1));
        assertTrue(tree.disconnect(1, 3));
        assertFalse(tree.hasEdge(1, 3));
    }
    
    @Test
    public void getNeighbors() {
        WeightedTreeNode node0 = tree.addTreeNode(0);
        WeightedTreeNode node1 = tree.addTreeNode(1);
        WeightedTreeNode node2 = tree.addTreeNode(2);
        WeightedTreeNode node3 = tree.addTreeNode(3);
        WeightedTreeNode node4 = tree.addTreeNode(4);
        
        assertTrue(tree.connect(0, 1, 0.0));
        assertTrue(tree.connect(0, 2, 0.0));
        assertTrue(tree.connect(0, 3, 0.0));
        
        Set<WeightedTreeNode> neighbors = tree.getNeighbors(0);
        
        assertEquals(3, neighbors.size());
        assertTrue(neighbors.contains(node1));
        assertTrue(neighbors.contains(node2));
        assertTrue(neighbors.contains(node3));
        assertFalse(neighbors.contains(node4));
    }    
    
    @Test
    public void getEdgeWeight() {
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        tree.connect(1, 2, 1.0);
        assertEquals(1.0, tree.getEdgeWeight(2, 1), 0.00001);
        tree.connect(2, 1, 2.0);
        assertEquals(2.0, tree.getEdgeWeight(1, 2), 0.00001);
    }
    
    @Test(expected = IllegalStateException.class)
    public void getEdgeWeightThrowsOnFirstBadId() {
        tree.addTreeNode(2);
        tree.getEdgeWeight(1, 2);
    }
    
    @Test(expected = IllegalStateException.class)
    public void getEdgeWeightThrowsOnSecondBadId() {
        tree.addTreeNode(1);
        tree.getEdgeWeight(1, 2);
    }
    
    @Test(expected = IllegalStateException.class) 
    public void getEdgeWeightThrowsOnNoEdge() {
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        tree.getEdgeWeight(1, 2);
    }
    
    @Test
    public void removeTreeNodeDisconnectFromNeighbors() {
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        tree.addTreeNode(3);
        tree.addTreeNode(0);
        
        tree.connect(0, 1, 1.0);
        tree.connect(0, 2, 1.0);
        tree.connect(0, 3, 1.0);
        
        assertTrue(tree.hasEdge(0, 2));
        
        tree.removeTreeNode(0);
        
        assertFalse(tree.hasEdge(0, 2));
    }
    
    @Test
    public void returnFalseOnConnectionToNonExistingNode() {
        tree.addTreeNode(1);
        assertFalse(tree.connect(1, 2, 0));
        
        tree.clear();
        
        tree.addTreeNode(2);
        assertFalse(tree.connect(1, 2, 0));
    }
    
    @Test
    public void connectThrowsOnNonExistingId1() {
        tree.addTreeNode(2);
        assertFalse(tree.connect(1, 2, 1.0));
    }
    
    @Test
    public void connectThrowsOnNonExistingId2() {
        tree.addTreeNode(1);
        assertFalse(tree.connect(1, 2, 1.0));
    }
    
    @Test(expected = IllegalStateException.class)
    public void getNeighborsThrowsOnBadId() {
        tree.getNeighbors(0);
    }
    
    @Test
    public void getTreeNodeId() {
        WeightedTreeNode node = new WeightedTreeNode(2);
        assertEquals(2, node.getId());
    }
    
    @Test
    public void treeNodeEquals() {
        WeightedTreeNode node = new WeightedTreeNode(3);
        
        assertTrue(node.equals(node));
        
        assertFalse(node.equals(new WeightedTreeNode(1)));
        
        assertFalse(node.equals(new Object()));
        assertFalse(node.equals(null));
        
        WeightedTreeNode nodeCopy = new WeightedTreeNode(3);
        assertTrue(node.equals(nodeCopy));
    }
    
    @Test
    public void isAcyclic() {
        tree.addTreeNode(0);
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        tree.addTreeNode(3);
        tree.addTreeNode(4);
        
        tree.connect(0, 1, 1.0);
        tree.connect(1, 2, 1.0);
        tree.connect(1, 3, 1.0);
        tree.connect(3, 4, 1.0);
        
        assertFalse(tree.isCyclic());
    }
    
    @Test
    public void isCyclic() {
        tree.addTreeNode(0);
        tree.addTreeNode(1);
        tree.addTreeNode(2);
        tree.addTreeNode(3);
        tree.addTreeNode(4);
        
        tree.connect(0, 1, 1.0);
        tree.connect(1, 2, 0);
        tree.connect(2, 3, 0);
        tree.connect(3, 1, 0);
        tree.connect(4, 2, 3.0);
        
        assertTrue(tree.isCyclic());
    }
}

Запрос критики

Как всегда, пожалуйста, расскажите мне все, что приходит на ум.

0

Похожие записи:

Добавить комментарий Отменить ответ