isomorphism-impl-v3.w

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

    }
}
@}


\paragraph{Case 2: $i \in G_1[k]$ and $j \not\in G_1[k]$.}
Before we extend the subgraph by incrementing $k$, we need to finish
verifying that $G_1[k]$ and $G_2[S]$ are isomorphic. We decrement the
edge counter for every edge incident to $f(k)$ in $G_2[S]$, which
should bring the counter back down to zero. If not we return false.

@d Verify $G_1[k] \isomorphic G_2[S]$ and then find match for $j$
@{
vertex1_t k = dfs_vertices[dfs_num_k];
@<Count out-edges of $f(k)$ in $G_2[S]$@>
@<Count in-edges of $f(k)$ in $G_2[S]$@>
if (num_edges_on_k != 0)
    return false;
@<Find a match for $j$ and continue@>
@}

\noindent We decrement the edge counter for every vertex in
$Adj[f(k)]$ that is also in $S$. We call \code{count\_if} to do the
counting, using \code{boost::bind} to create the predicate functor.

@d Count out-edges of $f(k)$ in $G_2[S]$
@{
num_edges_on_k -= 
    count_if(adjacent_vertices(f[k], G2), make_indirect_pmap(in_S));
@}

\noindent Next we iterate through all the vertices in $S$ and for each
we decrement the counter for each edge whose target is $k$.

% We could specialize this for the case when G_2 is bidirectional.

@d Count in-edges of $f(k)$ in $G_2[S]$
@{
for (int jj = 0; jj < dfs_num_k; ++jj) {
    vertex1_t j = dfs_vertices[jj];
    num_edges_on_k -= count(adjacent_vertices(f[j], G2), f[k]);
}
@}

Now that we have finished verifying that $G_1[k] \isomorphic G_2[S]$,
we can now consider extending the isomorphism. We need to find a match
for $j$ in $V_2 - S$. Since $j$ is adjacent to $i$, we can further
narrow down the search by only considering vertices adjacent to
$f(i)$. Also, the vertex must have the same vertex invariant. Once we
have a matching vertex $v$ we extend the matching subgraphs by
incrementing $k$ and adding $v$ to $S$, we set $f(j) = v$, and we set
the edge counter to $1$ (since $(i,j)$ is the first edge incident on
our new $k$). We continue to the next edge by calling \code{match}. If
that fails we undo the assignment $f(j) = v$.

@d Find a match for $j$ and continue
@{
BGL_FORALL_ADJ_T(f[i], v, G2, Graph2)
    if (invariant2(v) == invariant1(j) && in_S[v] == false) {
        f[j] = v;
        in_S[v] = true;
        num_edges_on_k = 1;
	int next_k = std::max(dfs_num_k, std::max(dfs_num[i], dfs_num[j]));
        if (match(next(iter), next_k))
            return true;
        in_S[v] = false;
    }
@}

\paragraph{Case 3: both $i$ and $j$ are in $G_1[k]$.} 
Our goal is to check whether $(f(i),f(j)) \in E_2[S]$.  If $f(j)$ is
in $Adj[f(i)]$ then we have a match for the edge $(i,j)$, and can
increment the counter for the number of edges incident on $k$ in
$E_1[k]$. We continue by calling \code{match} on the next edge.

@d Check to see if $(f(i),f(j)) \in E_2[S]$ and continue
@{
edge2_t e2;
bool fi_fj_exists = false;
typename graph_traits<Graph2>::out_edge_iterator io, io_end;
for (tie(io, io_end) = out_edges(f[i], G2); io != io_end; ++io)
  if (target(*io, G2) == f[j]) {
    fi_fj_exists = true;
    e2 = *io;
  }

if (fi_fj_exists && edge_compare(e2, *iter)) {
    ++num_edges_on_k;
    if (match(next(iter), dfs_num_k))
         return true;
}
@}

\section{Public Interface}

The following is the public interface for the \code{isomorphism}
function. The input to the function is the two graphs $G_1$ and $G_2$,
mappings from the vertices in the graphs to integers (in the range
$[0,|V|)$), and a vertex invariant function object. The output of the
function is an isomorphism $f$ if there is one. The \code{isomorphism}
function returns true if the graphs are isomorphic and false
otherwise. The invariant parameters are function objects that compute
the vertex invariants for vertices of the two graphs.  The
\code{max\_invariant} parameter is to specify one past the largest
integer that a vertex invariant number could be (the invariants
numbers are assumed to span from zero to \code{max\_invariant-1}).
The requirements on the template parameters are described below in the
``Concept checking'' code part.


@d Isomorphism function interface
@{
template <typename Graph1, typename Graph2, typename IsoMapping, 
          typename Invariant1, typename Invariant2, typename EdgeCompare,
          typename IndexMap1, typename IndexMap2>
bool isomorphism(const Graph1& G1, const Graph2& G2, IsoMapping f, 
                 Invariant1 invariant1, Invariant2 invariant2, 
                 std::size_t max_invariant, EdgeCompare edge_compare,
                 IndexMap1 index_map1, IndexMap2 index_map2)
@}


The function body consists of the concept checks followed by a quick
check for empty graphs or graphs of different size and then constructs
an algorithm object. We then call the \code{test\_isomorphism} member
function, which runs the algorithm.  The reason that we implement the
algorithm using a class is that there are a fair number of internal
data structures required, and it is easier to make these data members
of a class and make each section of the algorithm a member
function. This relieves us from the burden of passing lots of
arguments to each function, while at the same time avoiding the evils
of global variables (non-reentrant, etc.).


@d Isomorphism function body
@{
{
    @<Concept checking@>
    @<Quick return based on size@>
    detail::isomorphism_algo<Graph1, Graph2, IsoMapping, Invariant1,
        Invariant2, EdgeCompare, IndexMap1, IndexMap2> 
        algo(G1, G2, f, invariant1, invariant2, max_invariant, 
             edge_compare,
             index_map1, index_map2);
    return algo.test_isomorphism();
}
@}


\noindent If there are no vertices in either graph, then they are
trivially isomorphic. If the graphs have different numbers of vertices
then they are not isomorphic. We could also check the number of edges
here, but that would introduce the \bglconcept{EdgeListGraph}
requirement, which we otherwise do not need.

@d Quick return based on size
@{
if (num_vertices(G1) != num_vertices(G2))
    return false;
if (num_vertices(G1) == 0 && num_vertices(G2) == 0)
    return true;
@}

We use the Boost Concept Checking Library to make sure that the
template arguments fulfill certain requirements. The graph types must
model the \bglconcept{VertexListGraph} and \bglconcept{AdjacencyGraph}
concepts. The vertex invariants must model the
\stlconcept{AdaptableUnaryFunction} concept, with a vertex as their
argument and an integer return type.  The \code{IsoMapping} type
representing the isomorphism $f$ must be a
\pmconcept{ReadWritePropertyMap} that maps from vertices in $G_1$ to
vertices in $G_2$. The two other index maps are
\pmconcept{ReadablePropertyMap}s from vertices in $G_1$ and $G_2$ to
unsigned integers.


@d Concept checking
@{
// Graph requirements
function_requires< VertexListGraphConcept<Graph1> >();
function_requires< EdgeListGraphConcept<Graph1> >();
function_requires< VertexListGraphConcept<Graph2> >();
function_requires< BidirectionalGraphConcept<Graph2> >();

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;

// Vertex invariant requirement
function_requires< AdaptableUnaryFunctionConcept<Invariant1,
  size_type, vertex1_t> >();
function_requires< AdaptableUnaryFunctionConcept<Invariant2,
  size_type, vertex2_t> >();

// Property map requirements
function_requires< ReadWritePropertyMapConcept<IsoMapping, vertex1_t> >();
typedef typename property_traits<IsoMapping>::value_type IsoMappingValue;
BOOST_STATIC_ASSERT((is_same<IsoMappingValue, 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));
@}


\section{Data Structure Setup}

The following is the outline of the isomorphism algorithm class.  The
class is templated on all of the same parameters as the
\code{isomorphism} function, and all of the parameter values are
stored in the class as data members, in addition to the internal data
structures.

@d Isomorphism algorithm class
@{
template <typename Graph1, typename Graph2, typename IsoMapping,
    typename Invariant1, typename Invariant2, typename EdgeCompare,
    typename IndexMap1, typename IndexMap2>
class isomorphism_algo
{
    @<Typedefs for commonly used types@>
    @<Data members for the parameters@>
    @<Internal data structures@>
    friend struct compare_multiplicity;
    @<Invariant multiplicity comparison functor@>
    @<DFS visitor to record vertex and edge order@>
    @<Edge comparison predicate@>
public:
    @<Isomorphism algorithm constructor@>
    @<Test isomorphism member function@>
private:
    @<Match function@>
};
@}

The interesting parts of this class are the \code{test\_isomorphism}
function and the \code{match} function. We focus on those in the
following sections, and leave the other parts of the class to the
Appendix.

The \code{test\_isomorphism} function does all of the setup required
of the algorithm. This consists of sorting the vertices according to
invariant multiplicity, and then by DFS order.  The edges are then
sorted as previously described. The last step of this function is to
begin the backtracking search.

@d Test isomorphism member function
@{
bool test_isomorphism()
{
    @<Quick return if the vertex invariants do not match up@>
    @<Sort vertices according to invariant multiplicity@>
    @<Order vertices and edges by DFS@>
    @<Sort edges according to vertex DFS order@>

    int dfs_num_k = -1;
    return this->match(ordered_edges.begin(), dfs_num_k);
}
@}

As a first check to rule out graphs that have no possibility of
matching, one can create a list of computed vertex invariant numbers
for the vertices in each graph, sort the two lists, and then compare
them.  If the two lists are different then the two graphs are not
isomorphic.  If the two lists are the same then the two graphs may be
isomorphic.

@d Quick return if the vertex invariants do not match up
@{
{
    std::vector<invar1_value> invar1_array;
    BGL_FORALL_VERTICES_T(v, G1, Graph1)
        invar1_array.push_back(invariant1(v));
    sort(invar1_array);

    std::vector<invar2_value> invar2_array;
    BGL_FORALL_VERTICES_T(v, G2, Graph2)
        invar2_array.push_back(invariant2(v));
    sort(invar2_array);
    if (! equal(invar1_array, invar2_array))
        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. We then order the vertices by their
invariant multiplicity.  This will allow us to search the more
constrained vertices first.

@d Sort vertices according to invariant multiplicity
@{
std::vector<vertex1_t> V_mult;
BGL_FORALL_VERTICES_T(v, G1, Graph1)
    V_mult.push_back(v);
{
    std::vector<size_type> multiplicity(max_invariant, 0);
    BGL_FORALL_VERTICES_T(v, G1, Graph1)
        ++multiplicity[invariant1(v)];
    sort(V_mult, compare_multiplicity(invariant1, &multiplicity[0]));
}
@}

\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 Invariant multiplicity comparison functor
@{
struct compare_multiplicity
{
    compare_multiplicity(Invariant1 invariant1, size_type* multiplicity)
        : invariant1(invariant1), multiplicity(multiplicity) { }
    bool operator()(const vertex1_t& x, const vertex1_t& y) const {
        return multiplicity[invariant1(x)] < multiplicity[invariant1(y)];
    }
    Invariant1 invariant1;
    size_type* multiplicity;
};
@}

\subsection{Ordering by DFS Discover Time}

Next we order the vertices and edges by DFS discover time.  We would
normally call the BGL \code{depth\_first\_search} function to do this,