BGL 的 algorithm（十）
isomorphism
判定两个图是否同构是一个 NP-hard 的问题，BGL 提供了一个简单但是很慢的的算法（
#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
int
main() {
using namespace boost;
const int n = 12;
typedef adjacency_list<vecS, listS, undirectedS,
property<vertex_index_t, int> > graph_t;
graph_t g1(n), g2(n);
std::vector<graph_traits<graph_t>::vertex_descriptor> v1(n), v2(n);
property_map<graph_t, vertex_index_t>::type
v1_index_map = get(vertex_index, g1),
v2_index_map = get(vertex_index, g2);
graph_traits<graph_t>::vertex_iterator i, end;
int id = 0;
for (boost::tie(i, end) = vertices(g1); i != end; ++i, ++id) {
put(v1_index_map, *i, id);
v1[id] = *i;
}
id = 0;
for (boost::tie(i, end) = vertices(g2); i != end; ++i, ++id) {
put(v2_index_map, *i, id);
v2[id] = *i;
}
add_edge(v1[0], v1[1], g1); add_edge(v1[1], v1[2], g1);
add_edge(v1[0], v1[2], g1);
add_edge(v1[3], v1[4], g1); add_edge(v1[4], v1[5], g1);
add_edge(v1[5], v1[6], g1); add_edge(v1[6], v1[3], g1);
add_edge(v1[7], v1[8], g1); add_edge(v1[8], v1[9], g1);
add_edge(v1[9], v1[10], g1);
add_edge(v1[10], v1[11], g1); add_edge(v1[11], v1[7], g1);
add_edge(v2[9], v2[10], g2); add_edge(v2[10], v2[11], g2);
add_edge(v2[11], v2[9], g2);
add_edge(v2[0], v2[1], g2); add_edge(v2[1], v2[3], g2);
add_edge(v2[3], v2[2], g2); add_edge(v2[2], v2[0], g2);
add_edge(v2[4], v2[5], g2); add_edge(v2[5], v2[7], g2);
add_edge(v2[7], v2[8], g2);
add_edge(v2[8], v2[6], g2); add_edge(v2[6], v2[4], g2);
std::vector<graph_traits<graph_t>::vertex_descriptor> f(n);
bool ret = isomorphism
(g1, g2, isomorphism_map
(make_iterator_property_map(f.begin(), v1_index_map, f[0])));
std::cout << "isomorphic? " << ret << std::endl;
std::cout << "f: ";
for (std::size_t v = 0; v != f.size(); ++v)
std::cout << get(get(vertex_index, g2), f[v]) << " ";
std::cout << std::endl;
return 0;
}
Common subgraph
这里提供了 McGregor 算法，用于输出两个图所有同构的子图，这只需要 
#include <fstream>
#include <iostream>
#include <string>
#include <boost/lexical_cast.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/mcgregor_common_subgraphs.hpp>
#include <boost/property_map/shared_array_property_map.hpp>
using namespace boost;
template <typename Graph>
struct example_callback {
typedef typename graph_traits<Graph>::vertices_size_type VertexSizeFirst;
example_callback(const Graph& graph1) :
m_graph1(graph1) { }
template <typename CorrespondenceMapFirstToSecond,
typename CorrespondenceMapSecondToFirst>
bool
operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
VertexSizeFirst subgraph_size) {
// Fill membership map for first graph
typedef typename property_map<Graph, vertex_index_t>::type VertexIndexMap;
typedef shared_array_property_map<bool, VertexIndexMap> MembershipMap;
MembershipMap membership_map1(num_vertices(m_graph1),
get(vertex_index, m_graph1));
fill_membership_map<Graph>(m_graph1,
correspondence_map_1_to_2,
membership_map1);
// Generate filtered graphs using membership map
typedef typename membership_filtered_graph_traits<Graph, MembershipMap>::graph_type
MembershipFilteredGraph;
MembershipFilteredGraph subgraph1 =
make_membership_filtered_graph(m_graph1, membership_map1);
// Print the graph out to the console
std::cout << "Found common subgraph (size " << subgraph_size
<< ")" << std::endl;
print_graph(subgraph1);
std::cout << std::endl;
// Explore the entire space
return (true);
}
private:
const Graph& m_graph1;
VertexSizeFirst m_max_subgraph_size;
};
int
main (int argc, char *argv[]) {
// Using a vecS graph here so that we don't have to mess around with
// a vertex index map; it will be implicit.
typedef adjacency_list<listS, vecS, directedS,
property<vertex_name_t, unsigned int,
property<vertex_index_t, unsigned int> >,
property<edge_name_t, unsigned int> > Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::edge_descriptor Edge;
typedef property_map<Graph, vertex_name_t>::type VertexNameMap;
typedef property_map<Graph, edge_name_t>::type EdgeNameMap;
// Test maximum and unique variants on known graphs
Graph graph_simple1, graph_simple2;
example_callback<Graph> user_callback(graph_simple1);
VertexNameMap vname_map_simple1 = get(vertex_name, graph_simple1);
VertexNameMap vname_map_simple2 = get(vertex_name, graph_simple2);
// Graph that looks like a triangle
put(vname_map_simple1, add_vertex(graph_simple1), 1);
put(vname_map_simple1, add_vertex(graph_simple1), 2);
put(vname_map_simple1, add_vertex(graph_simple1), 3);
add_edge(0, 1, graph_simple1);
add_edge(0, 2, graph_simple1);
add_edge(1, 2, graph_simple1);
std::cout << "First graph:" << std::endl;
print_graph(graph_simple1);
std::cout << std::endl;
// Triangle with an extra vertex
put(vname_map_simple2, add_vertex(graph_simple2), 1);
put(vname_map_simple2, add_vertex(graph_simple2), 2);
put(vname_map_simple2, add_vertex(graph_simple2), 3);
put(vname_map_simple2, add_vertex(graph_simple2), 4);
add_edge(0, 1, graph_simple2);
add_edge(0, 2, graph_simple2);
add_edge(1, 2, graph_simple2);
add_edge(1, 3, graph_simple2);
std::cout << "Second graph:" << std::endl;
print_graph(graph_simple2);
std::cout << std::endl;
// All subgraphs
std::cout << "mcgregor_common_subgraphs:" << std::endl;
mcgregor_common_subgraphs
(graph_simple1, graph_simple2, true, user_callback,
vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
std::cout << std::endl;
// Unique subgraphs
std::cout << "mcgregor_common_subgraphs_unique:" << std::endl;
mcgregor_common_subgraphs_unique
(graph_simple1, graph_simple2, true, user_callback,
vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
std::cout << std::endl;
// Maximum subgraphs
std::cout << "mcgregor_common_subgraphs_maximum:" << std::endl;
mcgregor_common_subgraphs_maximum
(graph_simple1, graph_simple2, true, user_callback,
vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
std::cout << std::endl;
// Maximum, unique subgraphs
std::cout << "mcgregor_common_subgraphs_maximum_unique:" << std::endl;
mcgregor_common_subgraphs_maximum_unique
(graph_simple1, graph_simple2, true, user_callback,
vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
return 0;
}
最近碰到一个问题跟这个有点像，但是似乎是要求去掉重复结构后的公共部分。
另外，最近不少近似算法都是跟 graph 紧密相关的，可以考虑利用 BGL 的框架实现几个练练手。
——————
That these made war with Bera king of Sodom, and with Birsha king of Gomorrah, Shinab king of Admah, and Shemeber king of Zeboiim, and the king of Bela, which is Zoar.
