1

我正在使用boost库编写用于图挖掘的代码，并且我想使用该vf2_sub_graph_iso函数，如果存在图子图同构，则通常vf2_subgraph_iso返回，否则返回，但在我的情况下，我想让它仅在图完全相同时返回（结构和标签），在官方文档中提到：和谓词用于测试边和顶点是否等价。truefalsetrueEdgeEquivalencePredicateVertexEquivalencePredicate

这是图形文件：3test.txt，这是我的代码的一部分：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/config.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/graph_utility.hpp>

#include <fstream>
#include <iostream>
#include <vector>


//for mmap:
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>

using namespace std;
using namespace boost;


//==========STRUCTURES==========
// vertex
struct VertexProperties {
    int id;
    int label;
    VertexProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
};

// edge
struct EdgeProperties {
    unsigned label;
    EdgeProperties(unsigned l = 0) :label(l) {}
};

// Graph
struct GraphProperties {
    unsigned id;
    unsigned label;
    GraphProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
};

// adjency list
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties,
GraphProperties> Graph;

// descriptors

typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef std::pair<boost::graph_traits<Graph>::edge_descriptor, bool> edge_t;
// iterators
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::edge_iterator edge_iter;
typedef std::pair<edge_iter, edge_iter> edge_pair;


//*********global variables*************


vector<Graph> dataG;



//=================callback used fro subgraph_iso=================================================================
// Default print_callback
template <typename Graph1,typename Graph2>

  struct my_callback {

    my_callback(const Graph1& graph1, const Graph2& graph2)
      : graph1_(graph1), graph2_(graph2) {}

    template <typename CorrespondenceMap1To2,
              typename CorrespondenceMap2To1>
    bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {

      return true;
    }

  private:
    const Graph1& graph1_;
    const Graph2& graph2_;
  };


//==========handle_error==========
void handle_error(const char *msg) {
    perror(msg);
    exit(255);
}


//============READ ALL THE FILE AND RETURN A STRING===================
const char *readfromfile(const char *fname, size_t &length) {
    int fd = open(fname, O_RDONLY);
    if (fd == -1)
        handle_error("open");

    // obtain file size
    struct stat sb;
    if (fstat(fd, &sb) == -1)
        handle_error("fstat");

    length = sb.st_size;

    const char *addr = static_cast<const char *>(mmap(NULL, length, PROT_READ, MAP_PRIVATE, fd, 0u));
    if (addr == MAP_FAILED)
        handle_error("mmap");

    // TODO close fd at some point in time, call munmap(...)
    return addr;
}
//==========SPLIT THE STRING BY NEWLINE (\n) ==========
vector<string> splitstringtolines(string const& str) {

    std::vector<string> split_vector;
    split(split_vector, str, is_any_of("\n"));

    return split_vector;
}

//============Get a string starting from pos============
string getpos(int const& pos, string const& yy) {
    size_t i = pos;
    string str;
    for (; ((yy[i] != ' ') && (i < yy.length())); i++) {str += yy[i];}
    return str;
}
//==================read string vector and return graphs vector===================
std::vector<Graph> creategraphs(std::vector<string> const& fichlines) {

    for (string yy : fichlines) {
        switch (yy[0]) {
            case 't': {
                string str2 = getpos(4, yy);
                unsigned gid = atoi(str2.c_str());
                dataG.emplace_back(GraphProperties(gid, gid));

            } break;
            case 'v': {
                assert(!dataG.empty()); // assert will terminate the program  if its argument turns out to be false
                // cout<<yy<<endl;
                int vId, vLabel;
                string vvv = getpos(2, yy);
                vId = atoi(vvv.c_str());
                string vvvv = getpos((int)vvv.length() + 3, yy);
                // cout<<vvvv<<endl;
                vLabel = atoi(vvvv.c_str());
                boost::add_vertex(VertexProperties(vId, vLabel), dataG.back());
            }

                break;

            case 'e': { // cout<<yy<<endl;
                assert(!dataG.empty()); // assert will terminate the program  if its argument turns out to be false

                int fromId, toId, eLabel;
                string eee = getpos(2, yy);
                // cout<<eee<<endl;
                fromId = atoi(eee.c_str());
                string eee2 = getpos((int)eee.length() + 3, yy);
                // cout<<eee2<<endl;
                toId = atoi(eee2.c_str());
                int c = (int)eee.length() + (int)eee2.length() + 4;
                //    cout<<c<<endl;
                string eee3 = getpos(c, yy);
                //  cout<<eee3<<endl;
                eLabel = atoi(eee3.c_str());
                for (size_t i = 0; i < num_vertices(dataG.back()); ++i) // size_t vertice number in the graph
                {
                    if(dataG.back()[i].id==fromId) fromId=i;
                    else if(dataG.back()[i].id==toId) toId=i;
                }

                boost::add_edge(fromId, toId, EdgeProperties(eLabel), dataG.back());

            } break;
        }
    }

    return dataG;
}

//==============================M A I N   P R O G R A M =======================================
int main()
{

    size_t length;


    std::vector<Graph> dataG =creategraphs(splitstringtolines(readfromfile("3test.txt", length)));


    my_callback<Graph, Graph> my_callback(dataG[0], dataG[3]);
  cout<<"equal(dataG[0], dataG[3],my_callback)="<<vf2_sub_graph_iso(dataG[0], dataG[3],my_callback)<<endl;



}

如何在my_callback我的案例中使用属性映射来实现功能等效？

更新

这是一个简单的图形文件，仅包含 2 个图形：

t # 0
v 0 35
v 1 47
v 2 15
v 3 14
v 4 86
e 0 1 10
e 1 2 77
e 1 3 17
e 4 2 43
t # 1
v 0 35
v 1 47
v 2 15
v 3 14
v 4 86
e 0 1 10
e 1 2 7
e 1 3 17
e 4 2 4

这些图具有相同的结构但不同的标签，因此此代码必须返回 false 而不是 true：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/config.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/tuple/tuple_comparison.hpp>

#include <fstream>
#include <iostream>
#include <vector>


//for mmap:
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>

using namespace boost;

//==========STRUCTURES==========
// vertex
struct VertexProperties {
    int id;
    int label;
    VertexProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}

    bool operator==(VertexProperties const& other) const {
        return tie(id, label) == tie(other.id, other.label);
    }
};

// edge
struct EdgeProperties {
    unsigned label;
    EdgeProperties(unsigned l = 0) :label(l) {}

    bool operator==(EdgeProperties const& other) const {
        return tie(label) == tie(other.label);
    }
};

// Graph
struct GraphProperties {
    unsigned id;
    unsigned label;
    GraphProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
};

// adjency list
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties,
GraphProperties> Graph;

// descriptors

typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef std::pair<boost::graph_traits<Graph>::edge_descriptor, bool> edge_t;
// iterators
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::edge_iterator edge_iter;
typedef std::pair<edge_iter, edge_iter> edge_pair;


//*********global variables*************
std::vector<Graph> dataG;

//=================callback used fro subgraph_iso=================================================================
// Default print_callback
template <typename Graph1,typename Graph2>

  struct my_callback {

    my_callback(const Graph1& graph1, const Graph2& graph2)
      : graph1_(graph1), graph2_(graph2) {}

    template <typename CorrespondenceMap1To2,
              typename CorrespondenceMap2To1>
    bool operator()(CorrespondenceMap1To2 /*f*/, CorrespondenceMap2To1) const {
      return true;
    }

  private:
    const Graph1& graph1_;
    const Graph2& graph2_;
  };


//==========handle_error==========
void handle_error(const char *msg) {
    perror(msg);
    exit(255);
}


//============READ ALL THE FILE AND RETURN A STRING===================
const char *readfromfile(const char *fname, size_t &length) {
    int fd = open(fname, O_RDONLY);
    if (fd == -1)
        handle_error("open");

    // obtain file size
    struct stat sb;
    if (fstat(fd, &sb) == -1)
        handle_error("fstat");

    length = sb.st_size;

    const char *addr = static_cast<const char *>(mmap(NULL, length, PROT_READ, MAP_PRIVATE, fd, 0u));
    if (addr == MAP_FAILED)
        handle_error("mmap");

    // TODO close fd at some point in time, call munmap(...)
    return addr;
}
//==========SPLIT THE STRING BY NEWLINE (\n) ==========
std::vector<std::string> splitstringtolines(std::string const& str) {

    std::vector<std::string> split_vector;
    split(split_vector, str, is_any_of("\n"));

    return split_vector;
}

//============Get a string starting from pos============
std::string getpos(int const& pos, std::string const& yy) {
    size_t i = pos;
    std::string str;
    for (; ((yy[i] != ' ') && (i < yy.length())); i++) {str += yy[i];}
    return str;
}
//==================read string vector and return graphs vector===================
std::vector<Graph> creategraphs(std::vector<std::string> const& fichlines) {

    for (std::string yy : fichlines) {
        switch (yy[0]) {
            case 't': {
                std::string str2 = getpos(4, yy);
                unsigned gid = atoi(str2.c_str());
                dataG.emplace_back(GraphProperties(gid, gid));

            } break;
            case 'v': {
                assert(!dataG.empty()); // assert will terminate the program  if its argument turns out to be false
                // std::cout<<yy<<std::endl;
                int vId, vLabel;
                std::string vvv = getpos(2, yy);
                vId = atoi(vvv.c_str());
                std::string vvvv = getpos((int)vvv.length() + 3, yy);
                // std::cout<<vvvv<<std::endl;
                vLabel = atoi(vvvv.c_str());
                boost::add_vertex(VertexProperties(vId, vLabel), dataG.back());
            }

                break;

            case 'e': { // std::cout<<yy<<std::endl;
                assert(!dataG.empty()); // assert will terminate the program  if its argument turns out to be false

                int fromId, toId, eLabel;
                std::string eee = getpos(2, yy);
                // std::cout<<eee<<std::endl;
                fromId = atoi(eee.c_str());
                std::string eee2 = getpos((int)eee.length() + 3, yy);
                // std::cout<<eee2<<std::endl;
                toId = atoi(eee2.c_str());
                int c = (int)eee.length() + (int)eee2.length() + 4;
                //    std::cout<<c<<std::endl;
                std::string eee3 = getpos(c, yy);
                //  std::cout<<eee3<<std::endl;
                eLabel = atoi(eee3.c_str());
                for (size_t i = 0; i < num_vertices(dataG.back()); ++i) // size_t vertice number in the graph
                {
                    if(dataG.back()[i].id==fromId) fromId=i;
                    else if(dataG.back()[i].id==toId) toId=i;
                }

                boost::add_edge(fromId, toId, EdgeProperties(eLabel), dataG.back());

            } break;
        }
    }

    return dataG;
}

template <typename Graph1, typename Graph2>
bool my_bundled_graph_iso(Graph1 const& graph_small, Graph2 const& graph_large) {
    auto const vos = boost::copy_range<std::vector<Graph::vertex_descriptor> >(vertices(graph_small));

    return vf2_subgraph_iso(graph_small, graph_large, my_callback<Graph, Graph>(graph_small, graph_large), vos,
            edges_equivalent   (make_property_map_equivalent(boost::get(edge_bundle,   graph_small), boost::get(edge_bundle,   graph_large))).
            vertices_equivalent(make_property_map_equivalent(boost::get(vertex_bundle, graph_small), boost::get(vertex_bundle, graph_large)))
            );
}

//==============================M A I N   P R O G R A M =======================================
int main() {
    size_t length;
    std::vector<Graph> dataG = creategraphs(splitstringtolines(readfromfile("2.txt", length)));
    std::cout << std::boolalpha << my_bundled_graph_iso(dataG[0], dataG[1]) << std::endl;
}

更新2

我没有在问题中提到，即使没有 id（在不同的图中），顶点也可以相同的小先例示例。

4

1 回答 1

4

好的，让我们剖析文档。

为了传递非默认实现EdgeEquivalencePredicate，VertexEquivalencePredicate您需要第二个重载：

bool vf2_subgraph_iso(const GraphSmall& graph_small,
      const GraphLarge& graph_large,
      SubGraphIsoMapCallback user_callback,
      const VertexOrderSmall& vertex_order_small,
      const bgl_named_params<Param, Tag, Rest>& params)

这意味着您至少需要一个参数来匹配vertex_order_small和params。让我们先做最少的工作和供应vertex_order_small：

较小（第一个）图 graph_small 的有序顶点。在匹配过程中，顶点按照给出的顺序进行检查vertex_order_small。类型VertexOrderSmall必须是ContainerConcept具有值类型的模型graph_traits<GraphSmall>::vertex_descriptor。

默认 顶点按入/出度的多重性排序。

让我们以默认顺序传递一个顶点描述符向量：

auto const& graph_small = dataG[0];
auto const& graph_large = dataG[3];

auto vos = boost::copy_range<std::vector<Graph::vertex_descriptor> >(vertices(graph_small));
bool iso = vf2_graph_iso(graph_small, graph_large, my_callback, vos, no_named_parameters());

下一步，添加命名参数，例如：[¹]

bool iso = vf2_graph_iso(graph_small, graph_large, my_callback, vos, 
        edges_equivalent   ([&graph_small, &graph_large](Graph::edge_descriptor small_ed, Graph::edge_descriptor large_ed) {
            return graph_small[small_ed] == graph_large[large_ed];
        }).
        vertices_equivalent([&graph_small, &graph_large](Graph::vertex_descriptor small_vd, Graph::vertex_descriptor large_vd) { 
            return graph_small[small_vd] == graph_large[large_vd];
        })
    );

make_property_map_equivalent作为此处记录的最终顶部使用：

bool iso = vf2_graph_iso(graph_small, graph_large, my_callback, vos, 
        edges_equivalent   (make_property_map_equivalent(boost::get(edge_bundle,   graph_small), boost::get(edge_bundle,   graph_large))).
        vertices_equivalent(make_property_map_equivalent(boost::get(vertex_bundle, graph_small), boost::get(vertex_bundle, graph_large)))
    );

查看所有三个步骤Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/config.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/tuple/tuple_comparison.hpp>

#include <fstream>
#include <iostream>
#include <vector>


//for mmap:
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>

using namespace boost;

//==========STRUCTURES==========
// vertex
struct VertexProperties {
    int id;
    int label;
    VertexProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}

    bool operator==(VertexProperties const& other) const {
        return tie(id, label) == tie(other.id, other.label);
    }
};

// edge
struct EdgeProperties {
    unsigned label;
    EdgeProperties(unsigned l = 0) :label(l) {}

    bool operator==(EdgeProperties const& other) const {
        return tie(label) == tie(other.label);
    }
};

// Graph
struct GraphProperties {
    unsigned id;
    unsigned label;
    GraphProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
};

// adjency list
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties,
GraphProperties> Graph;

// descriptors

typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef std::pair<boost::graph_traits<Graph>::edge_descriptor, bool> edge_t;
// iterators
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::edge_iterator edge_iter;
typedef std::pair<edge_iter, edge_iter> edge_pair;


//*********global variables*************
std::vector<Graph> dataG;

//=================callback used fro subgraph_iso=================================================================
// Default print_callback
template <typename Graph1,typename Graph2>

  struct my_callback {

    my_callback(const Graph1& graph1, const Graph2& graph2)
      : graph1_(graph1), graph2_(graph2) {}

    template <typename CorrespondenceMap1To2,
              typename CorrespondenceMap2To1>
    bool operator()(CorrespondenceMap1To2 /*f*/, CorrespondenceMap2To1) const {
      return true;
    }

  private:
    const Graph1& graph1_;
    const Graph2& graph2_;
  };


//==========handle_error==========
void handle_error(const char *msg) {
    perror(msg);
    exit(255);
}


//============READ ALL THE FILE AND RETURN A STRING===================
const char *readfromfile(const char *fname, size_t &length) {
    int fd = open(fname, O_RDONLY);
    if (fd == -1)
        handle_error("open");

    // obtain file size
    struct stat sb;
    if (fstat(fd, &sb) == -1)
        handle_error("fstat");

    length = sb.st_size;

    const char *addr = static_cast<const char *>(mmap(NULL, length, PROT_READ, MAP_PRIVATE, fd, 0u));
    if (addr == MAP_FAILED)
        handle_error("mmap");

    // TODO close fd at some point in time, call munmap(...)
    return addr;
}
//==========SPLIT THE STRING BY NEWLINE (\n) ==========
std::vector<std::string> splitstringtolines(std::string const& str) {

    std::vector<std::string> split_vector;
    split(split_vector, str, is_any_of("\n"));

    return split_vector;
}

//============Get a string starting from pos============
std::string getpos(int const& pos, std::string const& yy) {
    size_t i = pos;
    std::string str;
    for (; ((yy[i] != ' ') && (i < yy.length())); i++) {str += yy[i];}
    return str;
}
//==================read string vector and return graphs vector===================
std::vector<Graph> creategraphs(std::vector<std::string> const& fichlines) {

    for (std::string yy : fichlines) {
        switch (yy[0]) {
            case 't': {
                std::string str2 = getpos(4, yy);
                unsigned gid = atoi(str2.c_str());
                dataG.emplace_back(GraphProperties(gid, gid));

            } break;
            case 'v': {
                assert(!dataG.empty()); // assert will terminate the program  if its argument turns out to be false
                // std::cout<<yy<<std::endl;
                int vId, vLabel;
                std::string vvv = getpos(2, yy);
                vId = atoi(vvv.c_str());
                std::string vvvv = getpos((int)vvv.length() + 3, yy);
                // std::cout<<vvvv<<std::endl;
                vLabel = atoi(vvvv.c_str());
                boost::add_vertex(VertexProperties(vId, vLabel), dataG.back());
            }

                break;

            case 'e': { // std::cout<<yy<<std::endl;
                assert(!dataG.empty()); // assert will terminate the program  if its argument turns out to be false

                int fromId, toId, eLabel;
                std::string eee = getpos(2, yy);
                // std::cout<<eee<<std::endl;
                fromId = atoi(eee.c_str());
                std::string eee2 = getpos((int)eee.length() + 3, yy);
                // std::cout<<eee2<<std::endl;
                toId = atoi(eee2.c_str());
                int c = (int)eee.length() + (int)eee2.length() + 4;
                //    std::cout<<c<<std::endl;
                std::string eee3 = getpos(c, yy);
                //  std::cout<<eee3<<std::endl;
                eLabel = atoi(eee3.c_str());
                for (size_t i = 0; i < num_vertices(dataG.back()); ++i) // size_t vertice number in the graph
                {
                    if(dataG.back()[i].id==fromId) fromId=i;
                    else if(dataG.back()[i].id==toId) toId=i;
                }

                boost::add_edge(fromId, toId, EdgeProperties(eLabel), dataG.back());

            } break;
        }
    }

    return dataG;
}

//==============================M A I N   P R O G R A M =======================================
int main() {
    size_t length;
    std::cout << std::boolalpha;
    std::vector<Graph> dataG = creategraphs(splitstringtolines(readfromfile("3test.txt", length)));
    auto const& graph_small = dataG[0];
    auto const& graph_large = dataG[3];

    my_callback<Graph, Graph> my_callback(graph_small, graph_large);
    std::cout << "equal(graph_small, graph_large,my_callback)=" << vf2_graph_iso(graph_small, graph_large, my_callback) << std::endl;

    // first step
    {
        auto vos = boost::copy_range<std::vector<Graph::vertex_descriptor> >(vertices(graph_small));
        std::cout << "equal(graph_small, graph_large,my_callback)=" << vf2_graph_iso(graph_small, graph_large, my_callback, vos, no_named_parameters()) << std::endl;
    }

    // second step
    {
        auto vos = boost::copy_range<std::vector<Graph::vertex_descriptor> >(vertices(graph_small));

        bool iso = vf2_graph_iso(graph_small, graph_large, my_callback, vos, 
                edges_equivalent   ([&graph_small, &graph_large](Graph::edge_descriptor small_ed, Graph::edge_descriptor large_ed) {
                    return graph_small[small_ed] == graph_large[large_ed];
                }).
                vertices_equivalent([&graph_small, &graph_large](Graph::vertex_descriptor small_vd, Graph::vertex_descriptor large_vd) { 
                    return graph_small[small_vd] == graph_large[large_vd];
                })
            );

        std::cout << "equal(graph_small, graph_large,my_callback)=" << iso << std::endl;
    }

    // third step
    {
        auto vos = boost::copy_range<std::vector<Graph::vertex_descriptor> >(vertices(graph_small));

        bool iso = vf2_graph_iso(graph_small, graph_large, my_callback, vos, 
                edges_equivalent   (make_property_map_equivalent(boost::get(edge_bundle,   graph_small), boost::get(edge_bundle,   graph_large))).
                vertices_equivalent(make_property_map_equivalent(boost::get(vertex_bundle, graph_small), boost::get(vertex_bundle, graph_large)))
            );

        std::cout << "equal(graph_small, graph_large,my_callback)=" << iso << std::endl;
    }
}

打印输出：

equal(graph_small, graph_large,my_callback)=true
equal(graph_small, graph_large,my_callback)=true
equal(graph_small, graph_large,my_callback)=false
equal(graph_small, graph_large,my_callback)=false

[¹] 当然，假设您operator==为边缘和顶点属性类型实现（请参阅完整列表）

于 2015-05-04T09:16:20.047 回答