Нужно найти подграфы из одного большого графа, используя boost::graph

Question

Нужно найти подграфы из одного большого графа, используя boost::graph

PH -> PH1
PH -> PH2
PH1 -> N1
PH1 -> N2
PH2 -> N3
PH2 -> N4

Требуемый выход как:

sub graph 1 : 

    PH1 -> N1
    PH1 -> N2

sub graph 2 : 
    PH2 -> N3
    PH2 -> N3

0

c++ boost boost-graph connected-components

Источник

user9150119 28 дек '17 в 16:58

1 ответ

Другие вопросы по тегам c++ boost boost-graph connected-components

user85371 29 дек '17 в 01:13 2017-12-29 01:13 · Answer 1 · 2017-12-29 01:13

Это почти тривиальное использование connected_components,

Сложнее всего игнорировать PH узел. Вы не сказали, указан ли этот узел или должен быть обнаружен. Я написал некоторый код, чтобы попытаться его обнаружить.

Давайте начнем

#include <boost/graph/adjacency_list.hpp>

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
    boost::property<boost::vertex_name_t, std::string> >;

Мы хотим примерно реализовать следующие шаги:

using ComponentId = int;
using Mappings    = std::vector<ComponentId>;
using Graphs      = std::vector<Graph>;

Graph build();
Mappings map_components(Graph const&);
Graphs split(Graph const&, Mappings const&);

И основная программа будет выглядеть

#include <boost/graph/graph_utility.hpp>
int main() {
    Graph g = build();

    Mappings components = map_components(g);

    for (auto& sub : split(g, components)) {
        std::cout << "\n========================\n";
        print_graph(sub, get(boost::vertex_name, sub));
    }
}

Пример данных

Это просто, так как мы использовали vertex_name имущество:

using Vertex = Graph::vertex_descriptor;

Graph build() {
    Graph g;

    Vertex PH = add_vertex({"PH"}, g);
    Vertex PH1 = add_vertex({"PH1"}, g);
    Vertex PH2 = add_vertex({"PH2"}, g);
    Vertex N1 = add_vertex({"N1"}, g);
    Vertex N2 = add_vertex({"N2"}, g);
    Vertex N3 = add_vertex({"N3"}, g);
    Vertex N4 = add_vertex({"N4"}, g);

    add_edge(PH, PH1, g);
    add_edge(PH, PH2, g);
    add_edge(PH1, N1, g);
    add_edge(PH1, N2, g);
    add_edge(PH2, N3, g);
    add_edge(PH2, N4, g);
    return g;
}

Составление карт компонентов

Это не так уж плохо

#include <boost/graph/connected_components.hpp> // connected_components
Mappings naive_components(Graph const& g) {
    Mappings mappings(num_vertices(g));
    int num = boost::connected_components(g, mappings.data());
    return mappings;
}

За исключением того, что все связано, поэтому мы получаем 1 компонент, содержащий все вершины... Давайте использовать articulation_points сначала "игнорировать" вершину:

#include <boost/graph/biconnected_components.hpp> // articulation_points
#include <boost/graph/connected_components.hpp> // connected_components
#include <boost/graph/filtered_graph.hpp>
#include <boost/function.hpp>

using Filtered = boost::filtered_graph<Graph, boost::keep_all, boost::function<bool(Vertex)> >;

Mappings map_components(Graph const& g) {
    Mappings mappings(num_vertices(g));

    std::vector<Vertex> ap;
    articulation_points(g, back_inserter(ap));

    if (!ap.empty()) {
        // get the articulation point with the lowest degree
        nth_element(ap.begin(), ap.begin()+1, ap.end(), [&](Vertex a, Vertex b) { return degree(a, g) < degree(b, g); });
        Vertex ignored = ap.front();

        std::cout << "Igoring articulation point " << get(boost::vertex_name, g, ignored) << " from graph\n";
        Filtered fg(g, {}, [&](Vertex v) { return ignored != v; });

        int num = boost::connected_components(fg, mappings.data());
        mappings[ignored] = num; // make sure the ignored vertex is in its own component
    }
    return mappings;
}

Это в основном делает то же самое, но игнорирует PH узел. Обратите внимание, что мы стараемся вырезать как можно меньше ребер (сортируя по degree).

расщепляющий

Разделение на отдельные графики - это почти формальность (повторное использование Filtered объявления графа):

#include <boost/graph/copy.hpp>

Graphs split(Graph const& g, Mappings const& components) {
    if (components.empty())
        return {};

    Graphs results;

    auto highest = *std::max_element(components.begin(), components.end());
    for (int c = 0; c <= highest; ++c) {
        results.emplace_back();
        boost::copy_graph(Filtered(g, {}, [c, &components](Vertex v) { return components.at(v) == c; }), results.back());
    }

    return results;
}

Полный листинг

Жить на Колиру

#include <boost/graph/adjacency_list.hpp>

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::property<boost::vertex_name_t, std::string> >;
using ComponentId = int;
using Mappings    = std::vector<ComponentId>;
using Graphs      = std::vector<Graph>;

Graph build();
Mappings map_components(Graph const&);
Graphs split(Graph const&, Mappings const&);

#include <boost/graph/graph_utility.hpp>
int main() {
    Graph g = build();

    Mappings components = map_components(g);

    for (auto& sub : split(g, components)) {
        std::cout << "\n========================\n";
        print_graph(sub, get(boost::vertex_name, sub));
    }
}

using Vertex = Graph::vertex_descriptor;

Graph build() {
    Graph g;

    Vertex PH = add_vertex({"PH"}, g);
    Vertex PH1 = add_vertex({"PH1"}, g);
    Vertex PH2 = add_vertex({"PH2"}, g);
    Vertex N1 = add_vertex({"N1"}, g);
    Vertex N2 = add_vertex({"N2"}, g);
    Vertex N3 = add_vertex({"N3"}, g);
    Vertex N4 = add_vertex({"N4"}, g);

    add_edge(PH, PH1, g);
    add_edge(PH, PH2, g);
    add_edge(PH1, N1, g);
    add_edge(PH1, N2, g);
    add_edge(PH2, N3, g);
    add_edge(PH2, N4, g);
    return g;
}

#include <boost/graph/biconnected_components.hpp> // articulation_points
#include <boost/graph/connected_components.hpp> // connected_components
#include <boost/graph/filtered_graph.hpp>
#include <boost/function.hpp>

using Filtered = boost::filtered_graph<Graph, boost::keep_all, boost::function<bool(Vertex)> >;

Mappings map_components(Graph const& g) {
    Mappings mappings(num_vertices(g));

    std::vector<Vertex> ap;
    articulation_points(g, back_inserter(ap));

    if (!ap.empty()) {
        // get the articulation point with the lowest degree
        nth_element(ap.begin(), ap.begin()+1, ap.end(), [&](Vertex a, Vertex b) { return degree(a, g) < degree(b, g); });
        Vertex ignored = ap.front();

        std::cout << "Igoring articulation point " << get(boost::vertex_name, g, ignored) << " from graph\n";
        Filtered fg(g, {}, [&](Vertex v) { return ignored != v; });

        int num = boost::connected_components(fg, mappings.data());
        mappings[ignored] = num; // make sure the ignored vertex is in its own component
    }
    return mappings;
}

#include <boost/graph/copy.hpp>

Graphs split(Graph const& g, Mappings const& components) {
    if (components.empty())
        return {};

    Graphs results;

    auto highest = *std::max_element(components.begin(), components.end());
    for (int c = 0; c <= highest; ++c) {
        results.emplace_back();
        boost::copy_graph(Filtered(g, {}, [c, &components](Vertex v) { return components.at(v) == c; }), results.back());
    }

    return results;
}

Печать

Igoring articulation point PH from graph

========================
PH1 --> N1 N2 
N1 --> 
N2 --> 

========================
PH2 --> N3 N4 
N3 --> 
N4 --> 

========================
PH -->