isomorphism-impl-v2.w

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

             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.

@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 type
arguments to the function fulfill there 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
that represents 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));
@}

The following is the outline of the isomorphism algorithm class.  The
class is templated on all of the same parameters of 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 IndexMap1, typename IndexMap2>
class isomorphism_algo
{
    @<Typedefs for commonly used types@>
    @<Data members for the parameters@>
    @<Ordered edge class@>
    @<Internal data structures@>
    friend struct compare_multiplicity;
    @<Invariant multiplicity comparison functor@>
    @<DFS visitor to record vertex and edge order@>
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 in the
following sections, and mention the other parts of the class when
needed (and a few are left 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 by the DFS order of vertices incident on the edges. More
details about this to come. The last step of this function is to
invoke the recursive \code{match} function which performs 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@>

    return this->match(ordered_edges.begin());
}
@}

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 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));
    std::sort(invar1_array.begin(), invar1_array.end());

    std::vector<invar2_value> invar2_array;
    BGL_FORALL_VERTICES_T(v, G2, Graph2)
        invar2_array.push_back(invariant2(v));
    std::sort(invar2_array.begin(), invar2_array.end());

    if (!std::equal(invar1_array.begin(), invar1_array.end(), invar2_array.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. 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)];

    std::sort(V_mult.begin(), V_mult.end(), compare_multiplicity(*this, &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(isomorphism_algo& algo, size_type* multiplicity)
        : algo(algo), multiplicity(multiplicity) { }
    bool operator()(const vertex1_t& x, const vertex1_t& y) const {
        return multiplicity[algo.invariant1(x)] < multiplicity[algo.invariant1(y)];
    }
    isomorphism_algo& algo;
    size_type* multiplicity;
};
@}

\subsection{Backtracking Search and Matching}






\subsection{Ordering by DFS Discover Time}

To implement the ``visit adjacent vertices first'' heuristic, we order
the vertices according to DFS discover time. This will give us the
order that the subgraph $G_1[k]$ will be expanded. As described in
\S\ref{sec:backtracking}, when trying to match $k$ with some vertex
$v$ in $V_2 - S$, we need to examine the edges in $E_1[k] -
E_1[k-1]$. It would be nice if we had the edges of $G_1$ arranged so
that when we are interested in vertex $k$, the edges in $E_1[k] -
E_1[k-1]$ are easy to find. This can be achieved by creating an array
of edges sorted by the DFS number of the larger of the source and
target vertex. The following array of ordered edges corresponds
to the graph in Figure~\ref{fig:edge-order}.

\begin{tabular}{cccccccccc}
      &0&1&2&3&4&5&6&7&8\\ \hline
source&0&1&1&3&3&4&4&5&6\\
target&1&2&3&1&2&3&5&6&4
\end{tabular}

The backtracking algorithm will scan through the edge array from left
to right to extend isomorphic subgraphs, and move back to the right
when a match fails. We will want to 










For example, suppose we have already matched the vertices
\{0,1,2\}, and 



\vizfig{edge-order}{Vertices with DFS numbering. The DFS trees are the solid edges.}

@c edge-order.dot
@{
digraph G {
size="3,2"
ratio=fill
node[shape=circle]
0 -> 1[style=bold]
1 -> 2[style=bold]
1 -> 3[style=bold]
3 -> 1[style=dashed]
3 -> 2[style=dashed]
4 -> 3[style=dashed]
4 -> 5[style=bold]
5 -> 6[style=bold]
6 -> 4[style=dashed]
}
@}




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, storing the results in in
the \code{dfs\_vertices} and \code{ordered\_edges} arrays. We then
create the \code{dfs\_number} array which provides a mapping from
vertex to DFS number, and renumber the edges with the DFS numbers.

@d Order vertices and edges by DFS
@{
std::vector<default_color_type> color_vec(num_vertices(G1));
safe_iterator_property_map<std::vector<default_color_type>::iterator, IndexMap1>
     color_map(color_vec.begin(), color_vec.size(), index_map1);
record_dfs_order dfs_visitor(dfs_vertices, ordered_edges);
typedef color_traits<default_color_type> Color;
for (vertex_iter u = V_mult.begin(); u != V_mult.end(); ++u) {
    if (color_map[*u] == Color::white()) {
	dfs_visitor.start_vertex(*u, G1);
	depth_first_visit(G1, *u, dfs_visitor, color_map);
    }
}
// Create the dfs_number array and dfs_number_map
dfs_number_vec.resize(num_vertices(G1));
dfs_number = make_safe_iterator_property_map(dfs_number_vec.begin(),
	                  dfs_number_vec.size(), index_map1);
size_type n = 0;
for (vertex_iter v = dfs_vertices.begin(); v != dfs_vertices.end(); ++v)
    dfs_number[*v] = n++;

// Renumber ordered_edges array according to DFS number
for (edge_iter e = ordered_edges.begin(); e != ordered_edges.end(); ++e) {
    if (e->source >= 0)
      e->source = dfs_number_vec[e->source];
    e->target = dfs_number_vec[e->target];
}
@}

\noindent The definition of the \code{record\_dfs\_order} visitor
class is as follows. EXPLAIN ficticious edges

@d DFS visitor to record vertex and edge order
@{
struct record_dfs_order : default_dfs_visitor
{
    record_dfs_order(std::vector<vertex1_t>& v, std::vector<ordered_edge>& e) 
	: vertices(v), edges(e) { }

    void start_vertex(vertex1_t v, const Graph1&) const {
        edges.push_back(ordered_edge(-1, v));
    }
    void discover_vertex(vertex1_t v, const Graph1&) const {
        vertices.push_back(v);
    }
    void examine_edge(edge1_t e, const Graph1& G1) const {
        edges.push_back(ordered_edge(source(e, G1), target(e, G1)));
    }
    std::vector<vertex1_t>& vertices;
    std::vector<ordered_edge>& edges;
};
@}


Reorder the edges so that all edges belonging to $G_1[k]$
appear before any edges not in $G_1[k]$, for $k=1,...,n$.

The order field needs a better name. How about k?

@d Sort edges according to vertex DFS order
@{
std::stable_sort(ordered_edges.begin(), ordered_edges.end());
// Fill in i->k_num field
if (!ordered_edges.empty()) {
  ordered_edges[0].k_num = 0;
  for (edge_iter i = next(ordered_edges.begin()); i != ordered_edges.end(); ++i)
      i->k_num = std::max(prior(i)->source, prior(i)->target);
}
@}






@d Typedefs for commonly used types
@{
typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t;
typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
typedef typename graph_traits<Graph1>::edge_descriptor edge1_t;
typedef typename graph_traits<Graph1>::vertices_size_type size_type;
typedef typename Invariant1::result_type invar1_value;
typedef typename Invariant2::result_type invar2_value;
@}

@d Data members for the parameters
@{
const Graph1& G1;
const Graph2& G2;
IsoMapping f;
Invariant1 invariant1;
Invariant2 invariant2;
std::size_t max_invariant;
IndexMap1 index_map1;
IndexMap2 index_map2;
@}

@d Internal data structures