如何在RDKIT分子键图边缘和BGL双连接组件标识符之间创建增强性能图？

Question

RDKIT库提供了一个分子类提供成员函数 getTopology 返回类型 adjacency_list＆lt; vecs，vecs，vecs，diondrecteds，atom *，bond *＆gt; 的BGL图。我了解RDKIT类型债券提供了成员函数 getIdx 返回唯一整数以识别债券，因此该图必须具有边缘编号的概念。

使用 biconnected_components 需要一个组件属性映射，该属性映射图形的边缘描述符类型的对象（我知道此类型是 bond> bond ？）来识别整数。由于RDKIT不在双连接组件中交易，因此我得出结论，该属性图必须在图表外部。在这种情况下，BGL文档建议使用 iterator_property_map 适配器类（请参阅“外部属性”部分）。我很难确定 iterator_property_map 获得所需属性映射的正确模板参数。如果这是正确的方法，则缺少模板参数？

不幸的是，在BGL文档中迷失之前，我的代码并没有太远：

void my_function(const RDKit::ROMol& molecule) {
 const RDKit::MolGraph& molecule_graph{molecule.getTopology()};

  using EdgesSize =
      boost::graph_traits<RDKit::MolGraph>::edges_size_type; // map value type
  using Edge =
      boost::graph_traits<RDKit::MolGraph>::edge_descriptor; // map key type

  std::vector<EdgesSize> component_map(boost::num_edges(molecule_graph)
  ); // range, begin() yields random access iterator

  // boost::iterator_property_map<?>;
  // boost::biconnected_components(molecule_graph, ?);
}

Answer 1

需要一个组件属性映射，该图映射图形的边缘描述符的对象（我知道这种类型是键？）

边缘描述符是内部描述符，有点像稳定的迭代器。例如

 edge_descriptor e = *edges(g).begin();

边缘属性是完全独立的概念。您可以从Edge描述符获得边缘属性：

 Bond* e_props = g[e]; // equivalent to:
 e_props = get(boost::edge_bundle, g, e);

毫不奇怪的是，对于顶点描述符与属性：

  Atom* first_a_prop = g[vertex(0, g)];

并发症

之间的两个描述符类型之间的显着差异是 - 仅是因为Graph类型使用 vecs 作为顶点容器选择器 - 确保顶点描述符是不可或缺的，其中边缘描述符是不透明的（类似于 void*）。

因此，边缘脱位不能是基于向量的属性映射的关键类型（因为它需要一个积分索引器）。

取而代之的是建立关联属性map：

// OUT: ComponentMap c
// must be a model of Writable Property Map. The value type should be
// an integer type, preferably the same as the edges_size_type of the
// graph. The key type must be the graph's edge descriptor type.
std::map<edge_descriptor, int> component_map;
auto c = boost::make_assoc_property_map(component_map);

样本

live on Coliru >

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/biconnected_components.hpp>
#include <iostream>

struct Atom {
};

struct Bond {
    int idx_ = 42;
    int getIdx() const { return idx_; }
};

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Atom*, Bond*>;
using vertex_descriptor = G::vertex_descriptor;
using edge_descriptor   = G::edge_descriptor;

int main() {
    std::array<Atom, 4> atoms;
    std::array<Bond, 2> bonds{Bond{111}, Bond{222}};

    G g;
    add_vertex(atoms.data()+0, g);
    add_vertex(atoms.data()+1, g);
    add_vertex(atoms.data()+2, g);
    add_vertex(atoms.data()+3, g);

    // using the fact that vertex_descriptor is 0..3 here:
    add_edge(0, 2, bonds.data()+0, g);
    add_edge(2, 3, bonds.data()+1, g);

    {
        // OUT: ComponentMap c
        // must be a model of Writable Property Map. The value type should be
        // an integer type, preferably the same as the edges_size_type of the
        // graph. The key type must be the graph's edge descriptor type.
        std::map<edge_descriptor, int> component_map;
        auto c = boost::make_assoc_property_map(component_map);

        // Now use it:
        size_t n = boost::biconnected_components(g, c);
        for (auto [e, component_id] : component_map) {
            std::cout << "Edge " << e << " (idx:" << g[e]->getIdx()
                      << ") mapped to component " << component_id << " out of "
                      << n << "\n";
        }
    }

    {
        std::map<edge_descriptor, int> component_map;
        auto c = boost::make_assoc_property_map(component_map);

        // also writing articulation points:
        [[maybe_unused]] auto [n, out] = boost::biconnected_components(
            g, c,
            std::ostream_iterator<vertex_descriptor>(
                std::cout << "articulation points: ", " "));

        std::cout << "\n";
    }

}

打印

Edge (0,2) (idx:111) mapped to component 1 out of 2
Edge (2,3) (idx:222) mapped to component 0 out of 2
articulation points: 2 

高级示例

您 can 将向量作为映射存储，但这需要您将边缘（ bonds ）映射到连续的积分范围[0..num_edges（g g） ）。

我不能假设 getIdx（）满足标准，但是如果这样做：

// first map edges to 0..num_edges using getIdx
auto edge_index = boost::make_function_property_map<edge_descriptor>(
    [&g](edge_descriptor e) { return g[e]->getIdx(); });

// provide num_edges storage for component-ids:
std::vector<int> component_ids(num_edges(g));

// project the vector through edge_index to make a Writable Property
// Map indexed by edge_descriptor;
auto c = boost::make_safe_iterator_property_map(component_ids.begin(),
        component_ids.size(), edge_index);

让我们将其应用于图形

> https://i.sstatic.net/wpwgf.png“ rel =” nofollow noreferrer“>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/biconnected_components.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <iostream>

enum letter : char { A, B, C, D, E, F, G, H, I };
struct Atom {
    Atom(letter) {}
};

struct Bond {
    int idx_;
    int getIdx() const { return idx_; }
};

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Atom*, Bond*>;
using vertex_descriptor = Graph::vertex_descriptor;
using edge_descriptor   = Graph::edge_descriptor;

int main() {
    std::array<Atom, 9>  atoms{A, B, C, D, E, F, G, H, I};
    std::array<Bond, 11> bonds{
        {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}}};

    Graph g;
    for (auto& atom : atoms)
        add_vertex(&atom, g);

    // using the fact that vertex_descriptor is vertex index:
    add_edge(A, B, &bonds.at(0), g);
    add_edge(A, F, &bonds.at(1), g);
    add_edge(A, G, &bonds.at(2), g);
    add_edge(B, C, &bonds.at(3), g);
    add_edge(B, D, &bonds.at(4), g);
    add_edge(B, E, &bonds.at(5), g);
    add_edge(C, D, &bonds.at(6), g);
    add_edge(E, F, &bonds.at(7), g);
    add_edge(G, H, &bonds.at(8), g);
    add_edge(G, I, &bonds.at(9), g);
    add_edge(H, I, &bonds.at(10), g);

    // OUT: ComponentMap c
    // must be a model of Writable Property Map. The value type should be
    // an integer type, preferably the same as the edges_size_type of the
    // graph. The key type must be the graph's edge descriptor type.

    // first map edges to 0..10 using getIdx
    auto edge_index = boost::make_function_property_map<edge_descriptor>(
            [&g](edge_descriptor e) { return g[e]->getIdx(); });

    // provide num_edges storage for component-ids:
    std::vector<int> component_ids(num_edges(g));

    // project the vector through edge_index to make a Writable Property
    // Map indexed by edge_descriptor;
    auto c = boost::make_safe_iterator_property_map(component_ids.begin(),
            component_ids.size(), edge_index);

    // Now use it:
    size_t n = boost::biconnected_components(g, c);

    for (auto e : boost::make_iterator_range(edges(g))) {
        // edge_index or getIdx, equivalent here:
        assert(edge_index[e] == g[e]->getIdx());

        auto idx =edge_index[e];
        auto cid = component_ids.at(idx);

        std::cout << "Edge " << e << " (idx:" << idx << ") mapped to component "
                  << cid << " out of " << n << "\n";
    }
}

live on Coliru 实际上

Edge (0,1) (idx:0) mapped to component 1 out of 4
Edge (0,5) (idx:1) mapped to component 1 out of 4
Edge (0,6) (idx:2) mapped to component 3 out of 4
Edge (1,2) (idx:3) mapped to component 0 out of 4
Edge (1,3) (idx:4) mapped to component 0 out of 4
Edge (1,4) (idx:5) mapped to component 1 out of 4
Edge (2,3) (idx:6) mapped to component 0 out of 4
Edge (4,5) (idx:7) mapped to component 1 out of 4
Edge (6,7) (idx:8) mapped to component 2 out of 4
Edge (6,8) (idx:9) mapped to component 2 out of 4
Edge (7,8) (idx:10) mapped to component 2 out of 4

，如果我们添加a nofollow noreferrer“> bonus wizardry” ：