BridgesTest.java
/**
* Copyright (c) 2020, 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 com.powsybl.iidm.network.Network;
import com.powsybl.iidm.network.test.EurostagTutorialExample1Factory;
import com.powsybl.openloadflow.network.*;
import com.powsybl.openloadflow.network.impl.Networks;
import org.jgrapht.alg.connectivity.BiconnectivityInspector;
import org.jgrapht.graph.Pseudograph;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.function.BiFunction;
import java.util.function.Predicate;
import java.util.stream.Collectors;
import static org.junit.jupiter.api.Assertions.assertEquals;
/**
* @author Florian Dupuy {@literal <florian.dupuy at rte-france.com>}
*/
class BridgesTest {
private static final Logger LOGGER = LoggerFactory.getLogger(BridgesTest.class);
private Network network;
private LfNetwork lfNetwork;
private Set<String> bridgesSetReference;
@BeforeEach
void setUp() {
long start = System.currentTimeMillis();
network = EurostagFactory.fix(EurostagTutorialExample1Factory.create());
List<LfNetwork> lfn = Networks.load(network, new FirstSlackBusSelector());
this.lfNetwork = lfn.get(0);
LOGGER.info("Reading network of {} buses in {} ms", lfNetwork.getBuses().size(), System.currentTimeMillis() - start);
this.bridgesSetReference = getBridgesReference();
LOGGER.info("Reference established");
}
private Set<String> getBridgesReference() {
return Arrays.stream(new String[] {"NGEN_NHV1", "NHV2_NLOAD"}).collect(Collectors.toSet());
}
@Test
void testNaiveConnectivity() {
Set<String> bridges = testBridgesOnConnectivity(lfNetwork,
new NaiveGraphConnectivity<>(LfBus::getNum), "naive algorithm");
assertEquals(bridgesSetReference, bridges);
}
@Test
void testEvenShiloach() {
Set<String> bridges = testBridgesOnConnectivity(lfNetwork, new EvenShiloachGraphDecrementalConnectivity<>(), "Even-Shiloach");
assertEquals(bridgesSetReference, bridges);
}
@Test
void testMst() {
Set<String> bridges = testBridgesOnConnectivity(lfNetwork, new MinimumSpanningTreeGraphConnectivity<>(), "Even-Shiloach");
assertEquals(bridgesSetReference, bridges);
}
@Test
void testFindBridges() {
BridgesFinder<LfBus> graph = new BridgesFinder<>(lfNetwork.getBuses().size(), LfBus::getNum);
for (LfBus bus : lfNetwork.getBuses()) {
graph.addVertex(bus);
}
for (LfBranch branch : lfNetwork.getBranches()) {
LfBus bus1 = branch.getBus1();
LfBus bus2 = branch.getBus2();
if (bus1 != null && bus2 != null) {
graph.addEdge(bus1, bus2);
}
}
long start = System.currentTimeMillis();
List<int[]> bridges = graph.getBridges();
LOGGER.info("Bridges calculated based on Hopcroft-Tarjan algorithm in {} ms", System.currentTimeMillis() - start);
BiFunction<Integer, Integer, String> verticesToBranchId = (v1, v2) -> {
Predicate<? super LfBranch> p = b -> b.getBus1() != null && b.getBus2() != null
&& (b.getBus1().getNum() == v1 && b.getBus2().getNum() == v2 || b.getBus1().getNum() == v2 && b.getBus2().getNum() == v1);
return lfNetwork.getBus(v1).getBranches().stream().filter(p).findFirst().orElseThrow(PowsyblException::new).getId();
};
Set<String> set = bridges.stream().collect(HashSet::new, (h, t) -> h.add(verticesToBranchId.apply(t[0], t[1])), HashSet::addAll);
assertEquals(bridgesSetReference, set);
}
@Test
void testBiconnectivityInspector() {
org.jgrapht.Graph<String, String> graph = getJgraphTGraph(lfNetwork);
BiconnectivityInspector<String, String> bi = new BiconnectivityInspector<>(graph);
long start = System.currentTimeMillis();
Set<String> bridges = bi.getBridges();
LOGGER.info("Bridges calculated based on jgraphT BiconnectivityInspector in {} ms", System.currentTimeMillis() - start);
assertEquals(bridgesSetReference, bridges);
}
private Set<String> testBridgesOnConnectivity(LfNetwork lfNetwork, GraphConnectivity<LfBus, LfBranch> connectivity, String method) {
long start = System.currentTimeMillis();
initGraphDc(lfNetwork, connectivity);
LOGGER.info("Graph init for {} in {} ms", method, System.currentTimeMillis() - start);
start = System.currentTimeMillis();
Set<String> bridgesSet = getBridges(lfNetwork, connectivity);
LOGGER.info("Bridges calculated based on {} in {} ms", method, System.currentTimeMillis() - start);
return bridgesSet;
}
private static Set<String> getBridges(LfNetwork lfNetwork, GraphConnectivity<LfBus, LfBranch> connectivity) {
Set<String> bridgesSet = new HashSet<>();
for (LfBranch branch : lfNetwork.getBranches()) {
LfBus bus1 = branch.getBus1();
LfBus bus2 = branch.getBus2();
if (bus1 != null && bus2 != null) {
connectivity.startTemporaryChanges();
connectivity.removeEdge(branch);
boolean connected = connectivity.getComponentNumber(bus1) == connectivity.getComponentNumber(bus2);
if (!connected) {
bridgesSet.add(branch.getId());
}
connectivity.undoTemporaryChanges();
}
}
return bridgesSet;
}
private static org.jgrapht.Graph<String, String> getJgraphTGraph(LfNetwork lfNetwork) {
org.jgrapht.Graph<String, String> graph = new Pseudograph<>(String.class);
for (LfBus bus : lfNetwork.getBuses()) {
graph.addVertex(bus.getId());
}
for (LfBranch branch : lfNetwork.getBranches()) {
LfBus bus1 = branch.getBus1();
LfBus bus2 = branch.getBus2();
if (bus1 != null && bus2 != null) {
graph.addEdge(bus1.getId(), bus2.getId(), branch.getId());
}
}
return graph;
}
private static void initGraphDc(LfNetwork lfNetwork, GraphConnectivity<LfBus, LfBranch> connectivity) {
for (LfBus bus : lfNetwork.getBuses()) {
connectivity.addVertex(bus);
}
for (LfBranch branch : lfNetwork.getBranches()) {
LfBus bus1 = branch.getBus1();
LfBus bus2 = branch.getBus2();
if (bus1 != null && bus2 != null) {
connectivity.addEdge(bus1, bus2, branch);
}
}
}
}