我努力理解描述。我想我已经明白了。请考虑指定要求,而不是仅在下次给出一个不完整的示例。
首先,我认为你的意思是找到根(零边)并将每个子节点视为子图。
但是,这导致:
// roots are nodes with a zero in-degree (no parents)
Vertices roots;
boost::remove_copy_if(vertices(g), back_inserter(roots), [&](Vertex v) { return boost::size(in_edges(v, g)); });
std::vector<Graph> subs;
for (Vertex root : roots) {
for (Vertex subroot : boost::make_iterator_range(adjacent_vertices(root, g))) {
std::set<Vertex> include;
std::vector<boost::default_color_type> colors(n);
boost::depth_first_visit(g, subroot,
boost::make_dfs_visitor(
boost::write_property(
boost::identity_property_map{},
inserter(include, include.end()),
boost::on_discover_vertex())
),
colors.data());
std::cout << "Root " << g[root].name << ": Subtree rooted at " << g[subroot].name << " includes " << include.size() << " nodes\n";
Filtered fg(g, boost::keep_all{}, [&](Vertex v) { return include.count(v); });
print_graph(fg, names);
}
}
Root A: Subtree rooted at B includes 4 nodes
B --> D E
D --> G
E -->
G -->
Root A: Subtree rooted at C includes 3 nodes
C --> F
F --> H
H -->
事实上,D
显然不是A
的孩子,所以不会计算。
回到绘图板。
所有子树包含单度儿童或叶节点?
这似乎确实描述了作为例子给出的“线性”子图。显然,“线性”(垂直)布局是任意布局选择。下面的所有三个表示都与问题图完全相同:
以相反的方式看待这一点突然变得更有意义:您可能希望列出从每个叶节点开始的所有线性依赖关系,直到您到达也参与另一个分支的节点。
这自然涉及进行拓扑搜索并从叶节点后面列出DAG中的每个分支:
Vertices reverse_topological;
boost::topological_sort(g, back_inserter(reverse_topological));
bool in_path = true;
for (auto v : reverse_topological) {
if (0 == out_degree(v, g)) { // is leaf?
in_path = true;
std::cout << "\nLeaf:";
}
in_path &= (1 == in_degree(v, g));
if (in_path)
std::cout << " " << names[v];
else
std::cout << " [" << names[v] << "]";
}
打印:
Leaf: G D
Leaf: E B
Leaf: H F C [A]
根据您的要求,您可以指示B
在两条路径中翻倍:
Vertices reverse_topological;
boost::topological_sort(g, back_inserter(reverse_topological));
bool in_path = true;
for (auto v : reverse_topological) {
switch (out_degree(v, g)) {
case 0:
// start a new path
in_path = true;
std::cout << "\nLeaf:";
break;
case 1:
break; // still single-degree
default: in_path = false;
}
if (in_path)
std::cout << " " << names[v];
else
std::cout << " [" << names[v] << "]";
}
打印
Leaf: G D
Leaf: E [B]
Leaf: H F C [A]
为了防止比特罗:
#include <boost/graph/adjacency_list.hpp>
struct GraphItem {
std::string name;
};
using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, GraphItem>;
using Vertex = Graph::vertex_descriptor;
using Vertices = std::vector<Vertex>;
#include <boost/graph/filtered_graph.hpp>
#include <boost/function.hpp>
using Filtered = boost::filtered_graph<Graph, boost::keep_all, boost::function<bool(Vertex)>>;
#include <boost/graph/graphviz.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graph_utility.hpp>
int main() {
Graph g;
auto names = get(&GraphItem::name, g);
enum {A,B,C,D,E,F,G,H,n};
Vertices vs {
add_vertex({"A"}, g),
add_vertex({"B"}, g),
add_vertex({"C"}, g),
add_vertex({"D"}, g),
add_vertex({"E"}, g),
add_vertex({"F"}, g),
add_vertex({"G"}, g),
add_vertex({"H"}, g),
};
assert(num_vertices(g) == n);
add_edge(vs[A], vs[B], g);
add_edge(vs[A], vs[C], g);
add_edge(vs[B], vs[D], g);
add_edge(vs[B], vs[E], g);
add_edge(vs[D], vs[G], g);
add_edge(vs[C], vs[F], g);
add_edge(vs[F], vs[H], g);
// write_graphviz(std::cout, g, make_label_writer(names));
// roots are nodes with a zero in-degree (no parents)
Vertices roots;
boost::remove_copy_if(vertices(g), back_inserter(roots), [&](Vertex v) { return boost::size(in_edges(v, g)); });
std::vector<Graph> subs;
for (Vertex root : roots) {
for (Vertex subroot : boost::make_iterator_range(adjacent_vertices(root, g))) {
std::set<Vertex> include;
std::vector<boost::default_color_type> colors(n);
boost::depth_first_visit(g, subroot,
boost::make_dfs_visitor(
boost::write_property(
boost::identity_property_map{},
inserter(include, include.end()),
boost::on_discover_vertex())
),
colors.data());
std::cout << "Root " << g[root].name << ": Subtree rooted at " << g[subroot].name << " includes " << include.size() << " nodes\n";
Filtered fg(g, boost::keep_all{}, [&](Vertex v) { return include.count(v); });
print_graph(fg, names);
}
}
}
#include <boost/graph/adjacency_list.hpp>
struct GraphItem {
std::string name;
};
using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, GraphItem>;
using Vertex = Graph::vertex_descriptor;
using Vertices = std::vector<Vertex>;
#include <boost/graph/topological_sort.hpp>
#include <iostream>
int main() {
Graph g;
auto names = get(&GraphItem::name, g);
{
enum {A,B,C,D,E,F,G,H,n};
Vertices vs {
add_vertex({"A"}, g),
add_vertex({"B"}, g),
add_vertex({"C"}, g),
add_vertex({"D"}, g),
add_vertex({"E"}, g),
add_vertex({"F"}, g),
add_vertex({"G"}, g),
add_vertex({"H"}, g),
};
assert(num_vertices(g) == n);
add_edge(vs[A], vs[B], g);
add_edge(vs[A], vs[C], g);
add_edge(vs[B], vs[D], g);
add_edge(vs[B], vs[E], g);
add_edge(vs[D], vs[G], g);
add_edge(vs[C], vs[F], g);
add_edge(vs[F], vs[H], g);
}
Vertices reverse_topological;
boost::topological_sort(g, back_inserter(reverse_topological));
bool in_path = true;
for (auto v : reverse_topological) {
if (0 == out_degree(v, g)) { // is leaf?
in_path = true;
std::cout << "\nLeaf:";
}
in_path &= (1 == in_degree(v, g));
if (in_path)
std::cout << " " << names[v];
else
std::cout << " [" << names[v] << "]";
}
}