Program Listing for File BiconnectedComponents.hpp¶

/*
 * BiconnectedeComponents.hpp
 *
 * Created on: March 2018
 *       Author: Eugenio Angriman
 */

#ifndef NETWORKIT_COMPONENTS_BICONNECTED_COMPONENTS_HPP_
#define NETWORKIT_COMPONENTS_BICONNECTED_COMPONENTS_HPP_

#include <map>
#include <unordered_set>
#include <vector>

#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

/*
 * @ingroup components
 * Determines the biconnected components of an undirected graph as defined in
 * Tarjan, Robert. Depth-First Search and Linear Graph Algorithms. SIAM J.
 * Comput. Vol 1, No. 2, June 1972.
 */
class BiconnectedComponents final : public Algorithm {

public:
    /*
     * Creates BiconnectedComponents class for Graph @a G.
     *
     * @param G The graph.
     */
    BiconnectedComponents(const Graph &G);

    /*
     * This method determines the biconnected components for the graph given in
     * the constructor.
     */
    void run() override;

    /*
     *  Get the number of biconnected components.
     *
     *  @return The number of biconnected components.
     */
    count numberOfComponents() const;

    /*
     * Get the size of each component.
     *
     * @return Map from component index to size.
     */
    std::map<count, count> getComponentSizes() const;

    /*
     * Get the components vector.
     *
     * @return Vector of vectors, each component is stored as an (unordered) set
     * of nodes.
     */
    std::vector<std::vector<node>> getComponents() const;

    /*
     * Get the components that contain node @a u.
     *
     * @param u A node.
     * @return Components that contain node @a u.
     */
    const std::unordered_set<node> &getComponentsOfNode(node u) const {
        assureFinished();
        return componentsOfNode[u];
    }

private:
    void init();
    void newComponent(std::pair<node, node> e);

    const Graph *G;
    count n;
    count idx;
    count nComp;
    std::vector<count> level;
    std::vector<count> lowpt;
    std::vector<node> parent;
    std::vector<bool> visited;
    std::vector<bool> isRoot;
    std::vector<std::unordered_set<node>> componentsOfNode;
    std::map<count, count> componentSizes;
};

inline count BiconnectedComponents::numberOfComponents() const {
    assureFinished();
    return nComp;
}

inline std::map<count, count> BiconnectedComponents::getComponentSizes() const {
    assureFinished();
    return componentSizes;
}

inline std::vector<std::vector<node>> BiconnectedComponents::getComponents() const {
    assureFinished();
    std::vector<std::vector<node>> result(nComp);

    node v = 0;
    for (auto components : componentsOfNode) {
        for (auto it = components.begin(); it != components.end(); ++it) {
            result[*it].push_back(v);
        }
        ++v;
    }
    return result;
}
} // namespace NetworKit
#endif // NETWORKIT_COMPONENTS_BICONNECTED_COMPONENTS_HPP_