CODEWITHSUNDEEP
c++boostgraphconnectivitysubgraph
KHALDOUN Mohsen
KHALDOUN Mohsen

Reputation: 57

subgraph and graph connectivity in boost

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.

Upvotes: 0

Views: 419

Answers (1)

KHALDOUN Mohsen
KHALDOUN Mohsen

Reputation: 142

well, here is two examples:

test if graph g1 is a subgraph of g2 (by giving g1 and g2 as a function parameter):

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

test graph g connectivity (by giving g as a function parameter):

bool graphconnexe(Graph const& g) {
    return num_edges(g) >= num_vertices(g) - 1;
}

Upvotes: 1

Related Questions