subgraph and graph connectivity in boost

Question

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.

What would it mean for connectivity to be represented by a boolean? Would you consider it to be true if and only if g were totally connected? — Austin Mullins
I see you've taken to not showing any attempt at code anymore, and instead just asking for code? As written this question is way too broad, and I see no relation to Boost or C++. Edit I was confused for a bit. Then I noticed the second account. Assuming you're the same guy — sehe
@sehe I'm just asking if there are some predefined functions to do this in BOOST then i will put the code — KHALDOUN Mohsen
Please edit the question to make your goal more clear and include the code you tried. Questions about what functions are in a specific library are best answered by reviewing the documentation for that library. — Austin Mullins

KHALDOUN Mohsen KHALDOUN Mohsen · Accepted Answer · 2015-03-21T08:12:25

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

subgraph and graph connectivity in boost

1 Answers