isomorphism-impl.w

boost库提供标准的C++ API 配合dev c++使用,功能更加强大

  template <class VertexIndexMap, class G>
  inline edge_ordering_fun<VertexIndexMap,G>
  edge_ordering(VertexIndexMap vip, const G& g)
  {
    return edge_ordering_fun<VertexIndexMap,G>(vip, g);
  }
} // namespace detail
@}


We are now ready to enter the main part of the algorithm, the
backtracking search implemented by the \code{isomorph} function (which
corresponds to the ISOMORPH algorithm).  The set $S$ is not
represented directly; instead we represent $V_2 - S$.  Initially $S =
\emptyset$ so $V_2 - S = V_2$.  We use the permuted indices for the
vertices of graph \code{g1}. We represent $V_2 - S$ with a bitset.  We
use \code{std::vector} instead of \code{boost::dyn\_bitset} for speed
instead of space.

@d Invoke recursive \code{isomorph} function
@{
std::vector<char> not_in_S_vec(num_vertices(g2), true);
iterator_property_map<char*, IndexMap2, char, char&>
  not_in_S(&not_in_S_vec[0], index_map2);

return detail::isomorph(g1_vertices.begin(), g1_vertices.end(), 
      edge_set.begin(), edge_set.end(), g1, g2,
      make_iterator_property_map(perm.begin(), index_map1, perm[0]),
      index_map2, f, invar1, invar2, not_in_S);
@}


\subsection{Implementation of ISOMORPH}

The ISOMORPH algorithm is implemented with the \code{isomorph}
function. The vertices of $G_1$ are searched in the order specified by
the iterator range \code{[k\_iter,last)}. The function returns true if
a isomorphism is found between the vertices of $G_1$ in
\code{[k\_iter,last)} and the vertices of $G_2$ in \code{not\_in\_S}.
The mapping is recorded in the parameter \code{f}.

@d Signature for the recursive isomorph function
@{
template <class VertexIter, class EdgeIter, class Graph1, class Graph2,
  class IndexMap1, class IndexMap2, class IndexMapping, 
  class Invar1, class Invar2, class Set>
bool isomorph(VertexIter k_iter, VertexIter last,
              EdgeIter edge_iter, EdgeIter edge_iter_end,
              const Graph1& g1, const Graph2& g2,
              IndexMap1 index_map1,
              IndexMap2 index_map2,
              IndexMapping f, Invar1 invar1, Invar2 invar2,
              const Set& not_in_S)
@}

\noindent The steps for this function are as follows.

@d Body of the isomorph function
@{
{
  @<Some typedefs and variable declarations@>
  @<Return true if matching is complete@>
  @<Create a copy of $f_{k-1}$ which will become $f_k$@>
  @<Compute $M$, the potential matches for $k$@>
  @<Invoke isomorph for each vertex in $M$@>
}
@}

\noindent Here we create short names for some often-used types
and declare some variables.

@d Some typedefs and variable declarations
@{
typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t;
typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
typedef typename graph_traits<Graph1>::vertices_size_type size_type;

vertex1_t k = *k_iter;
@}

\noindent We have completed creating an isomorphism if \code{k\_iter == last}.

@d Return true if matching is complete
@{
if (k_iter == last) 
  return true;
@}


In the pseudo-code for ISOMORPH, we iterate through each vertex in $v
\in V_2 - S$ and check if $k$ and $v$ can match.  A more efficient
approach is to directly iterate through the potential matches for $k$,
for this often is many fewer vertices than $V_2 - S$. Let $M$ be the
set of potential matches for $k$. $M$ consists of all the vertices $v
\in V_2 - S$ such that if $(k,j)$ or $(j,k) \in E_1[k] - E_1[k-1]$
then $(v,f(j)$ or $(f(j),v) \in E_2$ with $i(v) = i(k)$. Note that
this means if there are no edges in $E_1[k] - E_1[k-1]$ then $M = V_2
- S$. In the case where there are edges in $E_1[k] - E_1[k-1]$ we
break the computation of $M$ into two parts, computing $out$ sets
which are vertices that can match according to an out-edge of $k$, and
computing $in$ sets which are vertices that can match according to an
in-edge of $k$.

The implementation consists of a loop through the edges of $E_1[k] -
E_1[k-1]$. The straightforward implementation would initialize $M
\leftarrow V_2 - S$, and then intersect $M$ with the $out$ or $in$ set
for each edge. However, to reduce the cost of the intersection
operation, we start with $M \leftarrow \emptyset$, and on the first
iteration of the loop we do $M \leftarrow out$ or $M \leftarrow in$
instead of an intersection operation.

@d Compute $M$, the potential matches for $k$
@{
std::vector<vertex2_t> potential_matches;
bool some_edges = false;

for (; edge_iter != edge_iter_end; ++edge_iter) {
  if (get(index_map1, k) != edge_order(*edge_iter, index_map1, g1))
    break;      
  if (k == source(*edge_iter, g1)) { // (k,j)
    @<Compute the $out$ set@>
    if (some_edges == false) {
      @<Perform $M \leftarrow out$@>
    } else {
      @<Perform $M \leftarrow M \intersect out$@>
    }
    some_edges = true;
  } else { // (j,k)
    @<Compute the $in$ set@>
    if (some_edges == false) {
      @<Perform $M \leftarrow in$@>
    } else {
      @<Perform $M \leftarrow M \intersect in$@>
    }
    some_edges = true;
  }
  if (potential_matches.empty())
    break;
} // for edge_iter
if (some_edges == false) {
  @<Perform $M \leftarrow V_2 - S$@>
}
@}

To compute the $out$ set, we iterate through the out-edges $(k,j)$ of
$k$, and for each $j$ we iterate through the in-edges $(v,f(j))$ of
$f(j)$, putting all of the $v$'s in $out$ that have the same vertex
invariant as $k$, and which are in $V_2 - S$. Figure~\ref{fig:out}
depicts the computation of the $out$ set. The implementation is as
follows.

@d Compute the $out$ set
@{
vertex1_t j = target(*edge_iter, g1);
std::vector<vertex2_t> out;
typename graph_traits<Graph2>::in_edge_iterator ei, ei_end;
for (tie(ei, ei_end) = in_edges(get(f, j), g2); ei != ei_end; ++ei) {
  vertex2_t v = source(*ei, g2); // (v,f[j])
  if (invar1[k] == invar2[v] && not_in_S[v])
    out.push_back(v);
}
@}

\noindent Here initialize $M$ with the $out$ set. Since we are
representing sets with sorted vectors, we sort \code{out} before
copying to \code{potential\_matches}.

@d Perform $M \leftarrow out$
@{
indirect_cmp<IndexMap2,std::less<std::size_t> > cmp(index_map2);
std::sort(out.begin(), out.end(), cmp);
std::copy(out.begin(), out.end(), std::back_inserter(potential_matches));
@}

\noindent We use \code{std::set\_intersection} to implement $M
\leftarrow M \intersect out$. Since there is no version of
\code{std::set\_intersection} that works in-place, we create a
temporary for the result and then swap.

@d Perform $M \leftarrow M \intersect out$
@{
indirect_cmp<IndexMap2,std::less<std::size_t> > cmp(index_map2);
std::sort(out.begin(), out.end(), cmp);
std::vector<vertex2_t> tmp_matches;
std::set_intersection(out.begin(), out.end(),
                      potential_matches.begin(), potential_matches.end(),
                      std::back_inserter(tmp_matches), cmp);
std::swap(potential_matches, tmp_matches);
@}

% Shoot, there is some problem with f(j). Could have to do with the
% change from the edge set to just using out_edges and in_edges.
% Yes, have to visit edges in correct order to we don't hit
% part of f that is not yet defined.

\vizfig{out}{Computing the $out$ set.}

@c out.dot
@{
digraph G {
  node[shape=circle]
  size="4,2"
  ratio="fill"

  subgraph cluster0 { label="G_1"
    k -> j_1 
    k -> j_2 
    k -> j_3
  }

  subgraph cluster1 { label="G_2"

    subgraph cluster2 { label="out" v_1 v_2 v_3 v_4 v_5 v_6 }

    v_1 -> fj_1
    v_2 -> fj_1
    v_3 -> fj_1

    v_4 -> fj_2

    v_5 -> fj_3
    v_6 -> fj_3

    fj_1[label="f(j_1)"]
    fj_2[label="f(j_2)"]
    fj_3[label="f(j_3)"]
  }

  j_1 -> fj_1[style=dotted]
  j_2 -> fj_2[style=dotted]
  j_3 -> fj_3[style=dotted]
}
@}

The $in$ set is is constructed by iterating through the in-edges
$(j,k)$ of $k$, and for each $j$ we iterate through the out-edges
$(f(j),v)$ of $f(j)$. We put all of the $v$'s in $in$ that have the
same vertex invariant as $k$, and which are in $V_2 -
S$. Figure~\ref{fig:in} depicts the computation of the $in$ set.  The
following code computes the $in$ set.

@d Compute the $in$ set
@{
vertex1_t j = source(*edge_iter, g1);
std::vector<vertex2_t> in;
typename graph_traits<Graph2>::out_edge_iterator ei, ei_end;
for (tie(ei, ei_end) = out_edges(get(f, j), g2); ei != ei_end; ++ei) {
  vertex2_t v = target(*ei, g2); // (f[j],v)
  if (invar1[k] == invar2[v] && not_in_S[v])
    in.push_back(v);
}
@}

\noindent Here initialize $M$ with the $in$ set. Since we are
representing sets with sorted vectors, we sort \code{in} before
copying to \code{potential\_matches}.

@d Perform $M \leftarrow in$
@{
indirect_cmp<IndexMap2,std::less<std::size_t> > cmp(index_map2);
std::sort(in.begin(), in.end(), cmp);
std::copy(in.begin(), in.end(), std::back_inserter(potential_matches));
@}

\noindent Again we use \code{std::set\_intersection} on
sorted vectors to implement $M \leftarrow M \intersect in$.

@d Perform $M \leftarrow M \intersect in$
@{
indirect_cmp<IndexMap2, std::less<std::size_t> > cmp(index_map2);
std::sort(in.begin(), in.end(), cmp);
std::vector<vertex2_t> tmp_matches;
std::set_intersection(in.begin(), in.end(),
                      potential_matches.begin(), potential_matches.end(),
                      std::back_inserter(tmp_matches), cmp);
std::swap(potential_matches, tmp_matches);
@}

\vizfig{in}{Computing the $in$ set.}

@c in.dot
@{
digraph G {
  node[shape=circle]
  size="3,2"
  ratio="fill"
  subgraph cluster0 { label="G1"
    j_1 -> k
    j_2 -> k
  }

  subgraph cluster1 { label="G2"

    subgraph cluster2 { label="in" v_1 v_2 v_3 }

    v_1 -> fj_1
    v_2 -> fj_1

    v_3 -> fj_2

    fj_1[label="f(j_1)"]
    fj_2[label="f(j_2)"]