Слияние графиков с использованием графа ускорения

Question

Как сделать добавить границу между двумя различными графиками, используя библиотеку Boost Graph. Я видел код для слияния/сжатия двух вершин, но я не хочу этого делать. Я хочу связать конечную вершину одного графа с начальной вершиной другого графа и сделать его одним графиком. Оба графика одного типа.

Пожалуйста, помогите ...

Answer 1

Прежде всего, мы должны признать, что полученный граф является единым объектом. Я предполагаю, что вы хотите, чтобы он был того же типа Graph, что и ваши исходные два графика g1 и g2. Это означает, что у вас есть выбор сделать одно из следующего: График g = g1 + g2 или g1 + = g2 (оба варианта, конечно, в псевдокоде).

В любом случае результат будет содержать копию второго графика, а не «оригинальный» объект графа g2.

BGL фактически предоставляет вам функцию точно сделать это, а именно, функция "copy_graph"

Вы можете сделать что-то вроде следующего

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/copy.hpp> 


typedef boost::adjacency_list<> Graph; 
typedef Graph::vertex_descriptor vertex_t; 

void merging(Graph & g1, vertex_t v_in_g1, const Graph & g2, vertex_t u_in_g2) 
{ 
    typedef boost::property_map<Graph, boost::vertex_index_t>::type index_map_t; 


    //for simple adjacency_list<> this type would be more efficient: 
    typedef boost::iterator_property_map<typename std::vector<vertex_t>::iterator, 
     index_map_t,vertex_t,vertex_t&> IsoMap; 

    //for more generic graphs, one can try //typedef std::map<vertex_t, vertex_t> IsoMap; 
    IsoMap mapV; 
    boost::copy_graph(g2, g1, boost::orig_to_copy(mapV)); //means g1 += g2 

    vertex_t u_in_g1 = mapV[u_in_g2]; 
    boost::add_edge(v_in_g1, u_in_g1, g1); 
} 

Смотрите также copy a graph (adjacency_list) to another one