BridgesFinder.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 org.jgrapht.Graph;
import org.jgrapht.graph.Pseudograph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.function.ToIntFunction;

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

    private static class NeighbourList extends ArrayList<Integer> {
    }

    private final int nbVertices;
    private final ToIntFunction<V> numGetter;
    private final Graph<Integer, Object> graph = new Pseudograph<>(Object.class);

    private List<int[]> bridges;
    private final NeighbourList[] neighbours;
    private final boolean[] visited;

    /**
     * Depth-first search number
     */
    private final int[] dfsn;

    /**
     * Depth-first search number counter
     */
    private int dfsnCount;

    BridgesFinder(int nbVertices, ToIntFunction<V> numGetter) {
        this.numGetter = Objects.requireNonNull(numGetter);
        this.nbVertices = nbVertices;
        this.visited = new boolean[nbVertices];
        this.dfsn = new int[nbVertices];
        this.neighbours = new NeighbourList[nbVertices];
        for (int i = 0; i < nbVertices; ++i) {
            neighbours[i] = new NeighbourList();
        }
        this.dfsnCount = 0;
    }

    /**
     * Finds bridges in a connected component, recursively
     *
     * @param start  vertex to be visited
     * @param parent parent vertex of the vertex to be visited
     * @return the lowest reachable vertex from given vertex
     */
    private int findBridgesFromVertex(int start, int parent) {

        visited[start] = true;
        dfsnCount++;
        dfsn[start] = dfsnCount;
        int lowestReachableVertex = dfsnCount;

        for (int neighbour : neighbours[start]) {
            if (!visited[neighbour]) {
                // Neighbour not visited yet: consider it as child of start and visit it
                int lowestN = findBridgesFromVertex(neighbour, start);

                // Check if neighbour has a connection to one of the ancestors of start
                if (lowestReachableVertex > lowestN) {
                    lowestReachableVertex = lowestN;
                }

                // If the lowest vertex reachable from neighbour is after start,
                // and if edge is not doubled, then start-neighbour is a bridge
                if (lowestN > dfsn[start] && !doubledEdge(start, neighbour)) {
                    bridges.add(new int[] {start, neighbour});
                }
            } else {
                // Already visited neighbour
                if (neighbour != parent && lowestReachableVertex > dfsn[neighbour]) {
                    lowestReachableVertex = dfsn[neighbour];
                }
            }
        }

        return lowestReachableVertex;
    }

    private boolean doubledEdge(int u, int v) {
        return graph.getAllEdges(u, v).size() > 1;
    }


    /**
     * DFS based function to find all bridges
     *
     * @return the list of bridge edges, represented as pairs of vertices
     */
    List<int[]> getBridges() {
        lazySearch();
        return bridges;
    }

    private void lazySearch() {
        if (bridges == null) {
            dfsnCount = 0;
            bridges = new ArrayList<>();
            Arrays.fill(visited, false);
            for (int i = 0; i < nbVertices; i++) {
                if (!visited[i]) {
                    findBridgesFromVertex(i, i);
                }
            }
        }
    }

    public void addVertex(V vertex) {
        Objects.requireNonNull(vertex);
        graph.addVertex(numGetter.applyAsInt(vertex));
    }

    public void addEdge(V vertex1, V vertex2) {
        Objects.requireNonNull(vertex1);
        Objects.requireNonNull(vertex2);
        addEdge(numGetter.applyAsInt(vertex1), numGetter.applyAsInt(vertex2));
    }

    private void addEdge(int num1, int num2) {
        graph.addEdge(num1, num2, new Object());
        neighbours[num1].add(num2);
        neighbours[num2].add(num1);
    }

}