isomorphism-impl.w

C++的一个好库。。。现在很流行

// Graph requirements
function_requires< VertexListGraphConcept<Graph1> >();
function_requires< EdgeListGraphConcept<Graph1> >();
function_requires< VertexListGraphConcept<Graph2> >();
function_requires< BidirectionalGraphConcept<Graph2> >();

// Property map requirements
function_requires< ReadWritePropertyMapConcept<IndexMapping, vertex1_t> >();
typedef typename property_traits<IndexMapping>::value_type IndexMappingValue;
BOOST_STATIC_ASSERT((is_same<IndexMappingValue, vertex2_t>::value));

function_requires< ReadablePropertyMapConcept<IndexMap1, vertex1_t> >();
typedef typename property_traits<IndexMap1>::value_type IndexMap1Value;
BOOST_STATIC_ASSERT((is_convertible<IndexMap1Value, size_type>::value));

function_requires< ReadablePropertyMapConcept<IndexMap2, vertex2_t> >();
typedef typename property_traits<IndexMap2>::value_type IndexMap2Value;
BOOST_STATIC_ASSERT((is_convertible<IndexMap2Value, size_type>::value));
@}


\noindent If there are no vertices in either graph, then they are trivially
isomorphic.

@d Quick return with false if $|V_1| \neq |V_2|$
@{
if (num_vertices(g1) != num_vertices(g2))
  return false;
@}


\subsection{Ordering by Vertex Invariant Multiplicity}

The user can supply the vertex invariant functions as a
\stlconcept{AdaptableUnaryFunction} (with the addition of the
\code{max} function) in the \code{invariant1} and \code{invariant2}
parameters. We also define a default which uses the out-degree and
in-degree of a vertex. The following is the definition of the function
object for the default vertex invariant. User-defined vertex invariant
function objects should follow the same pattern.

@d Degree vertex invariant
@{
template <typename InDegreeMap, typename Graph>
class degree_vertex_invariant
{
public:
  typedef typename graph_traits<Graph>::vertex_descriptor argument_type;
  typedef typename graph_traits<Graph>::degree_size_type result_type;

  degree_vertex_invariant(const InDegreeMap& in_degree_map, const Graph& g)
    : m_in_degree_map(in_degree_map), m_g(g) { }

  result_type operator()(argument_type v) const {
    return (num_vertices(m_g) + 1) * out_degree(v, m_g)
      + get(m_in_degree_map, v);
  }
  // The largest possible vertex invariant number
  result_type max() const { 
    return num_vertices(m_g) * num_vertices(m_g) + num_vertices(m_g);
  }
private:
  InDegreeMap m_in_degree_map;
  const Graph& m_g;
};
@}

Since the invariant function may be expensive to compute, we
pre-compute the invariant numbers for every vertex in the two
graphs. The variables \code{invar1} and \code{invar2} are property
maps for accessing the stored invariants, which are described next.

@d Compute vertex invariants
@{
@<Setup storage for vertex invariants@>
for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1)
  invar1[*i1] = invariant1(*i1);
for (tie(i2, i2_end) = vertices(g2); i2 != i2_end; ++i2)
  invar2[*i2] = invariant2(*i2);
@}

\noindent We store the invariants in two vectors, indexed by the vertex indices
of the two graphs. We then create property maps for accessing these
two vectors in a more convenient fashion (they go directly from vertex
to invariant, instead of vertex to index to invariant).

@d Setup storage for vertex invariants
@{
typedef typename VertexInvariant1::result_type InvarValue1;
typedef typename VertexInvariant2::result_type InvarValue2;
typedef std::vector<InvarValue1> invar_vec1_t;
typedef std::vector<InvarValue2> invar_vec2_t;
invar_vec1_t invar1_vec(num_vertices(g1));
invar_vec2_t invar2_vec(num_vertices(g2));
typedef typename invar_vec1_t::iterator vec1_iter;
typedef typename invar_vec2_t::iterator vec2_iter;
iterator_property_map<vec1_iter, IndexMap1, InvarValue1, InvarValue1&>
  invar1(invar1_vec.begin(), index_map1);
iterator_property_map<vec2_iter, IndexMap2, InvarValue2, InvarValue2&>
  invar2(invar2_vec.begin(), index_map2);
@}

As discussed in \S\ref{sec:vertex-invariants}, we can quickly rule out
the possibility of any isomorphism between two graphs by checking to
see if the vertex invariants can match up. We sort both vectors of vertex
invariants, and then check to see if they are equal.

@d Quick return if the graph's invariants do not match
@{
{ // check if the graph's invariants do not match
  invar_vec1_t invar1_tmp(invar1_vec);
  invar_vec2_t invar2_tmp(invar2_vec);
  std::sort(invar1_tmp.begin(), invar1_tmp.end());
  std::sort(invar2_tmp.begin(), invar2_tmp.end());
  if (! std::equal(invar1_tmp.begin(), invar1_tmp.end(), 
                   invar2_tmp.begin()))
    return false;
}
@}

Next we compute the invariant multiplicity, the number of vertices
with the same invariant number. The \code{invar\_mult} vector is
indexed by invariant number. We loop through all the vertices in the
graph to record the multiplicity.

@d Compute invariant multiplicity
@{
std::vector<std::size_t> invar_mult(invariant1.max(), 0);
for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1)      
  ++invar_mult[invar1[*i1]];
@}

\noindent We then order the vertices by their invariant multiplicity.
This will allow us to search the more constrained vertices first.
Since we will need to know the permutation from the original order to
the new order, we do not sort the vertices directly. Instead we sort
the vertex indices, creating the \code{perm} array.  Once sorted, this
array provides a mapping from the new index to the old index.
We then use the \code{permute} function to sort the vertices of
the graph, which we store in the \code{g1\_vertices} vector.

@d Sort vertices by invariant multiplicity
@{
std::vector<size_type> perm;
integer_range<size_type> range(0, num_vertices(g1));
std::copy(range.begin(), range.end(), std::back_inserter(perm));
std::sort(perm.begin(), perm.end(),
          detail::compare_invariant_multiplicity(invar1_vec.begin(),
                                                 invar_mult.begin()));

std::vector<vertex1_t> g1_vertices;
for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1)
  g1_vertices.push_back(*i1);
permute(g1_vertices.begin(), g1_vertices.end(), perm.begin());
@}

\noindent The definition of the \code{compare\_multiplicity} predicate
is shown below. This predicate provides the glue that binds
\code{std::sort} to our current purpose.

@d Compare multiplicity predicate
@{
namespace detail {
  template <typename InvarMap, typename MultMap>
  struct compare_invariant_multiplicity_predicate
  {
    compare_invariant_multiplicity_predicate(InvarMap i, MultMap m)
      : m_invar(i), m_mult(m) { }

    template <typename Vertex>
    bool operator()(const Vertex& x, const Vertex& y) const
      { return m_mult[m_invar[x]] < m_mult[m_invar[y]]; }

    InvarMap m_invar;
    MultMap m_mult;
  };
  template <typename InvarMap, typename MultMap>
  compare_invariant_multiplicity_predicate<InvarMap, MultMap>
  compare_invariant_multiplicity(InvarMap i, MultMap m) {
    return compare_invariant_multiplicity_predicate<InvarMap, MultMap>(i,m);
  }
} // namespace detail
@}


\subsection{Ordering by DFS Discover Time}

To implement the ``visit adjacent vertices first'' heuristic, we order
the vertices according to DFS discover time.  We replace the ordering
in \code{perm} with the new DFS ordering. Again, we use \code{permute}
to sort the vertices of graph \code{g1}.

@d Order the vertices by DFS discover time
@{
{
  perm.clear();
  @<Compute DFS discover times@>
  g1_vertices.clear();
  for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1)
    g1_vertices.push_back(*i1);
  permute(g1_vertices.begin(), g1_vertices.end(), perm.begin());
}
@}

We implement the outer-loop of the DFS here, instead of calling the
\code{depth\_first\_search} function, because we want the roots of the
DFS tree's to be ordered by invariant multiplicity. We call
\code{depth\_\-first\_\-visit} to implement the recursive portion of
the DFS. The \code{record\_dfs\_order} adapts the DFS to record
the order in which DFS discovers the vertices.

@d Compute DFS discover times
@{
std::vector<default_color_type> color_vec(num_vertices(g1));
for (typename std::vector<vertex1_t>::iterator ui = g1_vertices.begin();
     ui != g1_vertices.end(); ++ui) {
  if (color_vec[get(index_map1, *ui)] 
      == color_traits<default_color_type>::white()) {
    depth_first_visit
      (g1, *ui, detail::record_dfs_order<Graph1, IndexMap1>(perm, 
                                                       index_map1), 
       make_iterator_property_map(&color_vec[0], index_map1, 
                                  color_vec[0]));
  }
}
@}

\noindent The definition of the \code{record\_dfs\_order} visitor
class is as follows. The index of each vertex is recorded in the
\code{dfs\_order} vector (which is the \code{perm} vector) in the
\code{discover\_vertex} event point.

@d Record DFS ordering visitor
@{
namespace detail {
  template <typename Graph1, typename IndexMap1>
  struct record_dfs_order : public default_dfs_visitor {
    typedef typename graph_traits<Graph1>::vertices_size_type size_type;
    typedef typename graph_traits<Graph1>::vertex_descriptor vertex;

    record_dfs_order(std::vector<size_type>& dfs_order, IndexMap1 index) 
      : dfs_order(dfs_order), index(index) { }

    void discover_vertex(vertex v, const Graph1& g) const {
      dfs_order.push_back(get(index, v));
    }
    std::vector<size_type>& dfs_order; 
    IndexMap1 index;
  };
} // namespace detail
@}


In the MATCH operation, we need to examine all the edges in the set
$E_1[k] - E_1[k-1]$. That is, we need to loop through all the edges of
the form $(k,j)$ or $(j,k)$ where $j \leq k$. To do this efficiently,
we create an array of all the edges in $G_1$ that has been sorted so
that $E_1[k] - E_1[k-1]$ forms a contiguous range.  To each edge
$e=(u,v)$ we assign the number $\max(u,v)$, and then sort the edges by
this number. All the edges $(u,v) \in E_1[k] - E_1[k-1]$ can then be
identified because $\max(u,v) = k$. The following code creates an
array of edges and then sorts them. The \code{edge\_\-ordering\_\-fun}
function object is described next.

@d Order the edges by DFS discover time
@{
typedef typename graph_traits<Graph1>::edge_descriptor edge1_t;
std::vector<edge1_t> edge_set;
std::copy(edges(g1).first, edges(g1).second, std::back_inserter(edge_set));

std::sort(edge_set.begin(), edge_set.end(), 
          detail::edge_ordering
          (make_iterator_property_map(perm.begin(), index_map1, perm[0]), g1));
@}

\noindent The \code{edge\_order} function computes the ordering number
for an edge, which for edge $e=(u,v)$ is $\max(u,v)$. The
\code{edge\_\-ordering\_\-fun} function object simply returns
comparison of two edge's ordering numbers.

@d Isomorph edge ordering predicate
@{
namespace detail {

  template <typename VertexIndexMap, typename Graph>
  std::size_t edge_order(const typename graph_traits<Graph>::edge_descriptor e,
                         VertexIndexMap index_map, const Graph& g) {
    return std::max(get(index_map, source(e, g)), get(index_map, target(e, g)));    
  }

  template <typename VertexIndexMap, typename Graph>
  class edge_ordering_fun {
  public:
    edge_ordering_fun(VertexIndexMap vip, const Graph& g)
      : m_index_map(vip), m_g(g) { }
    template <typename Edge>
    bool operator()(const Edge& e1, const Edge& e2) const {
      return edge_order(e1, m_index_map, m_g) < edge_order(e2, m_index_map, m_g);
    }
    VertexIndexMap m_index_map;
    const Graph& m_g;
  };