Получить подграф из Boost с определенным рисунком

Question

Получить подграф из Boost с определенным рисунком

Я ищу, чтобы извлечь шаблон цепочки из библиотеки графов повышения. Что-то вроде, если у меня есть граф со следующими ребрами и вершинами

Вершины: 0,1,2,3

Края:

 add_edge (0, 1, g);
add_edge (0, 3, g);
add_edge (1, 2, g);
add_edge (2, 3, g);

Я ищу заполнить подграф, который содержит записи, которые имеют шаблон A-> B-> C, чтобы я мог извлечь свойства из A-> B и B-> C, что-то вроде

i)  0->1->2
ii) 1->2->3

Любая помощь приветствуется. Благодарю.

1

boost c++filter subgraph

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я думаю, что вы хотите изоморфизм подграфа: http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/vf2_sub_graph_iso.html

Есть пример приложения тоже

//=======================================================================
// Copyright (C) 2012 Flavio De Lorenzi ([email protected])
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

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

int main() {
typedef property<edge_name_t, char> edge_property;
typedef property<vertex_name_t, char, property<vertex_index_t, int> > vertex_property;

// Using a vecS graphs => the index maps are implicit.
typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph_type;

// Build graph1
graph_type graph1;

add_vertex(vertex_property('a'), graph1);
add_vertex(vertex_property('a'), graph1);
add_vertex(vertex_property('a'), graph1);

add_edge(0, 1, edge_property('b'), graph1);
add_edge(0, 1, edge_property('b'), graph1);
add_edge(0, 1, edge_property('d'), graph1);

add_edge(1, 2, edge_property('s'), graph1);

add_edge(2, 2, edge_property('l'), graph1);
add_edge(2, 2, edge_property('l'), graph1);

// Build graph2
graph_type graph2;

add_vertex(vertex_property('a'), graph2);
add_vertex(vertex_property('a'), graph2);
add_vertex(vertex_property('a'), graph2);
add_vertex(vertex_property('a'), graph2);
add_vertex(vertex_property('a'), graph2);
add_vertex(vertex_property('a'), graph2);

add_edge(0, 1, edge_property('a'), graph2);
add_edge(0, 1, edge_property('a'), graph2);
add_edge(0, 1, edge_property('b'), graph2);

add_edge(1, 2, edge_property('s'), graph2);

add_edge(2, 3, edge_property('b'), graph2);
add_edge(2, 3, edge_property('d'), graph2);
add_edge(2, 3, edge_property('b'), graph2);

add_edge(3, 4, edge_property('s'), graph2);

add_edge(4, 4, edge_property('l'), graph2);
add_edge(4, 4, edge_property('l'), graph2);

add_edge(4, 5, edge_property('c'), graph2);
add_edge(4, 5, edge_property('c'), graph2);
add_edge(4, 5, edge_property('c'), graph2);

add_edge(5, 0, edge_property('s'), graph2);

// create predicates
typedef property_map<graph_type, vertex_name_t>::type vertex_name_map_t;
typedef property_map_equivalent<vertex_name_map_t, vertex_name_map_t> vertex_comp_t;
vertex_comp_t vertex_comp =
make_property_map_equivalent(get(vertex_name, graph1), get(vertex_name, graph2));

typedef property_map<graph_type, edge_name_t>::type edge_name_map_t;
typedef property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
edge_comp_t edge_comp =
make_property_map_equivalent(get(edge_name, graph1), get(edge_name, graph2));

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

// Print out all subgraph isomorphism mappings between graph1 and graph2.
// Function vertex_order_by_mult is used to compute the order of
// vertices of graph1. This is the order in which the vertices are examined
// during the matching process.
vf2_subgraph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));

return 0;
}

0