0

I want to know if there are some predefined functions to get those two tests results as a boolean in BOOST, then i will put the code (in an UPDATE).

1- if graph g1 is a subgraph of g2 (by giving g1 and g2 as a function parameter).

here http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/subgraph.html subgraph is used as a class not a function.

2- graph g connectivity (by giving g as a function parameter).

In the official documentation here http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/connected_components.html I found that connected_components function computes how many connected components are in the graph, and assigning each component an integer label. The algorithm then records which component each vertex in the graph belongs to by recording the component number in the component property map.

4

1 回答 1

1

好吧，这里有两个例子：

测试图 g1 是否是 g2 的子图（通过将 g1 和 g2 作为函数参数）：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
using namespace std;
using namespace boost;

struct my_callback 
{
    template <typename CorrespondenceMap1To2, typename CorrespondenceMap2To1>
    bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1 g) const 
    {
        return false;
    }
};


int main() {

  typedef adjacency_list<setS, vecS, bidirectionalS> graph_type;

  // Build graph1
  int num_vertices1 = 8; graph_type graph1(num_vertices1);
  add_edge(0, 6, graph1); 
  add_edge(0, 7, graph1);
  add_edge(1, 5, graph1); 
  add_edge(1, 7, graph1);
  add_edge(2, 4, graph1); 
  add_edge(2, 5, graph1); 
  add_edge(2, 6, graph1);
  add_edge(3, 4, graph1);

  // Build graph2
  int num_vertices2 = 9; graph_type graph2(num_vertices2);
  add_edge(0, 6, graph2); 
  add_edge(0, 8, graph2);
  add_edge(1, 5, graph2); 
  add_edge(1, 7, graph2);
  add_edge(2, 4, graph2); 
  add_edge(2, 7, graph2); 
  add_edge(2, 8, graph2);
  add_edge(3, 4, graph2); 
  add_edge(3, 5, graph2); 
  add_edge(3, 6, graph2);

  // Create callback to print mappings
  //vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);

  // Print out all subgraph isomorphism mappings between graph1 and graph2.
  // Vertices and edges are assumed to be always equivalent.
  cout<<vf2_subgraph_iso(graph1, graph2,my_callback())<<endl;

  return 0;
}

测试图 g 连通性（通过将 g 作为函数参数）：

bool graphconnexe(Graph const& g) {
    return num_edges(g) >= num_vertices(g) - 1;
}
于 2015-03-21T08:12:25.160 回答