Boost图在子图中找到边

Question

有一个图 G0 和子图 G1...G7，我想在子图 G1...G7 的集合中找到 G7 的出现，在这种特殊情况下，输出应该是 G7 在 5 , G7 在 7 但它不起作用，输出是 G7 在 4 中， G7在6， G7 在 7 中。我真的不明白错误可能在哪里。（也许是for-loop）

 #include < boost/config.hpp >

 #include < iostream >

 #include < boost/graph/subgraph.hpp >

 #include < boost/graph/adjacency_list.hpp >

 #include < boost/graph/graph_utility.hpp >

 #include < boost/graph/lookup_edge.hpp >


using namespace boost;

typedef subgraph< adjacency_list < vecS, vecS, directedS,

property < vertex_color_t, int > , property<edge_index_t, int> > > Graph;


int threshold = 3;
int size_of_database = 7;


int main(int,char*[])

{

    const int N = 6;
    Graph G0(N);
    enum { A, B, C, D, E, F};     // for conveniently refering to vertices in G0

    Graph& G1 = G0.create_subgraph();
    Graph& G2 = G0.create_subgraph();
    Graph& G3 = G0.create_subgraph();
    Graph& G4 = G0.create_subgraph();
    Graph& G5 = G0.create_subgraph();
    Graph& G6 = G0.create_subgraph();
    Graph& G7 = G0.create_subgraph();


    enum { A1, B1, C1 };   // for conveniently refering to vertices in G1
    enum { A2, B2 };    // for conveniently refering to vertices in G2
    enum { A3, B3 };
    enum { A4, B4, C4 };
    enum { A5, B5 };
    enum { A6, B6, C6 };
    enum { A7, B7 };

    add_vertex(C, G1); // global vertex C becomes local A1 for G1
    add_vertex(E, G1); // global vertex E becomes local B1 for G1
    add_vertex(F, G1); // global vertex F becomes local C1 for G1

    add_vertex(A, G2); // global vertex A becomes local A1 for G2
    add_vertex(B, G2); // global vertex B becomes local B1 for G2

    add_vertex(B, G3); // ...-||-...
    add_vertex(C, G3);

    add_vertex(A, G4);
    add_vertex(B, G4);
    add_vertex(E, G4);

    add_vertex(F, G5);
    add_vertex(D, G5);

    add_vertex(B, G6);
    add_vertex(D, G6);
    add_vertex(E, G6);

    add_vertex(F, G7);
    add_vertex(D, G7);

    add_edge(A, B, G0);
    add_edge(B, C, G0);
    add_edge(B, D, G0);
    add_edge(E, B, G0);
    add_edge(E, F, G0);
    add_edge(F, D, G0);

    add_edge(F, C, G1); // (A1,C1) is subgraph G1 local indices for (C,F).

    Graph::children_iterator ci, ci_end;
    Graph::edge_iterator ei, ei_end;

    int nj = 0;
    int g_n= 1;

    for (tie(ci, ci_end) = G0.children(); ci != ci_end; ++ci){

        for (tie(ei, ei_end) = edges(G7); ei != ei_end; ++ei){

            if( edge(G7.local_to_global(source(*ei,G7)), G7.local_to_global(target(*ei, G7)), *ci).second ) nj++;
        };
        if(nj == num_edges(G7)) std::cout<<"G7 is in"<<g_n<<std::endl;
        nj = 0;
        g_n++;
    };

    std::cout << "G0:" << std::endl;
    print_graph(G0, get(vertex_index, G0));
    print_edges2(G0, get(vertex_index, G0), get(edge_index, G0));
    std::cout << std::endl;

    int num = 1;
    for (boost::tie(ci, ci_end) = G0.children(); ci != ci_end; ++ci) {
        std::cout << "G" << num++ << ":" << std::endl;
        print_graph(*ci, get(vertex_index, *ci));
        print_edges2(*ci, get(vertex_index, *ci),get(edge_index, *ci));
        std::cout << std::endl;
    }



    return 0;
}

Answer 1

我想你想统计G7中包含边的子图的数量。

行

if (edge(G7.local_to_global(source(*ei, G7)), G7.local_to_global(target(*ei, G7)), *ci).second)

似乎是错误的，因为它使用全局顶点 ID 在 *ci 中找到一条边，这是它的任何子图。

doc

Each subgraph has its own vertex and edge descriptors, which we call local descriptors. We refer to root graph's vertex and edge descriptors as the global descriptors

这会更接近您的预期：

auto gs = G7.local_to_global(source(*ei, G7));
auto gt = G7.local_to_global(target(*ei, G7));

auto ls = ci->global_to_local(gs);
auto lt = ci->global_to_local(gt);

std::cout << "global (" << gs << "," << gt << ") local (" << ls << "," << gt << ")\n";

if (edge(ls, lt, *ci).second)
    nj++;

但是，global_to_local 断言顶点必须在子图中。所以真正的解决方法是

auto gs = G7.local_to_global(source(*ei, G7));
auto gt = G7.local_to_global(target(*ei, G7));
std::cout << "global (" << gs << "," << gt << ")\n";

auto ls = ci->find_vertex(gs);
auto lt = ci->find_vertex(gt);

if (ls.second && lt.second) {
    std::cout << "global (" << gs << "," << gt << ") local (" << ls.first << "," << lt.first << ")\n";

    if (edge(ls.first, lt.first, *ci).second)
        nj++;
}

演示

样式略有重构：

Live On Coliru

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/lookup_edge.hpp>
#include <boost/graph/subgraph.hpp>
#include <iostream>

using namespace boost;

typedef subgraph<adjacency_list<vecS, vecS, directedS, property<vertex_color_t, int>, property<edge_index_t, int>>>
    Graph;

int constexpr threshold = 3;
int constexpr size_of_database = 7;

template <typename G>
bool is_subgraph_present(G const& g, G const& other) {
    Graph::edge_iterator ei, ei_end;
    unsigned nj = 0;
    for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {

        auto gs = g.local_to_global(source(*ei, g));
        auto gt = g.local_to_global(target(*ei, g));
        //std::cout << "global (" << gs << "," << gt << ")\n";

        auto ls = other.find_vertex(gs);
        auto lt = other.find_vertex(gt);

        if (ls.second && lt.second) {
            //std::cout << "global (" << gs << "," << gt << ") local (" << ls.first << "," << lt.first << ")\n";

            if (edge(ls.first, lt.first, other).second)
                nj++;
        }
    }
    return nj == num_edges(g);
}


int main() {
    const int N = 6;
    enum { A, B, C, D, E, F }; // for conveniently refering to vertices in G0

    Graph G0(N);
    Graph& G1 = G0.create_subgraph();
    Graph& G2 = G0.create_subgraph();
    Graph& G3 = G0.create_subgraph();
    Graph& G4 = G0.create_subgraph();
    Graph& G5 = G0.create_subgraph();
    Graph& G6 = G0.create_subgraph();
    Graph& G7 = G0.create_subgraph();

    enum { A1, B1, C1 }; // for conveniently refering to vertices in G1
    enum { A2, B2 };     // for conveniently refering to vertices in G2
    enum { A3, B3 };
    enum { A4, B4, C4 };
    enum { A5, B5 };
    enum { A6, B6, C6 };
    enum { A7, B7 };

    add_vertex(C, G1); // global vertex C becomes local A1 for G1
    add_vertex(E, G1); // global vertex E becomes local B1 for G1
    add_vertex(F, G1); // global vertex F becomes local C1 for G1

    add_vertex(A, G2); // global vertex A becomes local A1 for G2
    add_vertex(B, G2); // global vertex B becomes local B1 for G2

    add_vertex(B, G3); // ...-||-...
    add_vertex(C, G3);

    add_vertex(A, G4);
    add_vertex(B, G4);
    add_vertex(E, G4);

    add_vertex(F, G5);
    add_vertex(D, G5);

    add_vertex(B, G6);
    add_vertex(D, G6);
    add_vertex(E, G6);

    add_vertex(F, G7);
    add_vertex(D, G7);

    add_edge(A, B, G0);
    add_edge(B, C, G0);
    add_edge(B, D, G0);
    add_edge(E, B, G0);
    add_edge(E, F, G0);
    add_edge(F, D, G0);

    //add_edge(F, C, G1); // (A1,C1) is subgraph G1 local indices for (C,F).

    Graph::children_iterator ci, ci_end;

    int g_n = 1;

    for (tie(ci, ci_end) = G0.children(); ci != ci_end; ++ci) {
        if (is_subgraph_present(G7, *ci)) {
            std::cout << "G7 is in G" << g_n << std::endl;
        }
        g_n++;
    }

    std::cout << "G0:" << std::endl;
    print_graph(G0, get(vertex_index, G0));
    print_edges2(G0, get(vertex_index, G0), get(edge_index, G0));
    std::cout << std::endl;

    int num = 1;
    for (boost::tie(ci, ci_end) = G0.children(); ci != ci_end; ++ci) {
        std::cout << "G" << num++ << ":" << std::endl;
        print_graph(*ci, get(vertex_index, *ci));
        print_edges2(*ci, get(vertex_index, *ci), get(edge_index, *ci));
        std::cout << std::endl;
    }
}

打印

7 is in G5
G7 is in G7
G0:
0 --> 1 
1 --> 2 3 
2 --> 
3 --> 
4 --> 1 5 
5 --> 3 
0(0,1) 1(1,2) 2(1,3) 3(4,1) 4(4,5) 5(5,3) 

G1:
0 --> 
1 --> 2 
2 --> 
4(1,2) 

G2:
0 --> 1 
1 --> 
0(0,1) 

G3:
0 --> 1 
1 --> 
1(0,1) 

G4:
0 --> 1 
1 --> 
2 --> 1 
0(0,1) 3(2,1) 

G5:
0 --> 1 
1 --> 
5(0,1) 

G6:
0 --> 1 
1 --> 
2 --> 0 
2(0,1) 3(2,0) 

G7:
0 --> 1 
1 --> 
5(0,1)

Boost图在子图中找到边

Boost graph find edge in subgraph

c++

boost

graph

subgraph

演示