isomorphism-impl.w

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

  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)"]
  }

  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