📄 isomorphism-impl.w
字号:
}
j_1 -> fj_1[style=dotted]
j_2 -> fj_2[style=dotted]
}
@}
In the case where there were no edges in $E_1[k] - E_1[k-1]$, then $M
= V_2 - S$, so here we insert all the vertices from $V_2$ that are not
in $S$.
@d Perform $M \leftarrow V_2 - S$
@{
typename graph_traits<Graph2>::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi)
if (not_in_S[*vi])
potential_matches.push_back(*vi);
@}
For each vertex $v$ in the potential matches $M$, we will create an
extended isomorphism $f_k = f_{k-1} \union \pair{k}{v}$. First
we create a local copy of $f_{k-1}$.
@d Create a copy of $f_{k-1}$ which will become $f_k$
@{
std::vector<vertex2_t> my_f_vec(num_vertices(g1));
typedef typename std::vector<vertex2_t>::iterator vec_iter;
iterator_property_map<vec_iter, IndexMap1, vertex2_t, vertex2_t&>
my_f(my_f_vec.begin(), index_map1);
typename graph_traits<Graph1>::vertex_iterator i1, i1_end;
for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1)
my_f[*i1] = get(f, *i1);
@}
Next we enter the loop through every vertex $v$ in $M$, and extend the
isomorphism with $\pair{k}{v}$. We then update the set $S$ (by
removing $v$ from $V_2 - S$) and make the recursive call to
\code{isomorph}. If \code{isomorph} returns successfully, we have
found an isomorphism for the complete graph, so we copy our local
mapping into the mapping from the previous calling function.
@d Invoke isomorph for each vertex in $M$
@{
for (std::size_t j = 0; j < potential_matches.size(); ++j) {
my_f[k] = potential_matches[j];
@<Perform $S' = S - \{ v \}$@>
if (isomorph(boost::next(k_iter), last, edge_iter, edge_iter_end, g1, g2,
index_map1, index_map2,
my_f, invar1, invar2, my_not_in_S)) {
for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1)
put(f, *i1, my_f[*i1]);
return true;
}
}
return false;
@}
We need to create the new set $S' = S - \{ v \}$, which will be the
$S$ for the next invocation to \code{isomorph}. As before, we
represent $V_2 - S'$ instead of $S'$ and use a bitset.
@d Perform $S' = S - \{ v \}$
@{
std::vector<char> my_not_in_S_vec(num_vertices(g2));
iterator_property_map<char*, IndexMap2, char, char&>
my_not_in_S(&my_not_in_S_vec[0], index_map2);
typename graph_traits<Graph2>::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi)
my_not_in_S[*vi] = not_in_S[*vi];;
my_not_in_S[potential_matches[j]] = false;
@}
\section{Appendix}
Here we output the header file \code{isomorphism.hpp}. We add a
copyright statement, include some files, and then pull the top-level
code parts into namespace \code{boost}.
@o isomorphism.hpp -d
@{
// (C) Copyright Jeremy Siek 2001. Permission to copy, use, modify,
// sell and distribute this software is granted provided this
// copyright notice appears in all copies. This software is provided
// "as is" without express or implied warranty, and with no claim as
// to its suitability for any purpose.
// See http://www.boost.org/libs/graph/doc/isomorphism-impl.pdf
// for a description of the implementation of the isomorphism function
// defined in this header file.
#ifndef BOOST_GRAPH_ISOMORPHISM_HPP
#define BOOST_GRAPH_ISOMORPHISM_HPP
#include <algorithm>
#include <boost/graph/detail/set_adaptor.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/graph/detail/permutation.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/property_map.hpp>
#include <boost/pending/integer_range.hpp>
#include <boost/limits.hpp>
#include <boost/static_assert.hpp>
#include <boost/graph/depth_first_search.hpp>
namespace boost {
@<Degree vertex invariant@>
namespace detail {
@<Signature for the recursive isomorph function@>
@<Body of the isomorph function@>
} // namespace detail
@<Record DFS ordering visitor@>
@<Compare multiplicity predicate@>
@<Isomorph edge ordering predicate@>
@<Isomorphism Function Interface@>
@<Isomorphism Function Body@>
namespace detail {
// Should move this, make is public
template <typename Graph, typename InDegreeMap, typename Cat>
void compute_in_degree(const Graph& g, const InDegreeMap& in_degree_map,
Cat)
{
typename graph_traits<Graph>::vertex_iterator vi, vi_end;
typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
for (tie(ei, ei_end) = out_edges(*vi, g); ei != ei_end; ++ei) {
typename graph_traits<Graph>::vertex_descriptor v = target(*ei, g);
put(in_degree_map, v, get(in_degree_map, v) + 1);
}
}
template <typename Graph, typename InDegreeMap>
void compute_in_degree(const Graph& g, const InDegreeMap& in_degree_map,
edge_list_graph_tag)
{
typename graph_traits<Graph>::edge_iterator ei, ei_end;
for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
typename graph_traits<Graph>::vertex_descriptor v = target(*ei, g);
put(in_degree_map, v, get(in_degree_map, v) + 1);
}
}
template <typename Graph, typename InDegreeMap>
void compute_in_degree(const Graph& g, const InDegreeMap& in_degree_map)
{
typename graph_traits<Graph>::traversal_category cat;
compute_in_degree(g, in_degree_map, cat);
}
template <typename Graph1, typename Graph2,
typename IndexMapping, typename IndexMap1, typename IndexMap2,
typename P, typename T, typename R>
bool isomorphism_impl(const Graph1& g1, const Graph2& g2,
IndexMapping f,
IndexMap1 index_map1, IndexMap2 index_map2,
const bgl_named_params<P,T,R>& params)
{
typedef typename graph_traits<Graph1>::vertices_size_type size_type;
// Compute the in-degrees
std::vector<size_type> in_degree_vec1(num_vertices(g1), 0);
typedef iterator_property_map<size_type*, IndexMap1,
size_type, size_type&> InDegreeMap1;
InDegreeMap1 in_degree_map1(&in_degree_vec1[0], index_map1);
detail::compute_in_degree(g1, in_degree_map1);
degree_vertex_invariant<InDegreeMap1, Graph1>
default_invar1(in_degree_map1, g1);
std::vector<size_type> in_degree_vec2(num_vertices(g2), 0);
typedef iterator_property_map<size_type*, IndexMap2,
size_type, size_type&> InDegreeMap2;
InDegreeMap2 in_degree_map2(&in_degree_vec2[0], index_map2);
detail::compute_in_degree(g2, in_degree_map2);
degree_vertex_invariant<InDegreeMap2, Graph2>
default_invar2(in_degree_map2, g2);
return isomorphism(g1, g2, f,
choose_param(get_param(params, vertex_invariant_t()), default_invar1),
choose_param(get_param(params, vertex_invariant_t()), default_invar2),
index_map1, index_map2);
}
} // namespace detail
// Named parameter interface
template <typename Graph1, typename Graph2, class P, class T, class R>
bool isomorphism(const Graph1& g1,
const Graph2& g2,
const bgl_named_params<P,T,R>& params)
{
typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
typename std::vector<vertex2_t>::size_type
n = is_default_param(get_param(params, vertex_isomorphism_t()))
? num_vertices(g1) : 1;
std::vector<vertex2_t> f(n);
vertex2_t x;
return detail::isomorphism_impl
(g1, g2,
choose_param(get_param(params, vertex_isomorphism_t()),
make_iterator_property_map(f.begin(),
choose_const_pmap(get_param(params, vertex_index1),
g1, vertex_index), x)),
choose_const_pmap(get_param(params, vertex_index1),
g1, vertex_index),
choose_const_pmap(get_param(params, vertex_index2),
g2, vertex_index),
params);
}
// All defaults interface
template <typename Graph1, typename Graph2>
bool isomorphism(const Graph1& g1, const Graph2& g2)
{
typedef typename graph_traits<Graph1>::vertices_size_type size_type;
typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
std::vector<vertex2_t> f(num_vertices(g1));
// Compute the in-degrees
std::vector<size_type> in_degree_vec1(num_vertices(g1), 0);
typedef typename property_map<Graph1,vertex_index_t>::const_type IndexMap1;
typedef iterator_property_map<size_type*, IndexMap1,
size_type, size_type&> InDegreeMap1;
InDegreeMap1 in_degree_map1(&in_degree_vec1[0], get(vertex_index, g1));
detail::compute_in_degree(g1, in_degree_map1);
degree_vertex_invariant<InDegreeMap1, Graph1>
invariant1(in_degree_map, g1);
std::vector<size_type> in_degree_vec2(num_vertices(g2), 0);
typedef typename property_map<Graph2,vertex_index_t>::const_type IndexMap2;
typedef iterator_property_map<size_type*, IndexMap2,
size_type, size_type&> InDegreeMap2;
InDegreeMap2 in_degree_map2(&in_degree_vec2[0], get(vertex_index, g2));
detail::compute_in_degree(g2, in_degree_map2);
degree_vertex_invariant<InDegreeMap2, Graph2>
invariant2(in_degree_map, g2);
return isomorphism
(g1, g2, make_iterator_property_map(f.begin(), get(vertex_index, g1), vertex2_t()),
invariant1, invariant2, get(vertex_index, g1), get(vertex_index, g2));
}
// Verify that the given mapping iso_map from the vertices of g1 to the
// vertices of g2 describes an isomorphism.
// Note: this could be made much faster by specializing based on the graph
// concepts modeled, but since we're verifying an O(n^(lg n)) algorithm,
// O(n^4) won't hurt us.
template<typename Graph1, typename Graph2, typename IsoMap>
inline bool verify_isomorphism(const Graph1& g1, const Graph2& g2,
IsoMap iso_map)
{
if (num_vertices(g1) != num_vertices(g2) || num_edges(g1) != num_edges(g2))
return false;
for (typename graph_traits<Graph1>::edge_iterator e1 = edges(g1).first;
e1 != edges(g1).second; ++e1) {
bool found_edge = false;
for (typename graph_traits<Graph2>::edge_iterator e2 = edges(g2).first;
e2 != edges(g2).second && !found_edge; ++e2) {
if (source(*e2, g2) == get(iso_map, source(*e1, g1)) &&
target(*e2, g2) == get(iso_map, target(*e1, g1))) {
found_edge = true;
}
}
if (!found_edge)
return false;
}
return true;
}
} // namespace boost
#endif // BOOST_GRAPH_ISOMORPHISM_HPP
@}
\bibliographystyle{abbrv}
\bibliography{ggcl}
\end{document}
% LocalWords: Isomorphism Siek isomorphism adjacency subgraph subgraphs OM DFS
% LocalWords: ISOMORPH Invariants invariants typename IndexMapping bool const
% LocalWords: VertexInvariant VertexIndexMap iterator typedef VertexG Idx num
% LocalWords: InvarValue struct invar vec iter tmp_matches mult inserter permute ui
% LocalWords: dfs cmp isomorph VertexIter EdgeIter IndexMap desc RPH ATCH pre
% LocalWords: iterators VertexListGraph EdgeListGraph BidirectionalGraph tmp
% LocalWords: ReadWritePropertyMap VertexListGraphConcept EdgeListGraphConcept
% LocalWords: BidirectionalGraphConcept ReadWritePropertyMapConcept indices ei
% LocalWords: IndexMappingValue ReadablePropertyMapConcept namespace InvarMap
% LocalWords: MultMap vip inline bitset typedefs fj hpp ifndef adaptor params
% LocalWords: bgl param pmap endif
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -