ConnectivityTest.java

/**
 * Copyright (c) 2021, RTE (http://www.rte-france.com)
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 * SPDX-License-Identifier: MPL-2.0
 */
package com.powsybl.openloadflow.graph;

import com.powsybl.commons.PowsyblException;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.Collections;
import java.util.Set;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import static org.junit.jupiter.api.Assertions.*;

/**
 * @author Florian Dupuy {@literal <florian.dupuy at rte-france.com>}
 */
class ConnectivityTest {

    @ParameterizedTest(name = "{0}")
    @MethodSource("provideNonRestrictedConnectivities")
    void setMainComponentVertexExceptionTest(GraphConnectivity<Integer, String> c) {
        Integer v1 = 1;
        Integer v2 = 2;
        Integer v3 = 3;
        String e12 = "1-2";
        c.addVertex(v1);
        c.addVertex(v2);
        c.addVertex(v3);
        c.addEdge(v1, v2, e12);

        c.setMainComponentVertex(v1);
        c.startTemporaryChanges();
        c.setMainComponentVertex(v2); // setting the main component vertex is accepted if already in the main component before
        PowsyblException e4 = assertThrows(PowsyblException.class, () -> c.setMainComponentVertex(v3));
        assertEquals("Cannot take the given vertex as main component vertex! This vertex was outside the main component before starting temporary changes", e4.getMessage());
    }

    @ParameterizedTest(name = "{0}")
    @MethodSource("provideAllConnectivities")
    void circleTest(GraphConnectivity<Integer, String> c) {
        int o1 = 1;
        int o2 = 2;
        int o3 = 3;
        int o4 = 4;
        String e12 = "1-2";
        String e23 = "2-3";
        String e34 = "3-4";
        String e41 = "4-1";
        c.addVertex(o1);
        c.addVertex(o2);
        c.addVertex(o3);
        c.addVertex(o4);
        c.addEdge(o1, o2, e12);
        c.addEdge(o2, o3, e23);
        c.addEdge(o3, o4, e34);
        c.addEdge(o4, o1, e41);

        c.startTemporaryChanges();
        c.removeEdge(e12);
        assertEquals(1, c.getNbConnectedComponents());
        assertTrue(c.getEdgesAddedToMainComponent().isEmpty());
        assertEquals(Set.of(e12), c.getEdgesRemovedFromMainComponent());
        assertTrue(c.getVerticesAddedToMainComponent().isEmpty());
        assertTrue(c.getVerticesRemovedFromMainComponent().isEmpty());
    }

    @ParameterizedTest(name = "{0}")
    @MethodSource("provideAllConnectivities")
    void loopCircleTest(GraphConnectivity<Integer, String> c) {
        int o1 = 1;
        int o2 = 2;
        int o3 = 3;
        String e11 = "1-1";
        String e12 = "1-2";
        String e23 = "2-3";
        String e31 = "3-1";
        c.addVertex(o1);
        c.addVertex(o2);
        c.addVertex(o3);
        c.addEdge(o1, o1, e11);
        c.addEdge(o1, o2, e12);
        c.addEdge(o2, o3, e23);
        c.addEdge(o3, o1, e31);

        c.startTemporaryChanges();
        c.removeEdge(e11);
        assertEquals(1, c.getNbConnectedComponents());
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e11), c.getEdgesRemovedFromMainComponent());

        c.undoTemporaryChanges();
        c.startTemporaryChanges();
        c.removeEdge(e12);
        assertEquals(1, c.getNbConnectedComponents());
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e12), c.getEdgesRemovedFromMainComponent());

        c.removeEdge(e31);
        assertEquals(2, c.getNbConnectedComponents());
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(o1), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e11, e31, e12), c.getEdgesRemovedFromMainComponent());
    }

    @ParameterizedTest(name = "{0}")
    @MethodSource("provideNonRestrictedConnectivities")
    void saveResetTest(GraphConnectivity<Integer, String> c) {
        Integer v1 = 1;
        Integer v2 = 2;
        Integer v3 = 3;
        Integer v4 = 4;
        Integer v5 = 5;
        String e11 = "1-1";
        String e12 = "1-2";
        String e23 = "2-3";
        String e31 = "3-1";
        String e45 = "4-5";
        c.addVertex(v1);
        c.addVertex(v2);
        c.addVertex(v3);
        c.addVertex(v4);
        c.addVertex(v5);
        c.addEdge(v1, v1, e11);
        c.addEdge(v1, v2, e12);
        c.addEdge(v2, v3, e23);
        c.addEdge(v3, v1, e31);
        c.addEdge(v4, v5, e45);
        //  |-------|
        //  1---2---3   4---5
        // |_|

        c.startTemporaryChanges();
        c.removeEdge(e12);
        c.removeEdge(e31);
        assertEquals(3, c.getNbConnectedComponents());
        assertEquals(Set.of(v1), c.getConnectedComponent(v1));
        assertEquals(Set.of(v2, v3), c.getConnectedComponent(v2));
        assertEquals(Set.of(v4, v5), c.getConnectedComponent(v5));
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(v1), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e11, e12, e31), c.getEdgesRemovedFromMainComponent());
        //  1   2---3   4---5
        // |_|

        c.startTemporaryChanges();
        c.removeEdge(e23);
        c.addEdge(v1, v2, e12);
        c.removeEdge(e11);
        String e34 = "3-4";
        c.addEdge(v3, v4, e34);
        assertEquals(2, c.getNbConnectedComponents());
        assertEquals(Set.of(v1, v2), c.getConnectedComponent(v1));
        assertEquals(Set.of(v3, v4, v5), c.getConnectedComponent(v5));
        assertEquals(Set.of(e34, e45), c.getEdgesAddedToMainComponent());
        assertEquals(Set.of(v4, v5), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(v2), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e23), c.getEdgesRemovedFromMainComponent());
        //  1---2   3---4---5

        c.undoTemporaryChanges();
        assertEquals(3, c.getNbConnectedComponents());
        assertEquals(Set.of(v1), c.getConnectedComponent(v1));
        assertEquals(Set.of(v2, v3), c.getConnectedComponent(v2));
        assertEquals(Set.of(v4, v5), c.getConnectedComponent(v5));
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(v1), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e11, e12, e31), c.getEdgesRemovedFromMainComponent());
        //  1   2---3   4---5
        // |_|

        c.startTemporaryChanges();
        c.addEdge(v1, v2, e12);
        assertEquals(2, c.getNbConnectedComponents());
        assertEquals(Set.of(v1, v2, v3), c.getConnectedComponent(v2));
        assertEquals(Set.of(v4, v5), c.getConnectedComponent(v5));
        assertEquals(Set.of(e11, e12), c.getEdgesAddedToMainComponent());
        assertEquals(Set.of(v1), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Collections.emptySet(), c.getEdgesRemovedFromMainComponent());
        //  1---2---3   4---5
        // |_|

        c.undoTemporaryChanges();
        assertEquals(3, c.getNbConnectedComponents());
        assertEquals(Set.of(v1), c.getConnectedComponent(v1));
        assertEquals(Set.of(v2, v3), c.getConnectedComponent(v2));
        assertEquals(Set.of(v4, v5), c.getConnectedComponent(v5));
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(v1), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e11, e12, e31), c.getEdgesRemovedFromMainComponent());
        //  1   2---3   4---5
        // |_|

        c.startTemporaryChanges();
        String e14 = "1-4";
        c.addEdge(v1, v4, e14);
        c.addEdge(v3, v4, e34);
        assertEquals(1, c.getNbConnectedComponents());
        assertEquals(Set.of(e11, e14, e34, e45), c.getEdgesAddedToMainComponent());
        assertEquals(Set.of(v1, v4, v5), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Collections.emptySet(), c.getEdgesRemovedFromMainComponent());
        //  |-----------|
        //  1   2---3---4---5
        // |_|

        Integer v6 = 6;
        c.addVertex(v6);
        assertEquals(2, c.getNbConnectedComponents());
        assertEquals(Set.of(v6), c.getConnectedComponent(v6));
        assertEquals(Set.of(e11, e14, e34, e45), c.getEdgesAddedToMainComponent());
        assertEquals(Set.of(v1, v4, v5), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Collections.emptySet(), c.getEdgesRemovedFromMainComponent());
        //  |-----------|
        //  1   2---3---4---5    6
        // |_|

        c.undoTemporaryChanges();
        c.undoTemporaryChanges();

        c.startTemporaryChanges();
        assertEquals(2, c.getNbConnectedComponents());
        assertEquals(Set.of(v1, v2, v3), c.getConnectedComponent(v1));
        assertEquals(Set.of(v4, v5), c.getConnectedComponent(v5));
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Collections.emptySet(), c.getEdgesRemovedFromMainComponent());

    }

    @ParameterizedTest(name = "{0}")
    @MethodSource("provideNonRestrictedConnectivities")
    void setMainComponentVertexTest(GraphConnectivity<Integer, String> c) {
        Integer v1 = 1;
        Integer v2 = 2;
        Integer v3 = 3;
        Integer v4 = 4;
        Integer v5 = 5;
        String e11 = "1-1";
        String e12 = "1-2";
        String e23 = "2-3";
        String e31 = "3-1";
        String e45 = "4-5";
        c.addVertex(v1);
        c.addVertex(v2);
        c.addVertex(v3);
        c.addVertex(v4);
        c.addVertex(v5);
        c.addEdge(v1, v1, e11);
        c.addEdge(v1, v2, e12);
        c.addEdge(v2, v3, e23);
        c.addEdge(v3, v1, e31);
        c.addEdge(v4, v5, e45);
        c.setMainComponentVertex(v5);
        //  |-------|
        //  1---2---3   4---5
        // |_|

        c.startTemporaryChanges();
        c.removeEdge(e12);
        c.removeEdge(e31);
        String e14 = "1-4";
        c.addEdge(v1, v4, e14);
        assertEquals(Set.of(e11, e14), c.getEdgesAddedToMainComponent());
        assertEquals(Set.of(v1), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Collections.emptySet(), c.getEdgesRemovedFromMainComponent());
        //  |-----------|
        //  1   2---3   4---5
        // |_|

        c.startTemporaryChanges();
        c.removeEdge(e23);
        c.addEdge(v1, v2, e12);
        c.removeEdge(e11);
        String e34 = "3-4";
        c.addEdge(v3, v4, e34);
        assertEquals(Set.of(e12, e34), c.getEdgesAddedToMainComponent());
        assertEquals(Set.of(v2, v3), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e11), c.getEdgesRemovedFromMainComponent());
        //  |-----------|
        //  1---2   3---4---5

        c.undoTemporaryChanges();
        //  |-----------|
        //  1   2---3   4---5
        // |_|

        c.startTemporaryChanges();
        String e14b = "1-4 duplicate";
        c.addEdge(v1, v4, e14b);
        c.addEdge(v3, v4, e34);
        c.removeEdge(e45);
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(v1, v4), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e11, e14, e45), c.getEdgesRemovedFromMainComponent());
        //  |-----------|
        //  |-----------|
        //  1   2---3---4   5
        // |_|

        c.setMainComponentVertex(1);
        assertEquals(Set.of(e14b, e23, e34), c.getEdgesAddedToMainComponent());
        assertEquals(Set.of(v2, v3), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(v5), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e45), c.getEdgesRemovedFromMainComponent());

        c.setMainComponentVertex(5);
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(v1, v4), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e11, e14, e45), c.getEdgesRemovedFromMainComponent());

        c.setMainComponentVertex(1);
        Integer v6 = 6;
        c.addVertex(v6);
        assertEquals(Set.of(e14b, e23, e34), c.getEdgesAddedToMainComponent());
        assertEquals(Set.of(v2, v3), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(v5), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e45), c.getEdgesRemovedFromMainComponent());
        //  |-----------|
        //  |-----------|
        //  1   2---3---4   5    6
        // |_|

        c.undoTemporaryChanges(); // vertex 5 is considered again as main component vertex
        //  |-----------|
        //  1   2---3   4---5
        // |_|
        assertEquals(Set.of(e11, e14), c.getEdgesAddedToMainComponent());
        assertEquals(Set.of(v1), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Collections.emptySet(), c.getEdgesRemovedFromMainComponent());

        c.undoTemporaryChanges();

        c.startTemporaryChanges();
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Collections.emptySet(), c.getEdgesRemovedFromMainComponent());
    }

    @ParameterizedTest(name = "{0}")
    @MethodSource("provideAllConnectivities")
    void exceptionsTest(GraphConnectivity<Integer, String> c) {
        Integer v1 = 1;
        Integer v2 = 2;
        String e12 = "1-2";
        String e22 = "2-2";
        c.addVertex(v1);
        c.addVertex(v2);
        c.addEdge(v1, v2, e12);
        c.addEdge(v2, v2, e22);
        c.removeEdge(e22);

        PowsyblException e1 = assertThrows(PowsyblException.class, c::getNbConnectedComponents);
        assertEquals("Cannot compute connectivity without a saved state, please call GraphConnectivity::startTemporaryChanges at least once beforehand",
                e1.getMessage());

        PowsyblException e2 = assertThrows(PowsyblException.class, c::undoTemporaryChanges);
        assertEquals("Cannot reset, no remaining saved connectivity", e2.getMessage());

        PowsyblException e3 = assertThrows(PowsyblException.class, c::undoTemporaryChanges);
        assertEquals("Cannot reset, no remaining saved connectivity", e3.getMessage());
    }

    @ParameterizedTest(name = "{0}")
    @MethodSource("provideAllConnectivities")
    void multipleEdgesTest(GraphConnectivity<Integer, String> c) {
        int o1 = 1;
        int o2 = 2;
        int o3 = 3;
        String e12 = "1-2";
        String e23 = "2-3";
        c.addVertex(o1);
        c.addVertex(o2);
        c.addVertex(o3);
        c.addEdge(o1, o2, e12);
        c.addEdge(o1, o2, e12);
        c.addEdge(o2, o3, e23);
        // 1---2---3

        c.startTemporaryChanges();
        assertEquals(1, c.getNbConnectedComponents());
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
        assertEquals(Collections.emptySet(), c.getEdgesRemovedFromMainComponent());
        // 1---2---3

        c.removeEdge(e12);
        assertEquals(2, c.getNbConnectedComponents());
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(o1), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of(e12), c.getEdgesRemovedFromMainComponent());
        // 1   2---3

        // Non-effective modifications
        c.removeEdge(e12);
        c.removeEdge(e12);
        c.addVertex(o1);
        assertEquals(2, c.getNbConnectedComponents());

        boolean incrementalSupport = !(c instanceof EvenShiloachGraphDecrementalConnectivity);
        if (incrementalSupport) {
            c.addEdge(o1, o2, e12);
            assertEquals(1, c.getNbConnectedComponents());
            assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
            assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
            assertEquals(Collections.emptySet(), c.getVerticesRemovedFromMainComponent());
            assertEquals(Collections.emptySet(), c.getEdgesRemovedFromMainComponent());
            // 1---2---3
        }
    }

    @ParameterizedTest(name = "{0}")
    @MethodSource("provideNonRestrictedConnectivities")
    void removeThenAddEdgesTest(GraphConnectivity<Integer, String> c) {
        IntStream.range(1, 6).forEach(c::addVertex);
        IntStream.range(1, 5).forEach(i -> c.addEdge(i, i + 1, i + "-" + (i + 1)));
        // 1---2---3---4---5

        c.startTemporaryChanges();
        c.removeEdge("2-3");
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(1, 2), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of("1-2", "2-3"), c.getEdgesRemovedFromMainComponent());
        // 1---2   3---4---5

        c.removeEdge("1-2");
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(1, 2), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of("1-2", "2-3"), c.getEdgesRemovedFromMainComponent());
        // 1   2   3---4---5

        c.addEdge(1, 2, "1-2");
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(1, 2), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of("1-2", "2-3"), c.getEdgesRemovedFromMainComponent());
        // 1---2   3---4---5

        c.addVertex(6);
        c.addEdge(5, 6, "5-6");
        assertEquals(Set.of("5-6"), c.getEdgesAddedToMainComponent());
        assertEquals(Set.of(6), c.getVerticesAddedToMainComponent());
        // 1---2   3---4---5---6

        c.removeEdge("5-6");
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(1, 2), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of("1-2", "2-3"), c.getEdgesRemovedFromMainComponent());
        // 1---2   3---4---5   6

        c.removeEdge("1-2");
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(1, 2), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of("1-2", "2-3"), c.getEdgesRemovedFromMainComponent());
        // 1   2   3---4---5   6

        c.addEdge(1, 2, "1-2");
        assertEquals(Collections.emptySet(), c.getEdgesAddedToMainComponent());
        assertEquals(Collections.emptySet(), c.getVerticesAddedToMainComponent());
        assertEquals(Set.of(1, 2), c.getVerticesRemovedFromMainComponent());
        assertEquals(Set.of("1-2", "2-3"), c.getEdgesRemovedFromMainComponent());
        // 1---2   3---4---5   6
    }

    private static Stream<Arguments> provideNonRestrictedConnectivities() {
        return Stream.of(
                Arguments.of(new NaiveGraphConnectivity<Integer, String>(v -> v - 1)),
                Arguments.of(new MinimumSpanningTreeGraphConnectivity<>()));
    }

    private static Stream<Arguments> provideAllConnectivities() {
        return Stream.of(
                Arguments.of(new NaiveGraphConnectivity<Integer, String>(v -> v - 1)),
                Arguments.of(new EvenShiloachGraphDecrementalConnectivity<>()),
                Arguments.of(new MinimumSpanningTreeGraphConnectivity<>()));
    }
}