需要使用boost :: graph从一个大图中查找子图 [英] Need to find sub graphs from one big graph using boost::graph
本文介绍了需要使用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
推荐答案
使用connected_components几乎没有问题.
复杂的事情是忽略PH节点.您没有说这个节点是 give 还是应该被检测到.我已经写了一些代码来尝试检测它.
The complicating thing is to ignore the PH node. You didn't say whether this node is given or should be detected. I have written some code to try to detect it.
#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> >;
我们要大致执行以下步骤:
We want to implement roughly the following steps:
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;
}
映射组件
这还不错:
Mapping Components
This is not too bad:
#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个包含所有顶点的组件...让我们使用
Except, everything is connected, so we get 1 component containing all the vertices... Let's use articulation_points to "ignore" a vertex first:
#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排序).
That's basically doing the same thing, but it ignores the PH node. Note that we try to make sure we cut as few edges as possible (by sorting by degree).
拆分为单独的图形几乎是一种形式(重新使用相同的Filtered图形声明):
Splitting into separate graphs is almost a formality (re-using the same Filtered graph declarations):
#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 -->
这篇关于需要使用boost :: graph从一个大图中查找子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
