如何在 rdkit 分子键图边缘和 BGL 双连通组件标识符之间创建一个提升 属性 映射?

How to create a boost property map between rdkit molecular bond graph edges and BGL biconnected component identifiers?

rdkit库提供了分子class ROMol that provides a member function getTopology that returns a BGL graph of type adjacency_list<vecS, vecS, undirectedS, Atom *, Bond *>. I understand that the rdkit type Bond定义图的边属性。我知道 Bond 提供了一个成员函数 getIdx returns 一个唯一的整数来标识键,因此该图必须具有边编号的概念。

biconnected_components one requires a component property map that maps objects of the edge descriptor type of the graph (I understand this type is Bond?) to component identifying integers. As rdkit does not deal in biconnected components, I conclude this property map must be exterior to the graph. In this case, the BGL documentation suggests to use the iterator_property_map 适配器 class 使用 BGL 算法(参见“外部属性”部分)。我努力确定 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, ?);
}

one requires a component property map that maps objects of the edge descriptor type of the graph (I understand this type is Bond?)

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

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

边缘属性是完全不同的概念。您可以像这样从边缘描述符中获取边缘属性:

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

不出所料,顶点描述符与属性也是如此:

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

并发症

两种描述符类型之间的显着区别是 - 仅因为图类型使用 vecS 作为顶点容器选择器 - 保证顶点描述符是整数,其中边缘描述符是不透明的(类似于 void*)。

因此,edge-decriptor 不能是 vector-based 属性 映射的键类型(因为它需要一个完整的索引器)。

改为创建关联 property-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 

高级示例

可以强制一个向量作为映射存储,但这需要你将边()映射到一个连续的整数范围[0..num_edges(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);

让我们把它应用到图表中 from the documentation:

Live On Coliru

#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";
    }
}

哪个打印打印出预期的映射

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

事实上,如果我们添加一个 little bit of bonus wizardry,我们可以渲染: