如何高效使用boost graph
How to efficiently use boost graph
我有如下一段代码：
struct Vertex {
std::string name;
};
struct Edge {
std::string name;
};
class MyGraph {
public:
MyGraph() = default;
using Graph = adjacency_list<vecS, vecS, bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = graph_traits<Graph>::vertex_descriptor;
using EdgeDesc = graph_traits<Graph>::edge_descriptor;
void addNode(std::shared_ptr<Vertex> node){
const auto name = node->name;
if (vertexMap_.find(name) == vertexMap_.end()) {
const auto vertex = add_vertex(node, graph_);
vertexLabelArray_.emplace_back(name);
vertexMap_[name] = vertex;
}
}
void addEdge(std::shared_ptr<Vertex> src, std::shared_ptr<Vertex> dst, std::shared_ptr<Edge> weight = nullptr) {
const auto srcName = src->name;
const auto dstName = dst->name;
const auto vertexPair = std::make_pair(srcName, dstName);
if (edgeSet_.find(vertexPair) == edgeSet_.end()) {
addNode(src);
addNode(dst);
const auto edge = add_edge(vertexMap_[srcName], vertexMap_[dstName], weight, graph_).first;
edgeSet_.insert(vertexPair);
edgeLabelMap_[edge] = weight ? weight->name : "";
}
}
void print(std::ostream& out)
{
write_graphviz(out, graph_,
make_label_writer(vertexLabelArray_.data()),
make_label_writer(make_assoc_property_map(edgeLabelMap_)));
}
private:
std::vector<std::string> vertexLabelArray_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
std::set<std::pair<std::string, std::string>> edgeSet_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{"n1"}});
const auto n2 = std::make_shared<Node>(Node{{"n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.addEdge(n1, n2, e1);
g.print(std::cout);
}
我想减少一些潜在的冗余：
1 - 我如何使用 setS 而不是 vecS 来避免检查 vertex/edge 是否存在。当我这样做时，write_graphiz 函数抱怨它失败并出现许多以
开头的错误
error: cannot form a reference to 'void' typedef const value_type& const_reference;
2 - 我正在使用 shared_ptr 允许将自定义对象附加到顶点和边。有没有一种简单的方法可以根据附加对象查找顶点索引？
3 - 是否可以删除大部分外部数据结构并以某种方式使用 boost 属性？
全部上传到这里：https://godbolt.org/z/qbEnEoYj3
感谢任何帮助。
1 - how can i use setS instead of vecS to avoid checking is a
Q.: vertex/edge exists. when i do so, the write_graphiz function complains
that it fails with lots of errors beginning with
当然可以。事实上边缘选择器是没有问题的：https://godbolt.org/z/b1xbYMM4s。制作顶点容器 setS 不会达到你的意思，因为每个添加的顶点根据定义都是唯一的。
但为了显示手头的技术问题：该存储策略没有隐式顶点索引（序号 [0..numvertices()]）。有些算法需要一个。另外，你假设一个 VertexLabelArray_ 不再有意义，所以让我们变成 VertexLabelMap_ 就像边缘标签一样：
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct Vertex {
std::string name;
};
struct Edge {
std::string name;
};
class MyGraph {
public:
MyGraph() = default;
using Graph = boost::adjacency_list< //
boost::setS, boost::listS, boost::bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = boost::graph_traits<Graph>::vertex_descriptor;
using EdgeDesc = boost::graph_traits<Graph>::edge_descriptor;
void addNode(std::shared_ptr<Vertex> node)
{
const auto name = node->name;
if (vertexMap_.find(name) == vertexMap_.end()) {
const auto vertex = add_vertex(node, graph_);
vertexLabelMap_.emplace(vertex, name);
vertexMap_[name] = vertex;
}
}
void addEdge(std::shared_ptr<Vertex> src, std::shared_ptr<Vertex> dst,
std::shared_ptr<Edge> weight = nullptr)
{
const auto srcName = src->name;
const auto dstName = dst->name;
const auto vertexPair = std::make_pair(srcName, dstName);
if (edgeSet_.find(vertexPair) == edgeSet_.end()) {
addNode(src);
addNode(dst);
const auto edge = add_edge(vertexMap_[srcName], vertexMap_[dstName],
weight, graph_)
.first;
edgeSet_.insert(vertexPair);
edgeLabelMap_[edge] = weight ? weight->name : "";
}
}
void print(std::ostream& out)
{
std::map<VertexDesc, int> idmap;
for (auto v : boost::make_iterator_range(vertices(graph_))) {
idmap.emplace(v, idmap.size());
}
write_graphviz(out, graph_,
boost::make_label_writer(
boost::make_assoc_property_map(vertexLabelMap_)),
boost::make_label_writer(
boost::make_assoc_property_map(edgeLabelMap_)),
boost::default_writer{},
boost::make_assoc_property_map(idmap));
}
private:
std::map<VertexDesc, std::string> vertexLabelMap_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
std::set<std::pair<std::string, std::string>> edgeSet_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
#include <iostream>
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{"n1"}});
const auto n2 = std::make_shared<Node>(Node{{"n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.addEdge(n1, n2, e1);
g.print(std::cout);
}
或者，如果这样的索引可以成为 Vertex 的一部分：
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
struct Vertex {
int id;
std::string name;
};
struct Edge {
std::string name;
};
class MyGraph {
public:
MyGraph() = default;
using Graph = boost::adjacency_list< //
boost::setS, boost::listS, boost::bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = boost::graph_traits<Graph>::vertex_descriptor;
using EdgeDesc = boost::graph_traits<Graph>::edge_descriptor;
void addNode(std::shared_ptr<Vertex> const& node)
{
const auto name = node->name;
if (vertexMap_.find(name) == vertexMap_.end()) {
const auto vertex = add_vertex(node, graph_);
vertexLabelArray_.push_back(name);
vertexMap_[name] = vertex;
}
}
void addEdge(std::shared_ptr<Vertex> const& src,
std::shared_ptr<Vertex> const& dst,
std::shared_ptr<Edge> const& weight = nullptr)
{
const auto srcName = src->name;
const auto dstName = dst->name;
const auto vertexPair = std::make_pair(srcName, dstName);
if (edgeSet_.find(vertexPair) == edgeSet_.end()) {
addNode(src);
addNode(dst);
const auto edge = add_edge(vertexMap_[srcName], vertexMap_[dstName],
weight, graph_)
.first;
edgeSet_.insert(vertexPair);
edgeLabelMap_[edge] = weight ? weight->name : "";
}
}
void print(std::ostream& out)
{
auto idmap = boost::make_transform_value_property_map(
[](auto const& sp) { return sp->id; },
get(boost::vertex_bundle, graph_));
write_graphviz(
out, graph_,
boost::make_label_writer(boost::make_iterator_property_map(
vertexLabelArray_.begin(), idmap)),
boost::make_label_writer(
boost::make_assoc_property_map(edgeLabelMap_)),
boost::default_writer{}, idmap);
}
private:
std::vector<std::string> vertexLabelArray_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
std::set<std::pair<std::string, std::string>> edgeSet_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
#include <iostream>
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{0, "n1"}});
const auto n2 = std::make_shared<Node>(Node{{1, "n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.addEdge(n1, n2, e1);
g.print(std::cout);
}
Q.: 2 - i am using a shared_ptr for allowing for custom object to be
attached to vertices and edges.
我注意到了这一点。我认为这有点值得怀疑。如果您正在寻找效率，我不会到处使用 shared_ptr。
Q.: is there an easy way for looking up a
vertex index based on its attached object?
不是内置的。有（未记录的？）labeled_graph 适配器有...一些方便。 YMMV。另外，您可以 use a bimap or similar.
Q.: 3 - Is it possible to remove most of the external data structures and
use boost property instead somehow?
我会强烈考虑这一点。当然可以。基本上，你已经这样做了。
评论
您的代码有很多改进的机会（包括有效的优化）。
通过const&:
传递共享指针
首先不要传递共享指针，因为您不打算共享 ownership/observe refcounts/lifetimes。当我展示一个直接在图形模型中体现 node/edge 数据的版本时，我会展示这个。
void addNode 可以 return 顶点描述符，避免大量冗余查找。这也使得已经存在的项目不是错误变得更加明确。 （现在它只是忽略了 addNode/addEdge?）
void ensureEdge(std::shared_ptr<Vertex> const& src,
std::shared_ptr<Vertex> const& dst,
std::shared_ptr<Edge> const& edge = {})
{
if (edgeSet_.emplace(src->name, dst->name).second) {
auto [descriptor, isnew] = add_edge( //
ensureNode(src), ensureNode(dst), edge, graph_);
edgeLabelMap_.emplace(descriptor, edge ? edge->name : "");
}
}
工作更少意味着效率更高。
就像您几乎提到的那样，您已经可以使用 add_edge 的结果测试边缘是否存在，避免额外的 edgeSet_:
EdgeDesc ensureEdge(std::shared_ptr<Vertex> const& src,
std::shared_ptr<Vertex> const& dst,
std::shared_ptr<Edge> const& edge = {})
{
auto [descriptor, isnew] =
add_edge(ensureNode(src), ensureNode(dst), edge, graph_);
if (isnew)
edgeLabelMap_.emplace(descriptor, edge ? edge->name : "");
return descriptor;
}
请注意，现在，由于行为更加一致，我们还可以 return 边缘描述符。这将消除查询我们刚刚添加的边缘的需要。
当前版本Live On Compiler Explorer:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
struct Vertex { std::string name; };
struct Edge { std::string name; };
class MyGraph {
public:
MyGraph() = default;
using Graph = boost::adjacency_list< //
boost::setS, boost::vecS, boost::bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = Graph::vertex_descriptor;
using EdgeDesc = Graph::edge_descriptor;
VertexDesc ensureNode(std::shared_ptr<Vertex> const& node)
{
auto const& name = node->name;
auto it = vertexMap_.find(name);
if (it == vertexMap_.end()) {
auto descriptor = add_vertex(node, graph_);
vertexLabelArray_.push_back(name);
vertexMap_[name] = descriptor;
it = vertexMap_.emplace(name, descriptor).first;
}
return it->second;
}
EdgeDesc ensureEdge(std::shared_ptr<Vertex> const& src,
std::shared_ptr<Vertex> const& dst,
std::shared_ptr<Edge> const& edge = {})
{
auto [descriptor, isnew] =
add_edge(ensureNode(src), ensureNode(dst), edge, graph_);
if (isnew)
edgeLabelMap_.emplace(descriptor, edge ? edge->name : "");
return descriptor;
}
void print(std::ostream& out) const
{
write_graphviz(
out, graph_, //
boost::make_label_writer(vertexLabelArray_.data()),
boost::make_label_writer(make_assoc_property_map(edgeLabelMap_)));
}
private:
std::vector<std::string> vertexLabelArray_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
#include <iostream>
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{"n1"}});
const auto n2 = std::make_shared<Node>(Node{{"n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.ensureEdge(n1, n2, e1);
g.print(std::cout);
}
仍然打印
digraph G {
0[label=n2];
1[label=n1];
1->0 [label=e1];
}
其他步骤
您指定了 BidirectionalGraph 支持，但目前不使用边缘界面。考虑放弃它，这样您就不会产生维护冗余边缘信息的开销
using Graph = boost::adjacency_list< //
boost::setS, boost::vecS, boost::directedS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
考虑对 属性 包使用值语义。这将减少分配，增加参考位置，并可能带来大量存储优化机会。
考虑这个版本，它不再使用 vertexLabelArray_ 也不再使用 edgeLabelMap_（毕竟这两个属性都只存在于图形模型中）：
void print(std::ostream& out) const {
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)));
}
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct Vertex { std::string name; };
struct Edge { std::string name; };
class MyGraph {
public:
using Graph = boost::adjacency_list< //
boost::setS, boost::vecS, boost::directedS, Vertex, Edge>;
using VertexDesc = Graph::vertex_descriptor;
using EdgeDesc = Graph::edge_descriptor;
VertexDesc ensureNode(Vertex const& node) {
if (auto it = vertexMap_.find(node.name); it != vertexMap_.end())
return it->second;
auto descriptor = add_vertex(node, graph_);
vertexMap_[node.name] = descriptor;
vertexMap_.emplace(node.name, descriptor);
return descriptor;
}
EdgeDesc ensureEdge(Vertex const& src, Vertex const& dst, Edge edge) {
auto [descriptor, isnew] =
add_edge(ensureNode(src), ensureNode(dst), std::move(edge), graph_);
return descriptor; // TODO maybe raise an error if !isnew?
}
void print(std::ostream& out) const {
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)));
}
private:
std::map<std::string, VertexDesc> vertexMap_;
Graph graph_;
};
struct Node : Vertex { };
struct Arc : Edge { };
#include <iostream>
int main() {
MyGraph g;
Node n1{{"n1"}}, n2{{"n2"}};
Arc e1{{"e1"}};
g.ensureEdge(n1, n2, e1);
g.ensureEdge({"n3"}, {"n4"}, {"e2"});
g.print(std::cout);
}
打印
digraph G {
0[label=n2];
1[label=n1];
2[label=n4];
3[label=n3];
1->0 [label=e1];
3->2 [label=e2];
}
更高效的顶点查找？
如果您真的很关心存储和查找效率，请将 vertexMap_ 键设为 string_view。这需要仔细考虑引用字符串的生命周期。
// use stored property, not parameter as vertexMap_ key!
vertexMap_.emplace(graph_[vd].name, vd);
对于初学者，您需要一个具有参考稳定性的容器选择器用于顶点容器（例如listS）。
此外，考虑将容器设为 flat_map，这样存储和查找将得到很大优化。他们将有效地成为 vector<tuple<char const*, size_t, size_t> >:
boost::container::flat_map<std::string_view, VertexDesc> vertexMap_;
#include <boost/container/flat_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct Vertex { std::string name; };
struct Edge { std::string name; };
class MyGraph {
public:
using Graph = boost::adjacency_list< //
boost::setS, boost::listS, boost::directedS, Vertex, Edge>;
using VertexDesc = Graph::vertex_descriptor;
using EdgeDesc = Graph::edge_descriptor;
VertexDesc ensureNode(Vertex const& node) {
if (auto it = vertexMap_.find(node.name); it != vertexMap_.end())
return it->second;
auto vd = add_vertex(node, graph_);
// use stored property, not parameter as vertexMap_ key!
vertexMap_.emplace(graph_[vd].name, vd);
return vd;
}
EdgeDesc ensureEdge(Vertex const& src, Vertex const& dst, Edge edge) {
auto [ed, isnew] =
add_edge(ensureNode(src), ensureNode(dst), std::move(edge), graph_);
return ed; // TODO maybe raise an error if !isnew?
}
void print(std::ostream& out) const {
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)),
boost::default_writer{},
get(&Vertex::name, graph_));
}
private:
boost::container::flat_map<std::string_view, VertexDesc> vertexMap_;
Graph graph_;
};
struct Node : Vertex { };
struct Arc : Edge { };
#include <iostream>
int main() {
MyGraph g;
Node n1{{"n1"}}, n2{{"n2"}};
Arc e1{{"e1"}};
g.ensureEdge(n1, n2, e1);
g.ensureEdge({"n3"}, {"n4"}, {"e2"});
g.print(std::cout);
}
请注意，这通过使用 Vertex name 作为 graphviz 节点 ID 欺骗了 little。无论如何，这很有意义：
digraph G {
n2[label=n2];
n1[label=n1];
n4[label=n4];
n3[label=n3];
n1->n2 [label=e1];
n3->n4 [label=e2];
}
如果您坚持使用完整的 ID - 您可以使用 vertexMap_ 现在是连续的这一事实来破解它们：
void print(std::ostream& out) const {
auto node_id = boost::make_function_property_map<VertexDesc>(
[this](VertexDesc vd) {
return vertexMap_.find(graph_[vd].name) - vertexMap_.begin();
});
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)),
boost::default_writer{}, node_id);
}
这会打印 (Live Link):
digraph G {
1[label=n2];
0[label=n1];
3[label=n4];
2[label=n3];
0->1 [label=e1];
2->3 [label=e2];
}
Note that doing the listS vertex container selection makes a BIG difference in resource trade-offs in the graph implementation itself, so if the vertex lookup via vertexMap_ is not your bottleneck, don't do this optimization!
更多 BGL 设施
正如我提到的，BGL 中有一些支持标记图。我不推荐这样做，因为我 run into my share of implementation bugs/quirks。但我不在这里提及它是我的失职。
另见 How to create a named_graph with Boost Graph Library? 这是一个很好的答案
我有如下一段代码：
struct Vertex {
std::string name;
};
struct Edge {
std::string name;
};
class MyGraph {
public:
MyGraph() = default;
using Graph = adjacency_list<vecS, vecS, bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = graph_traits<Graph>::vertex_descriptor;
using EdgeDesc = graph_traits<Graph>::edge_descriptor;
void addNode(std::shared_ptr<Vertex> node){
const auto name = node->name;
if (vertexMap_.find(name) == vertexMap_.end()) {
const auto vertex = add_vertex(node, graph_);
vertexLabelArray_.emplace_back(name);
vertexMap_[name] = vertex;
}
}
void addEdge(std::shared_ptr<Vertex> src, std::shared_ptr<Vertex> dst, std::shared_ptr<Edge> weight = nullptr) {
const auto srcName = src->name;
const auto dstName = dst->name;
const auto vertexPair = std::make_pair(srcName, dstName);
if (edgeSet_.find(vertexPair) == edgeSet_.end()) {
addNode(src);
addNode(dst);
const auto edge = add_edge(vertexMap_[srcName], vertexMap_[dstName], weight, graph_).first;
edgeSet_.insert(vertexPair);
edgeLabelMap_[edge] = weight ? weight->name : "";
}
}
void print(std::ostream& out)
{
write_graphviz(out, graph_,
make_label_writer(vertexLabelArray_.data()),
make_label_writer(make_assoc_property_map(edgeLabelMap_)));
}
private:
std::vector<std::string> vertexLabelArray_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
std::set<std::pair<std::string, std::string>> edgeSet_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{"n1"}});
const auto n2 = std::make_shared<Node>(Node{{"n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.addEdge(n1, n2, e1);
g.print(std::cout);
}
我想减少一些潜在的冗余：
1 - 我如何使用 setS 而不是 vecS 来避免检查 vertex/edge 是否存在。当我这样做时，write_graphiz 函数抱怨它失败并出现许多以
error: cannot form a reference to 'void' typedef const value_type& const_reference;
2 - 我正在使用 shared_ptr 允许将自定义对象附加到顶点和边。有没有一种简单的方法可以根据附加对象查找顶点索引？
3 - 是否可以删除大部分外部数据结构并以某种方式使用 boost 属性？
全部上传到这里：https://godbolt.org/z/qbEnEoYj3
感谢任何帮助。
1 - how can i use setS instead of vecS to avoid checking is a Q.: vertex/edge exists. when i do so, the write_graphiz function complains that it fails with lots of errors beginning with
当然可以。事实上边缘选择器是没有问题的：https://godbolt.org/z/b1xbYMM4s。制作顶点容器 setS 不会达到你的意思，因为每个添加的顶点根据定义都是唯一的。
但为了显示手头的技术问题：该存储策略没有隐式顶点索引（序号 [0..numvertices()]）。有些算法需要一个。另外，你假设一个 VertexLabelArray_ 不再有意义，所以让我们变成 VertexLabelMap_ 就像边缘标签一样：
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct Vertex {
std::string name;
};
struct Edge {
std::string name;
};
class MyGraph {
public:
MyGraph() = default;
using Graph = boost::adjacency_list< //
boost::setS, boost::listS, boost::bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = boost::graph_traits<Graph>::vertex_descriptor;
using EdgeDesc = boost::graph_traits<Graph>::edge_descriptor;
void addNode(std::shared_ptr<Vertex> node)
{
const auto name = node->name;
if (vertexMap_.find(name) == vertexMap_.end()) {
const auto vertex = add_vertex(node, graph_);
vertexLabelMap_.emplace(vertex, name);
vertexMap_[name] = vertex;
}
}
void addEdge(std::shared_ptr<Vertex> src, std::shared_ptr<Vertex> dst,
std::shared_ptr<Edge> weight = nullptr)
{
const auto srcName = src->name;
const auto dstName = dst->name;
const auto vertexPair = std::make_pair(srcName, dstName);
if (edgeSet_.find(vertexPair) == edgeSet_.end()) {
addNode(src);
addNode(dst);
const auto edge = add_edge(vertexMap_[srcName], vertexMap_[dstName],
weight, graph_)
.first;
edgeSet_.insert(vertexPair);
edgeLabelMap_[edge] = weight ? weight->name : "";
}
}
void print(std::ostream& out)
{
std::map<VertexDesc, int> idmap;
for (auto v : boost::make_iterator_range(vertices(graph_))) {
idmap.emplace(v, idmap.size());
}
write_graphviz(out, graph_,
boost::make_label_writer(
boost::make_assoc_property_map(vertexLabelMap_)),
boost::make_label_writer(
boost::make_assoc_property_map(edgeLabelMap_)),
boost::default_writer{},
boost::make_assoc_property_map(idmap));
}
private:
std::map<VertexDesc, std::string> vertexLabelMap_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
std::set<std::pair<std::string, std::string>> edgeSet_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
#include <iostream>
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{"n1"}});
const auto n2 = std::make_shared<Node>(Node{{"n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.addEdge(n1, n2, e1);
g.print(std::cout);
}
或者，如果这样的索引可以成为 Vertex 的一部分：
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
struct Vertex {
int id;
std::string name;
};
struct Edge {
std::string name;
};
class MyGraph {
public:
MyGraph() = default;
using Graph = boost::adjacency_list< //
boost::setS, boost::listS, boost::bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = boost::graph_traits<Graph>::vertex_descriptor;
using EdgeDesc = boost::graph_traits<Graph>::edge_descriptor;
void addNode(std::shared_ptr<Vertex> const& node)
{
const auto name = node->name;
if (vertexMap_.find(name) == vertexMap_.end()) {
const auto vertex = add_vertex(node, graph_);
vertexLabelArray_.push_back(name);
vertexMap_[name] = vertex;
}
}
void addEdge(std::shared_ptr<Vertex> const& src,
std::shared_ptr<Vertex> const& dst,
std::shared_ptr<Edge> const& weight = nullptr)
{
const auto srcName = src->name;
const auto dstName = dst->name;
const auto vertexPair = std::make_pair(srcName, dstName);
if (edgeSet_.find(vertexPair) == edgeSet_.end()) {
addNode(src);
addNode(dst);
const auto edge = add_edge(vertexMap_[srcName], vertexMap_[dstName],
weight, graph_)
.first;
edgeSet_.insert(vertexPair);
edgeLabelMap_[edge] = weight ? weight->name : "";
}
}
void print(std::ostream& out)
{
auto idmap = boost::make_transform_value_property_map(
[](auto const& sp) { return sp->id; },
get(boost::vertex_bundle, graph_));
write_graphviz(
out, graph_,
boost::make_label_writer(boost::make_iterator_property_map(
vertexLabelArray_.begin(), idmap)),
boost::make_label_writer(
boost::make_assoc_property_map(edgeLabelMap_)),
boost::default_writer{}, idmap);
}
private:
std::vector<std::string> vertexLabelArray_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
std::set<std::pair<std::string, std::string>> edgeSet_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
#include <iostream>
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{0, "n1"}});
const auto n2 = std::make_shared<Node>(Node{{1, "n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.addEdge(n1, n2, e1);
g.print(std::cout);
}
Q.: 2 - i am using a shared_ptr for allowing for custom object to be attached to vertices and edges.
我注意到了这一点。我认为这有点值得怀疑。如果您正在寻找效率，我不会到处使用 shared_ptr。
Q.: is there an easy way for looking up a vertex index based on its attached object?
不是内置的。有（未记录的？）labeled_graph 适配器有...一些方便。 YMMV。另外，您可以 use a bimap or similar.
Q.: 3 - Is it possible to remove most of the external data structures and use boost property instead somehow?
我会强烈考虑这一点。当然可以。基本上，你已经这样做了。
评论
您的代码有很多改进的机会（包括有效的优化）。
通过
传递共享指针const&:首先不要传递共享指针，因为您不打算共享 ownership/observe refcounts/lifetimes。当我展示一个直接在图形模型中体现 node/edge 数据的版本时，我会展示这个。
void addNode可以 return 顶点描述符，避免大量冗余查找。这也使得已经存在的项目不是错误变得更加明确。 （现在它只是忽略了addNode/addEdge?）void ensureEdge(std::shared_ptr<Vertex> const& src, std::shared_ptr<Vertex> const& dst, std::shared_ptr<Edge> const& edge = {}) { if (edgeSet_.emplace(src->name, dst->name).second) { auto [descriptor, isnew] = add_edge( // ensureNode(src), ensureNode(dst), edge, graph_); edgeLabelMap_.emplace(descriptor, edge ? edge->name : ""); } }工作更少意味着效率更高。
就像您几乎提到的那样，您已经可以使用
add_edge的结果测试边缘是否存在，避免额外的edgeSet_:EdgeDesc ensureEdge(std::shared_ptr<Vertex> const& src, std::shared_ptr<Vertex> const& dst, std::shared_ptr<Edge> const& edge = {}) { auto [descriptor, isnew] = add_edge(ensureNode(src), ensureNode(dst), edge, graph_); if (isnew) edgeLabelMap_.emplace(descriptor, edge ? edge->name : ""); return descriptor; }请注意，现在，由于行为更加一致，我们还可以 return 边缘描述符。这将消除查询我们刚刚添加的边缘的需要。
当前版本Live On Compiler Explorer:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
struct Vertex { std::string name; };
struct Edge { std::string name; };
class MyGraph {
public:
MyGraph() = default;
using Graph = boost::adjacency_list< //
boost::setS, boost::vecS, boost::bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = Graph::vertex_descriptor;
using EdgeDesc = Graph::edge_descriptor;
VertexDesc ensureNode(std::shared_ptr<Vertex> const& node)
{
auto const& name = node->name;
auto it = vertexMap_.find(name);
if (it == vertexMap_.end()) {
auto descriptor = add_vertex(node, graph_);
vertexLabelArray_.push_back(name);
vertexMap_[name] = descriptor;
it = vertexMap_.emplace(name, descriptor).first;
}
return it->second;
}
EdgeDesc ensureEdge(std::shared_ptr<Vertex> const& src,
std::shared_ptr<Vertex> const& dst,
std::shared_ptr<Edge> const& edge = {})
{
auto [descriptor, isnew] =
add_edge(ensureNode(src), ensureNode(dst), edge, graph_);
if (isnew)
edgeLabelMap_.emplace(descriptor, edge ? edge->name : "");
return descriptor;
}
void print(std::ostream& out) const
{
write_graphviz(
out, graph_, //
boost::make_label_writer(vertexLabelArray_.data()),
boost::make_label_writer(make_assoc_property_map(edgeLabelMap_)));
}
private:
std::vector<std::string> vertexLabelArray_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
#include <iostream>
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{"n1"}});
const auto n2 = std::make_shared<Node>(Node{{"n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.ensureEdge(n1, n2, e1);
g.print(std::cout);
}
仍然打印
digraph G {
0[label=n2];
1[label=n1];
1->0 [label=e1];
}
其他步骤
您指定了
BidirectionalGraph支持，但目前不使用边缘界面。考虑放弃它，这样您就不会产生维护冗余边缘信息的开销using Graph = boost::adjacency_list< // boost::setS, boost::vecS, boost::directedS, std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;考虑对 属性 包使用值语义。这将减少分配，增加参考位置，并可能带来大量存储优化机会。
考虑这个版本，它不再使用
vertexLabelArray_也不再使用edgeLabelMap_（毕竟这两个属性都只存在于图形模型中）：void print(std::ostream& out) const { write_graphviz(out, graph_, make_label_writer(get(&Vertex::name, graph_)), make_label_writer(get(&Edge::name, graph_))); }
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct Vertex { std::string name; };
struct Edge { std::string name; };
class MyGraph {
public:
using Graph = boost::adjacency_list< //
boost::setS, boost::vecS, boost::directedS, Vertex, Edge>;
using VertexDesc = Graph::vertex_descriptor;
using EdgeDesc = Graph::edge_descriptor;
VertexDesc ensureNode(Vertex const& node) {
if (auto it = vertexMap_.find(node.name); it != vertexMap_.end())
return it->second;
auto descriptor = add_vertex(node, graph_);
vertexMap_[node.name] = descriptor;
vertexMap_.emplace(node.name, descriptor);
return descriptor;
}
EdgeDesc ensureEdge(Vertex const& src, Vertex const& dst, Edge edge) {
auto [descriptor, isnew] =
add_edge(ensureNode(src), ensureNode(dst), std::move(edge), graph_);
return descriptor; // TODO maybe raise an error if !isnew?
}
void print(std::ostream& out) const {
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)));
}
private:
std::map<std::string, VertexDesc> vertexMap_;
Graph graph_;
};
struct Node : Vertex { };
struct Arc : Edge { };
#include <iostream>
int main() {
MyGraph g;
Node n1{{"n1"}}, n2{{"n2"}};
Arc e1{{"e1"}};
g.ensureEdge(n1, n2, e1);
g.ensureEdge({"n3"}, {"n4"}, {"e2"});
g.print(std::cout);
}
打印
digraph G {
0[label=n2];
1[label=n1];
2[label=n4];
3[label=n3];
1->0 [label=e1];
3->2 [label=e2];
}
更高效的顶点查找？
如果您真的很关心存储和查找效率，请将 vertexMap_ 键设为 string_view。这需要仔细考虑引用字符串的生命周期。
// use stored property, not parameter as vertexMap_ key!
vertexMap_.emplace(graph_[vd].name, vd);
对于初学者，您需要一个具有参考稳定性的容器选择器用于顶点容器（例如listS）。
此外，考虑将容器设为 flat_map，这样存储和查找将得到很大优化。他们将有效地成为 vector<tuple<char const*, size_t, size_t> >:
boost::container::flat_map<std::string_view, VertexDesc> vertexMap_;
#include <boost/container/flat_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct Vertex { std::string name; };
struct Edge { std::string name; };
class MyGraph {
public:
using Graph = boost::adjacency_list< //
boost::setS, boost::listS, boost::directedS, Vertex, Edge>;
using VertexDesc = Graph::vertex_descriptor;
using EdgeDesc = Graph::edge_descriptor;
VertexDesc ensureNode(Vertex const& node) {
if (auto it = vertexMap_.find(node.name); it != vertexMap_.end())
return it->second;
auto vd = add_vertex(node, graph_);
// use stored property, not parameter as vertexMap_ key!
vertexMap_.emplace(graph_[vd].name, vd);
return vd;
}
EdgeDesc ensureEdge(Vertex const& src, Vertex const& dst, Edge edge) {
auto [ed, isnew] =
add_edge(ensureNode(src), ensureNode(dst), std::move(edge), graph_);
return ed; // TODO maybe raise an error if !isnew?
}
void print(std::ostream& out) const {
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)),
boost::default_writer{},
get(&Vertex::name, graph_));
}
private:
boost::container::flat_map<std::string_view, VertexDesc> vertexMap_;
Graph graph_;
};
struct Node : Vertex { };
struct Arc : Edge { };
#include <iostream>
int main() {
MyGraph g;
Node n1{{"n1"}}, n2{{"n2"}};
Arc e1{{"e1"}};
g.ensureEdge(n1, n2, e1);
g.ensureEdge({"n3"}, {"n4"}, {"e2"});
g.print(std::cout);
}
请注意，这通过使用 Vertex name 作为 graphviz 节点 ID 欺骗了 little。无论如何，这很有意义：
digraph G {
n2[label=n2];
n1[label=n1];
n4[label=n4];
n3[label=n3];
n1->n2 [label=e1];
n3->n4 [label=e2];
}
如果您坚持使用完整的 ID - 您可以使用 vertexMap_ 现在是连续的这一事实来破解它们：
void print(std::ostream& out) const {
auto node_id = boost::make_function_property_map<VertexDesc>(
[this](VertexDesc vd) {
return vertexMap_.find(graph_[vd].name) - vertexMap_.begin();
});
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)),
boost::default_writer{}, node_id);
}
这会打印 (Live Link):
digraph G {
1[label=n2];
0[label=n1];
3[label=n4];
2[label=n3];
0->1 [label=e1];
2->3 [label=e2];
}
Note that doing the
listSvertex container selection makes a BIG difference in resource trade-offs in the graph implementation itself, so if the vertex lookup viavertexMap_is not your bottleneck, don't do this optimization!
更多 BGL 设施
正如我提到的，BGL 中有一些支持标记图。我不推荐这样做，因为我 run into my share of implementation bugs/quirks。但我不在这里提及它是我的失职。
另见 How to create a named_graph with Boost Graph Library? 这是一个很好的答案