需要使用boost :: graph从一个大图中查找子图

问题描述 投票：0回答：1
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
c++ boost boost-graph connected-components
1个回答
0
投票

使用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;
}

除了一切都是连通的，所以我们得到一个包含所有顶点的组件......让我们先使用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;
}

Full Listing

Live On Coliru

#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 -->
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.