123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987 |
- \documentclass[11pt,awpaper]{book}
- \usepackage{math}
- \usepackage{jweb}
- \usepackage[nolineno]{lgrind}
- \usepackage{awpaper}
- \usepackage{graphicx}
- \setlength{\evensidemargin}{-0.25in}% was -0.17in
- \setlength{\oddsidemargin}{0in}%was -0.25in
- \setlength{\textwidth}{5.625in}%was 5.75in
- \setlength{\textheight}{7.75in}
- \setlength{\topmargin}{-0.125in}%was -0.25
- \addtolength{\topmargin}{-\headheight}
- \addtolength{\topmargin}{-\headsep}
- \newif\ifpdf
- \ifx\pdfoutput\undefined
- \pdffalse
- \else
- \pdfoutput=1
- \pdftrue
- \fi
- \ifpdf
- \usepackage[
- pdftex,
- colorlinks=true, %change to true for the electronic version
- linkcolor=blue,filecolor=blue,pagecolor=blue,urlcolor=blue
- ]{hyperref}
- \fi
- \ifpdf
- \newcommand{\stlconcept}[1]{\href{https://boost.org/sgi/stl/#1.html}{{\small \textsf{#1}}}}
- \newcommand{\bglconcept}[1]{\href{http://www.boost.org/libs/graph/doc/#1.html}{{\small \textsf{#1}}}}
- \newcommand{\pmconcept}[1]{\href{http://www.boost.org/libs/property_map/#1.html}{{\small \textsf{#1}}}}
- \newcommand{\myhyperref}[2]{\hyperref[#1]{#2}}
- \newcommand{\vizfig}[2]{\begin{figure}[htbp]\centerline{\includegraphics*{#1.pdf}}\caption{#2}\label{fig:#1}\end{figure}}
- \else
- \newcommand{\myhyperref}[2]{#2}
- \newcommand{\bglconcept}[1]{{\small \textsf{#1}}}
- \newcommand{\pmconcept}[1]{{\small \textsf{#1}}}
- \newcommand{\stlconcept}[1]{{\small \textsf{#1}}}
- \newcommand{\vizfig}[2]{\begin{figure}[htbp]\centerline{\includegraphics*{#1.eps}}\caption{#2}\label{fig:#1}\end{figure}}
- \fi
- \newcommand{\code}[1]{{\small{\em \textbf{#1}}}}
- \newcommand{\isomorphic}{\cong}
- \begin{document}
- \title{An Implementation of Graph Isomorphism Testing}
- \author{Jeremy G. Siek}
- \maketitle
- % Ideas: use BFS instead of DFS, don't have to sort edges?
- % No, you would still have to sort the edges.
- %
- %Figure~\ref{fig:iso-eg2}.
- % 0 0 0 1 1 2 5 6 6 7
- % 1 2 3 4 2 4 6 3 7 5
- %\vizfig{iso-eg2}{Vertices numbered by BFS discover time. The BFS tree
- %edges are the solid lines. Nodes $0$ and $5$ are BFS tree root nodes.}
- %
- % You could do a modified Dijkstra, where the priority in the queue
- % would be the BFS discover time of the target vertex.
- % Use w(u,v) = |Adj[u] \intersect Adj[v]| as an edge invariant.
- % Has anyone used edge invariants before?
- \section{Introduction}
- This paper documents the implementation of the \code{isomorphism()}
- function of the Boost Graph Library. The implementation was by Jeremy
- Siek with algorithmic improvements and test code from Douglas Gregor
- and Brian Osman. The \code{isomorphism()} function answers the
- question, ``are these two graphs equal?'' By \emph{equal} we mean
- the two graphs have the same structure---the vertices and edges are
- connected in the same way. The mathematical name for this kind of
- equality is \emph{isomorphism}.
- More precisely, an \emph{isomorphism} is a one-to-one mapping of the
- vertices in one graph to the vertices of another graph such that
- adjacency is preserved. Another words, given graphs $G_{1} =
- (V_{1},E_{1})$ and $G_{2} = (V_{2},E_{2})$, an isomorphism is a
- function $f$ such that for all pairs of vertices $a,b$ in $V_{1}$,
- edge $(a,b)$ is in $E_{1}$ if and only if edge $(f(a),f(b))$ is in
- $E_{2}$.
- The graph $G_1$ is \emph{isomorphic} to $G_2$ if an isomorphism exists
- between the two graphs, which we denote by $G_1 \isomorphic G_2$.
- Both graphs must be the same size, so let $N = |V_1| = |V_2|$.
- In the following discussion we will need to use several more notions
- from graph theory. The graph $G_s=(V_s,E_s)$ is a \emph{subgraph} of
- graph $G=(V,E)$ if $V_s \subseteq V$ and $E_s \subseteq E$. An
- \emph{induced subgraph}, denoted by $G[V_s]$, of a graph $G=(V,E)$
- consists of the vertices in $V_s$, which is a subset of $V$, and every
- edge $(u,v)$ in $E$ such that both $u$ and $v$ are in $V_s$. We use
- the notation $E[V_s]$ to mean the edges in $G[V_s]$.
- \section{Backtracking Search}
- \label{sec:backtracking}
- The algorithm used by the \code{isomorphism()} function is, at first
- approximation, an exhaustive search implemented via backtracking. The
- backtracking algorithm is a recursive function. At each stage we will
- try to extend the match that we have found so far. So suppose that we
- have already determined that some subgraph of $G_1$ is isomorphic to a
- subgraph of $G_2$. We then try to add a vertex to each subgraph such
- that the new subgraphs are still isomorphic to one another. At some
- point we may hit a dead end---there are no vertices that can be added
- to extend the isomorphic subgraphs. We then backtrack to previous
- smaller matching subgraphs, and try extending with a different vertex
- choice. The process ends by either finding a complete mapping between
- $G_1$ and $G_2$ and returning true, or by exhausting all possibilities
- and returning false.
- The problem with the exhaustive backtracking algorithm is that there
- are $N!$ possible vertex mappings, and $N!$ gets very large as $N$
- increases, so we need to prune the search space. We use the pruning
- techniques described in
- \cite{deo77:_new_algo_digraph_isomorph,fortin96:_isomorph,reingold77:_combin_algo},
- some of which originated in
- \cite{sussenguth65:_isomorphism,unger64:_isomorphism}. Also, the
- specific backtracking method we use is the one from
- \cite{deo77:_new_algo_digraph_isomorph}.
- We consider the vertices of $G_1$ for addition to the matched subgraph
- in a specific order, so assume that the vertices of $G_1$ are labeled
- $1,\ldots,N$ according to that order. As we will see later, a good
- ordering of the vertices is by DFS discover time. Let $G_1[k]$ denote
- the subgraph of $G_1$ induced by the first $k$ vertices, with $G_1[0]$
- being an empty graph. We also consider the edges of $G_1$ in a
- specific order. We always examine edges in the current subgraph
- $G_1[k]$ first, that is, edges $(u,v)$ where both $u \leq k$ and $v
- \leq k$. This ordering of edges can be acheived by sorting each edge
- $(u,v)$ by lexicographical comparison on the tuple $\langle \max(u,v),
- u, v \rangle$. Figure~\ref{fig:iso-eg} shows an example of a graph
- with the vertices labelled by DFS discover time. The edge ordering for
- this graph is as follows:
- \begin{tabular}{lccccccccc}
- source: &0&1&0&1&3&0&5&6&6\\
- target: &1&2&3&3&2&4&6&4&7
- \end{tabular}
- \vizfig{iso-eg}{Vertices numbered by DFS discover time. The DFS tree
- edges are the solid lines. Nodes $0$ and $5$ are DFS tree root nodes.}
- Each step of the backtracking search moves from left to right though
- the ordered edges. At each step it examines an edge $(i,j)$ of $G_1$
- and decides whether to continue to the left or to go back. There are
- three cases to consider:
- \begin{enumerate}
- \item \label{case:1} $i > k$
- \item \label{case:2} $i \leq k$ and $j > k$.
- \item \label{case:3} $i \leq k$ and $j \leq k$.
- \end{enumerate}
- \paragraph{Case 1: $i > k$.}
- $i$ is not in the matched subgraph $G_1[k]$. This situation only
- happens at the very beginning of the search, or when $i$ is not
- reachable from any of the vertices in $G_1[k]$. This means that we
- are finished with $G_1[k]$. We increment $k$ and find a match for it
- amongst any of the eligible vertices in $V_2 - S$. We then proceed to
- Case 2. It is usually the case that $i$ is equal to the new $k$, but
- when there is another DFS root $r$ with no in-edges or out-edges
- and if $r < i$ then it will be the new $k$.
- \paragraph{Case 2: $i \leq k$ and $j > k$.}
- $i$ is in the matched subgraph $G_1[k]$, but $j$ is not. We are about
- to increment $k$ to try and grow the matched subgraph to include
- $j$. However, first we need to finish verifying that $G_1[k]
- \isomorphic G_2[S]$. In previous steps we proved that $G_1[k-1]
- \isomorphic G_2[S-\{f(k)\}]$, so now we just need to verify the
- extension of the isomorphism to $k$. At this point we are guaranteed
- to have seen all the edges to and from vertex $k$ (because the edges
- are sorted), and in previous steps we have checked that for each edge
- incident on $k$ in $E_1[k]$ there is a matching edge in
- $E_2[S]$. However we still need to check the ``only if'' part of the
- ``if and only if''. So we check that for every edge $(u,v)$ incident
- on $f(k)$ there is $(f^{-1}(u),f^{-1}(v)) \in E_1[k]$. A quick way to
- verify this is to make sure that the number of edges incident on $k$
- in $E_1[k]$ is the same as the number of edges incident on $f(k)$ in
- $E_2[S]$. We create an edge counter that we increment every time we
- see an edge incident on $k$ and decrement for each edge incident on
- $f(k)$. If the counter gets back to zero we know the edges match up.
- Once we have verified that $G_1[k] \isomorphic G_2[S]$ we add $f(k)$
- to $S$, increment $k$, and then try assigning $j$ to
- any of the eligible vertices in $V_2 - S$. More about what
- ``eligible'' means below.
- \paragraph{Case 3: $i \leq k$ and $j \leq k$.}
- Both $i$ and $j$ are in $G_1[k]$. We check to make sure that
- $(f(i),f(j)) \in E_2[S]$ and then proceed to the next edge.
- \subsection{Vertex Invariants}
- \label{sec:vertex-invariants}
- One way to reduce the search space is through the use of \emph{vertex
- invariants}. The idea is to compute a number for each vertex $i(v)$
- such that $i(v) = i(v')$ if there exists some isomorphism $f$ where
- $f(v) = v'$. Then when we look for a match to some vertex $v$, only
- those vertices that have the same vertex invariant number are
- ``eligible''. The number of vertices in a graph with the same vertex
- invariant number $i$ is called the \emph{invariant multiplicity} for
- $i$. In this implementation, by default we use the function $i(v) =
- (|V|+1) \times \outdegree(v) + \indegree(v)$, though the user can also
- supply there own invariant function. The ability of the invariant
- function to prune the search space varies widely with the type of
- graph.
- The following is the definition of the functor that implements the
- default vertex invariant. The functor models the
- \stlconcept{AdaptableUnaryFunction} concept.
- @d Degree vertex invariant functor
- @{
- template <typename InDegreeMap, typename Graph>
- class degree_vertex_invariant
- {
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
- typedef typename graph_traits<Graph>::degree_size_type size_type;
- public:
- typedef vertex_t argument_type;
- typedef 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) { }
- size_type operator()(vertex_t 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
- size_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;
- };
- @}
- \subsection{Vertex Order}
- A good choice of the labeling for the vertices (which determines the
- order in which the subgraph $G_1[k]$ is grown) can also reduce the
- search space. In the following we discuss two labeling heuristics.
- \subsubsection{Most Constrained First}
- Consider the most constrained vertices first. That is, examine
- lower-degree vertices before higher-degree vertices. This reduces the
- search space because it chops off a trunk before the trunk has a
- chance to blossom out. We can generalize this to use vertex
- invariants. We examine vertices with low invariant multiplicity
- before examining vertices with high invariant multiplicity.
- \subsubsection{Adjacent First}
- It only makes sense to examine an edge if one or more of its vertices
- has been assigned a mapping. This means that we should visit vertices
- adjacent to those in the current matched subgraph before proceeding.
- \subsubsection{DFS Order, Starting with Lowest Multiplicity}
- For this implementation, we combine the above two heuristics in the
- following way. To implement the ``adjacent first'' heuristic we apply
- DFS to the graph, and use the DFS discovery order as our vertex
- order. To comply with the ``most constrained first'' heuristic we
- order the roots of our DFS trees by invariant multiplicity.
- \subsection{Implementation of the \code{match} function}
- The \code{match} function implements the recursive backtracking,
- handling the four cases described in \S\ref{sec:backtracking}.
- @d Match function
- @{
- bool match(edge_iter iter, int dfs_num_k)
- {
- if (iter != ordered_edges.end()) {
- vertex1_t i = source(*iter, G1), j = target(*iter, G2);
- if (dfs_num[i] > dfs_num_k) {
- @<Find a match for the DFS tree root $k+1$@>
- }
- else if (dfs_num[j] > dfs_num_k) {
- @<Verify $G_1[k] \isomorphic G_2[S]$ and then find match for $j$@>
- }
- else {
- @<Check to see if $(f(i),f(j)) \in E_2[S]$ and continue@>
- }
- } else
- return true;
- return false;
- }
- @}
- \noindent Now to describe how each of the four cases is implemented.
- \paragraph{Case 1: $i \not\in G_1[k]$.}
- We increment $k$ and try to map it to any of the eligible vertices of
- $V_2 - S$. After matching the new $k$ we proceed by invoking
- \code{match}. We do not yet move on to the next edge, since we have
- not yet found a match for edge, or for target $j$. We reset the edge
- counter to zero.
- @d Find a match for the DFS tree root $k+1$
- @{
- vertex1_t kp1 = dfs_vertices[dfs_num_k + 1];
- BGL_FORALL_VERTICES_T(u, G2, Graph2) {
- if (invariant1(kp1) == invariant2(u) && in_S[u] == false) {
- f[kp1] = u;
- in_S[u] = true;
- num_edges_on_k = 0;
- if (match(iter, dfs_num_k + 1));
- return true;
- in_S[u] = false;
- }
- }
- @}
- \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
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph1> ));
- BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> ));
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph2> ));
- BOOST_CONCEPT_ASSERT(( 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
- BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Invariant1,
- size_type, vertex1_t> ));
- BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Invariant2,
- size_type, vertex2_t> ));
- // Property map requirements
- BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<IsoMapping, vertex1_t> ));
- typedef typename property_traits<IsoMapping>::value_type IsoMappingValue;
- BOOST_STATIC_ASSERT((is_same<IsoMappingValue, vertex2_t>::value));
- BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap1, vertex1_t> ));
- typedef typename property_traits<IndexMap1>::value_type IndexMap1Value;
- BOOST_STATIC_ASSERT((is_convertible<IndexMap1Value, size_type>::value));
- BOOST_CONCEPT_ASSERT(( 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,
- but we want the roots of the DFS tree's to be ordered by invariant
- multiplicity. Therefore we implement the outer-loop of the DFS here
- and then call \code{depth\_\-first\_\-visit} to handle the recursive
- portion of the DFS. The \code{record\_dfs\_order} adapts the DFS to
- record the ordering, storing the results in in the
- \code{dfs\_vertices} and \code{ordered\_edges} arrays. We then create
- the \code{dfs\_num} array which provides a mapping from vertex to DFS
- number.
- @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_num array and dfs_num_map
- dfs_num_vec.resize(num_vertices(G1));
- dfs_num = make_safe_iterator_property_map(dfs_num_vec.begin(),
- dfs_num_vec.size(), index_map1);
- size_type n = 0;
- for (vertex_iter v = dfs_vertices.begin(); v != dfs_vertices.end(); ++v)
- dfs_num[*v] = n++;
- @}
- \noindent The definition of the \code{record\_dfs\_order} visitor
- class is as follows.
- @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<edge1_t>& e)
- : vertices(v), edges(e) { }
- 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(e);
- }
- std::vector<vertex1_t>& vertices;
- std::vector<edge1_t>& edges;
- };
- @}
- The final stage of the setup is to 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$.
- @d Sort edges according to vertex DFS order
- @{
- sort(ordered_edges, edge_cmp(G1, dfs_num));
- @}
- \noindent The edge comparison function object is defined as follows.
- @d Edge comparison predicate
- @{
- struct edge_cmp {
- edge_cmp(const Graph1& G1, DFSNumMap dfs_num)
- : G1(G1), dfs_num(dfs_num) { }
- bool operator()(const edge1_t& e1, const edge1_t& e2) const {
- using namespace std;
- vertex1_t u1 = dfs_num[source(e1,G1)], v1 = dfs_num[target(e1,G1)];
- vertex1_t u2 = dfs_num[source(e2,G1)], v2 = dfs_num[target(e2,G1)];
- int m1 = max(u1, v1);
- int m2 = max(u2, v2);
- // lexicographical comparison
- return make_pair(m1, make_pair(u1, v1))
- < make_pair(m2, make_pair(u2, v2));
- }
- const Graph1& G1;
- DFSNumMap dfs_num;
- };
- @}
- \section{Appendix}
- @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<Graph2>::edge_descriptor edge2_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;
- EdgeCompare edge_compare;
- IndexMap1 index_map1;
- IndexMap2 index_map2;
- @}
- @d Internal data structures
- @{
- std::vector<vertex1_t> dfs_vertices;
- typedef typename std::vector<vertex1_t>::iterator vertex_iter;
- std::vector<int> dfs_num_vec;
- typedef safe_iterator_property_map<typename std::vector<int>::iterator,
- IndexMap1> DFSNumMap;
- DFSNumMap dfs_num;
- std::vector<edge1_t> ordered_edges;
- typedef typename std::vector<edge1_t>::iterator edge_iter;
- std::vector<char> in_S_vec;
- typedef safe_iterator_property_map<typename std::vector<char>::iterator,
- IndexMap2> InSMap;
- InSMap in_S;
- int num_edges_on_k;
- @}
- @d Isomorphism algorithm constructor
- @{
- isomorphism_algo(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)
- : G1(G1), G2(G2), f(f), invariant1(invariant1), invariant2(invariant2),
- max_invariant(max_invariant), edge_compare(edge_compare),
- index_map1(index_map1), index_map2(index_map2)
- {
- in_S_vec.resize(num_vertices(G1));
- in_S = make_safe_iterator_property_map
- (in_S_vec.begin(), in_S_vec.size(), index_map2);
- }
- @}
- @o isomorphism.hpp
- @{
- // Copyright (C) 2001 Jeremy Siek, Douglas Gregor, Brian Osman
- //
- // Permission to copy, use, sell and distribute this software is granted
- // provided this copyright notice appears in all copies.
- // Permission to modify the code and to distribute modified code is granted
- // provided this copyright notice appears in all copies, and a notice
- // that the code was modified is included with the copyright notice.
- //
- // This software is provided "as is" without express or implied warranty,
- // and with no claim as to its suitability for any purpose.
- #ifndef BOOST_GRAPH_ISOMORPHISM_HPP
- #define BOOST_GRAPH_ISOMORPHISM_HPP
- #include <utility>
- #include <vector>
- #include <iterator>
- #include <algorithm>
- #include <boost/graph/iteration_macros.hpp>
- #include <boost/graph/depth_first_search.hpp>
- #include <boost/utility.hpp>
- #include <boost/detail/algorithm.hpp>
- #include <boost/pending/indirect_cmp.hpp> // for make_indirect_pmap
- namespace boost {
- namespace detail {
- @<Isomorphism algorithm class@>
-
- template <typename Graph, typename InDegreeMap>
- void compute_in_degree(const Graph& g, InDegreeMap in_degree_map)
- {
- BGL_FORALL_VERTICES_T(v, g, Graph)
- put(in_degree_map, v, 0);
- BGL_FORALL_VERTICES_T(u, g, Graph)
- BGL_FORALL_ADJ_T(u, v, g, Graph)
- put(in_degree_map, v, get(in_degree_map, v) + 1);
- }
- } // namespace detail
- @<Degree vertex invariant functor@>
- @<Isomorphism function interface@>
- @<Isomorphism function body@>
- namespace detail {
- struct default_edge_compare {
- template <typename Edge1, typename Edge2>
- bool operator()(Edge1 e1, Edge2 e2) const { return true; }
- };
-
- template <typename Graph1, typename Graph2,
- typename IsoMapping,
- typename IndexMap1, typename IndexMap2,
- typename P, typename T, typename R>
- bool isomorphism_impl(const Graph1& G1, const Graph2& G2,
- IsoMapping f, IndexMap1 index_map1, IndexMap2 index_map2,
- const bgl_named_params<P,T,R>& params)
- {
- std::vector<std::size_t> in_degree1_vec(num_vertices(G1));
- typedef safe_iterator_property_map<std::vector<std::size_t>::iterator,
- IndexMap1> InDeg1;
- InDeg1 in_degree1(in_degree1_vec.begin(), in_degree1_vec.size(), index_map1);
- compute_in_degree(G1, in_degree1);
- std::vector<std::size_t> in_degree2_vec(num_vertices(G2));
- typedef safe_iterator_property_map<std::vector<std::size_t>::iterator,
- IndexMap2> InDeg2;
- InDeg2 in_degree2(in_degree2_vec.begin(), in_degree2_vec.size(), index_map2);
- compute_in_degree(G2, in_degree2);
- degree_vertex_invariant<InDeg1, Graph1> invariant1(in_degree1, G1);
- degree_vertex_invariant<InDeg2, Graph2> invariant2(in_degree2, G2);
- default_edge_compare edge_cmp;
- return isomorphism(G1, G2, f,
- choose_param(get_param(params, vertex_invariant1_t()), invariant1),
- choose_param(get_param(params, vertex_invariant2_t()), invariant2),
- choose_param(get_param(params, vertex_max_invariant_t()),
- invariant2.max()),
- choose_param(get_param(params, edge_compare_t()), edge_cmp),
- 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 = num_vertices(g1);
- std::vector<vertex2_t> f(n);
- return detail::isomorphism_impl
- (g1, g2,
- choose_param(get_param(params, vertex_isomorphism_t()),
- make_safe_iterator_property_map(f.begin(), f.size(),
- choose_const_pmap(get_param(params, vertex_index1),
- g1, vertex_index), vertex2_t())),
- 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)
- {
- return isomorphism(g1, g2,
- bgl_named_params<int, buffer_param_t>(0));// bogus named param
- }
- // 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 0
- // problematic for filtered_graph!
- if (num_vertices(g1) != num_vertices(g2) || num_edges(g1) != num_edges(g2))
- return false;
- #endif
-
- 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
- #include <boost/graph/iteration_macros_undef.hpp>
- #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 IsoMapping 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 edge_iter_t IndexMap desc RPH ATCH pre
- % LocalWords: iterators VertexListGraph EdgeListGraph BidirectionalGraph tmp
- % LocalWords: ReadWritePropertyMap VertexListGraphConcept EdgeListGraphConcept
- % LocalWords: BidirectionalGraphConcept ReadWritePropertyMapConcept indices ei
- % LocalWords: IsoMappingValue ReadablePropertyMapConcept namespace InvarFun
- % LocalWords: MultMap vip inline bitset typedefs fj hpp ifndef adaptor params
- % LocalWords: bgl param pmap endif
|