]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | \documentclass[11pt]{report} |
2 | ||
3 | %\input{defs} | |
4 | \usepackage{math} | |
5 | \usepackage{jweb} | |
6 | \usepackage{lgrind} | |
7 | \usepackage{times} | |
8 | \usepackage{fullpage} | |
9 | \usepackage{graphicx} | |
10 | ||
11 | \newif\ifpdf | |
12 | \ifx\pdfoutput\undefined | |
13 | \pdffalse | |
14 | \else | |
15 | \pdfoutput=1 | |
16 | \pdftrue | |
17 | \fi | |
18 | ||
19 | \ifpdf | |
20 | \usepackage[ | |
21 | pdftex, | |
22 | colorlinks=true, %change to true for the electronic version | |
23 | linkcolor=blue,filecolor=blue,pagecolor=blue,urlcolor=blue | |
24 | ]{hyperref} | |
25 | \fi | |
26 | ||
27 | \ifpdf | |
28 | \newcommand{\stlconcept}[1]{\href{http://www.sgi.com/tech/stl/#1.html}{{\small \textsf{#1}}}} | |
29 | \newcommand{\bglconcept}[1]{\href{http://www.boost.org/libs/graph/doc/#1.html}{{\small \textsf{#1}}}} | |
30 | \newcommand{\pmconcept}[1]{\href{http://www.boost.org/libs/property_map/#1.html}{{\small \textsf{#1}}}} | |
31 | \newcommand{\myhyperref}[2]{\hyperref[#1]{#2}} | |
32 | \newcommand{\vizfig}[2]{\begin{figure}[htbp]\centerline{\includegraphics*{#1.pdf}}\caption{#2}\label{fig:#1}\end{figure}} | |
33 | \else | |
34 | \newcommand{\myhyperref}[2]{#2} | |
35 | \newcommand{\bglconcept}[1]{{\small \textsf{#1}}} | |
36 | \newcommand{\pmconcept}[1]{{\small \textsf{#1}}} | |
37 | \newcommand{\stlconcept}[1]{{\small \textsf{#1}}} | |
38 | \newcommand{\vizfig}[2]{\begin{figure}[htbp]\centerline{\includegraphics*{#1.eps}}\caption{#2}\label{fig:#1}\end{figure}} | |
39 | \fi | |
40 | ||
41 | \newcommand{\code}[1]{{\small{\em \textbf{#1}}}} | |
42 | ||
43 | ||
44 | % jweb -np isomorphism-impl.w; dot -Tps out.dot -o out.eps; dot -Tps in.dot -o in.eps; latex isomorphism-impl.tex; dvips isomorphism-impl.dvi -o isomorphism-impl.ps | |
45 | ||
46 | \setlength\overfullrule{5pt} | |
47 | \tolerance=10000 | |
48 | \sloppy | |
49 | \hfuzz=10pt | |
50 | ||
51 | \makeindex | |
52 | ||
53 | \newcommand{\isomorphic}{\cong} | |
54 | ||
55 | \begin{document} | |
56 | ||
57 | \title{An Implementation of Isomorphism Testing} | |
58 | \author{Jeremy G. Siek} | |
59 | ||
60 | \maketitle | |
61 | ||
62 | \section{Introduction} | |
63 | ||
64 | This paper documents the implementation of the \code{isomorphism()} | |
65 | function of the Boost Graph Library. The implementation was by Jeremy | |
66 | Siek with algorithmic improvements and test code from Douglas Gregor. | |
67 | The \code{isomorphism()} function answers the question, ``are these | |
68 | two graphs equal?'' By \emph{equal}, we mean the two graphs have the | |
69 | same structure---the vertices and edges are connected in the same | |
70 | way. The mathematical name for this kind of equality is | |
71 | \emph{isomorphic}. | |
72 | ||
73 | An \emph{isomorphism} is a one-to-one mapping of the vertices in one | |
74 | graph to the vertices of another graph such that adjacency is | |
75 | preserved. Another words, given graphs $G_{1} = (V_{1},E_{1})$ and | |
76 | $G_{2} = (V_{2},E_{2})$, an isomorphism is a function $f$ such that | |
77 | for all pairs of vertices $a,b$ in $V_{1}$, edge $(a,b)$ is in $E_{1}$ | |
78 | if and only if edge $(f(a),f(b))$ is in $E_{2}$. | |
79 | ||
80 | Both graphs must be the same size, so let $N = |V_1| = |V_2|$. The | |
81 | graph $G_1$ is \emph{isomorphic} to $G_2$ if an isomorphism exists | |
82 | between the two graphs, which we denote by $G_1 \isomorphic G_2$. | |
83 | ||
84 | In the following discussion we will need to use several notions from | |
85 | graph theory. The graph $G_s=(V_s,E_s)$ is a \emph{subgraph} of graph | |
86 | $G=(V,E)$ if $V_s \subseteq V$ and $E_s \subseteq E$. An | |
87 | \emph{induced subgraph}, denoted by $G[V_s]$, of a graph $G=(V,E)$ | |
88 | consists of the vertices in $V_s$, which is a subset of $V$, and every | |
89 | edge $(u,v)$ in $E$ such that both $u$ and $v$ are in $V_s$. We use | |
90 | the notation $E[V_s]$ to mean the edges in $G[V_s]$. | |
91 | ||
92 | In some places we express a function as a set of pairs, so the set $f | |
93 | = \{ \pair{a_1}{b_1}, \ldots, \pair{a_n}{b_n} \}$ | |
94 | means $f(a_i) = b_i$ for $i=1,\ldots,n$. | |
95 | ||
96 | \section{Exhaustive Backtracking Search} | |
97 | ||
98 | The algorithm used by the \code{isomorphism()} function is, at | |
99 | first approximation, an exhaustive search implemented via | |
100 | backtracking. The backtracking algorithm is a recursive function. At | |
101 | each stage we will try to extend the match that we have found so far. | |
102 | So suppose that we have already determined that some subgraph of $G_1$ | |
103 | is isomorphic to a subgraph of $G_2$. We then try to add a vertex to | |
104 | each subgraph such that the new subgraphs are still isomorphic to one | |
105 | another. At some point we may hit a dead end---there are no vertices | |
106 | that can be added to extend the isomorphic subgraphs. We then | |
107 | backtrack to previous smaller matching subgraphs, and try extending | |
108 | with a different vertex choice. The process ends by either finding a | |
109 | complete mapping between $G_1$ and $G_2$ and return true, or by | |
110 | exhausting all possibilities and returning false. | |
111 | ||
112 | We are going to consider the vertices of $G_1$ in a specific order | |
113 | (more about this later), so assume that the vertices of $G_1$ are | |
114 | labeled $1,\ldots,N$ according to the order that we plan to add them | |
115 | to the subgraph. Let $G_1[k]$ denote the subgraph of $G_1$ induced by | |
116 | the first $k$ vertices, with $G_1[0]$ being an empty graph. At each | |
117 | stage of the recursion we start with an isomorphism $f_{k-1}$ between | |
118 | $G_1[k-1]$ and a subgraph of $G_2$, which we denote by $G_2[S]$, so | |
119 | $G_1[k-1] \isomorphic G_2[S]$. The vertex set $S$ is the subset of | |
120 | $V_2$ that corresponds via $f_{k-1}$ to the first $k-1$ vertices in | |
121 | $G_1$. We try to extend the isomorphism by finding a vertex $v \in V_2 | |
122 | - S$ that matches with vertex $k$. If a matching vertex is found, we | |
123 | have a new isomorphism $f_k$ with $G_1[k] \isomorphic G_2[S \union \{ | |
124 | v \}]$. | |
125 | ||
126 | \begin{tabbing} | |
127 | IS\=O\=M\=O\=RPH($k$, $S$, $f_{k-1}$) $\equiv$ \\ | |
128 | \>\textbf{if} ($k = |V_1|+1$) \\ | |
129 | \>\>\textbf{return} true \\ | |
130 | \>\textbf{for} each vertex $v \in V_2 - S$ \\ | |
131 | \>\>\textbf{if} (MATCH($k$, $v$)) \\ | |
132 | \>\>\>$f_k = f_{k-1} \union \pair{k}{v}$ \\ | |
133 | \>\>\>ISOMORPH($k+1$, $S \union \{ v \}$, $f_k$)\\ | |
134 | \>\>\textbf{else}\\ | |
135 | \>\>\>\textbf{return} false \\ | |
136 | \\ | |
137 | ISOMORPH($0$, $G_1$, $\emptyset$, $G_2$) | |
138 | \end{tabbing} | |
139 | ||
140 | The basic idea of the match operation is to check whether $G_1[k]$ is | |
141 | isomorphic to $G_2[S \union \{ v \}]$. We already know that $G_1[k-1] | |
142 | \isomorphic G_2[S]$ with the mapping $f_{k-1}$, so all we need to do | |
143 | is verify that the edges in $E_1[k] - E_1[k-1]$ connect vertices that | |
144 | correspond to the vertices connected by the edges in $E_2[S \union \{ | |
145 | v \}] - E_2[S]$. The edges in $E_1[k] - E_1[k-1]$ are all the | |
146 | out-edges $(k,j)$ and in-edges $(j,k)$ of $k$ where $j$ is less than | |
147 | or equal to $k$ according to the ordering. The edges in $E_2[S \union | |
148 | \{ v \}] - E_2[S]$ consists of all the out-edges $(v,u)$ and | |
149 | in-edges $(u,v)$ of $v$ where $u \in S$. | |
150 | ||
151 | \begin{tabbing} | |
152 | M\=ATCH($k$, $v$) $\equiv$ \\ | |
153 | \>$out \leftarrow \forall (k,j) \in E_1[k] - E_1[k-1] \Big( (v,f(j)) \in E_2[S \union \{ v \}] - E_2[S] \Big)$ \\ | |
154 | \>$in \leftarrow \forall (j,k) \in E_1[k] - E_1[k-1] \Big( (f(j),v) \in E_2[S \union \{ v \}] - E_2[S] \Big)$ \\ | |
155 | \>\textbf{return} $out \Land in$ | |
156 | \end{tabbing} | |
157 | ||
158 | The problem with the exhaustive backtracking algorithm is that there | |
159 | are $N!$ possible vertex mappings, and $N!$ gets very large as $N$ | |
160 | increases, so we need to prune the search space. We use the pruning | |
161 | techniques described in | |
162 | \cite{deo77:_new_algo_digraph_isomorph,fortin96:_isomorph,reingold77:_combin_algo} | |
163 | that originated in | |
164 | \cite{sussenguth65:_isomorphism,unger64:_isomorphism}. | |
165 | ||
166 | \section{Vertex Invariants} | |
167 | \label{sec:vertex-invariants} | |
168 | ||
169 | One way to reduce the search space is through the use of \emph{vertex | |
170 | invariants}. The idea is to compute a number for each vertex $i(v)$ | |
171 | such that $i(v) = i(v')$ if there exists some isomorphism $f$ where | |
172 | $f(v) = v'$. Then when we look for a match to some vertex $v$, we only | |
173 | need to consider those vertices that have the same vertex invariant | |
174 | number. The number of vertices in a graph with the same vertex | |
175 | invariant number $i$ is called the \emph{invariant multiplicity} for | |
176 | $i$. In this implementation, by default we use the out-degree of the | |
177 | vertex as the vertex invariant, though the user can also supply their | |
178 | own invariant function. The ability of the invariant function to prune | |
179 | the search space varies widely with the type of graph. | |
180 | ||
181 | As a first check to rule out graphs that have no possibility of | |
182 | matching, one can create a list of computed vertex invariant numbers | |
183 | for the vertices in each graph, sort the two lists, and then compare | |
184 | them. If the two lists are different then the two graphs are not | |
185 | isomorphic. If the two lists are the same then the two graphs may be | |
186 | isomorphic. | |
187 | ||
188 | Also, we extend the MATCH operation to use the vertex invariants to | |
189 | help rule out vertices. | |
190 | ||
191 | \begin{tabbing} | |
192 | M\=A\=T\=C\=H-INVAR($k$, $v$) $\equiv$ \\ | |
193 | \>$out \leftarrow \forall (k,j) \in E_1[k] - E_1[k-1] \Big( (v,f(j)) \in E_2[S \union \{ v \}] - E_2[S] \Land i(v) = i(k) \Big)$ \\ | |
194 | \>$in \leftarrow \forall (j,k) \in E_1[k] - E_1[k-1] \Big( (f(j),v) \in E_2[S \union \{ v \}] - E_2[S] \Land i(v) = i(k) \Big)$ \\ | |
195 | \>\textbf{return} $out \Land in$ | |
196 | \end{tabbing} | |
197 | ||
198 | \section{Vertex Order} | |
199 | ||
200 | A good choice of the labeling for the vertices (which determines the | |
201 | order in which the subgraph $G_1[k]$ is grown) can also reduce the | |
202 | search space. In the following we discuss two labeling heuristics. | |
203 | ||
204 | \subsection{Most Constrained First} | |
205 | ||
206 | Consider the most constrained vertices first. That is, examine | |
207 | lower-degree vertices before higher-degree vertices. This reduces the | |
208 | search space because it chops off a trunk before the trunk has a | |
209 | chance to blossom out. We can generalize this to use vertex | |
210 | invariants. We examine vertices with low invariant multiplicity | |
211 | before examining vertices with high invariant multiplicity. | |
212 | ||
213 | \subsection{Adjacent First} | |
214 | ||
215 | The MATCH operation only considers edges when the other vertex already | |
216 | has a mapping defined. This means that the MATCH operation can only | |
217 | weed out vertices that are adjacent to vertices that have already been | |
218 | matched. Therefore, when choosing the next vertex to examine, it is | |
219 | desirable to choose one that is adjacent a vertex already in $S_1$. | |
220 | ||
221 | \subsection{DFS Order, Starting with Lowest Multiplicity} | |
222 | ||
223 | For this implementation, we combine the above two heuristics in the | |
224 | following way. To implement the ``adjacent first'' heuristic we apply | |
225 | DFS to the graph, and use the DFS discovery order as our vertex | |
226 | order. To comply with the ``most constrained first'' heuristic we | |
227 | order the roots of our DFS trees by invariant multiplicity. | |
228 | ||
229 | ||
230 | \section{Implementation} | |
231 | ||
232 | The following is the public interface for the \code{isomorphism} | |
233 | function. The input to the function is the two graphs $G_1$ and $G_2$, | |
234 | mappings from the vertices in the graphs to integers (in the range | |
235 | $[0,|V|)$), and a vertex invariant function object. The output of the | |
236 | function is an isomorphism $f$ if there is one. The \code{isomorphism} | |
237 | function returns true if the graphs are isomorphic and false | |
238 | otherwise. The requirements on type template parameters are described | |
239 | below in the section ``Concept checking''. | |
240 | ||
241 | @d Isomorphism Function Interface | |
242 | @{ | |
243 | template <typename Graph1, typename Graph2, | |
244 | typename IndexMapping, | |
245 | typename VertexInvariant1, typename VertexInvariant2, | |
246 | typename IndexMap1, typename IndexMap2> | |
247 | bool isomorphism(const Graph1& g1, const Graph2& g2, | |
248 | IndexMapping f, | |
249 | VertexInvariant1 invariant1, VertexInvariant2 invariant2, | |
250 | IndexMap1 index_map1, IndexMap2 index_map2) | |
251 | @} | |
252 | ||
253 | The main outline of the \code{isomorphism} function is as | |
254 | follows. Most of the steps in this function are for setting up the | |
255 | vertex ordering, first ordering the vertices by invariant multiplicity | |
256 | and then by DFS order. The last step is the call to the | |
257 | \code{isomorph} function which starts the backtracking search. | |
258 | ||
259 | @d Isomorphism Function Body | |
260 | @{ | |
261 | { | |
262 | @<Some type definitions and iterator declarations@> | |
263 | @<Concept checking@> | |
264 | @<Quick return with false if $|V_1| \neq |V_2|$@> | |
265 | @<Compute vertex invariants@> | |
266 | @<Quick return if the graph's invariants do not match@> | |
267 | @<Compute invariant multiplicity@> | |
268 | @<Sort vertices by invariant multiplicity@> | |
269 | @<Order the vertices by DFS discover time@> | |
270 | @<Order the edges by DFS discover time@> | |
271 | @<Invoke recursive \code{isomorph} function@> | |
272 | } | |
273 | @} | |
274 | ||
275 | There are some types that will be used throughout the function, which | |
276 | we create shortened names for here. We will also need vertex | |
277 | iterators for \code{g1} and \code{g2} in several places, so we define | |
278 | them here. | |
279 | ||
280 | @d Some type definitions and iterator declarations | |
281 | @{ | |
282 | typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t; | |
283 | typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t; | |
284 | typedef typename graph_traits<Graph1>::vertices_size_type size_type; | |
285 | typename graph_traits<Graph1>::vertex_iterator i1, i1_end; | |
286 | typename graph_traits<Graph2>::vertex_iterator i2, i2_end; | |
287 | @} | |
288 | ||
289 | We use the Boost Concept Checking Library to make sure that the type | |
290 | arguments to the function fulfill there requirements. The | |
291 | \code{Graph1} type must be a \bglconcept{VertexListGraph} and a | |
292 | \bglconcept{EdgeListGraph}. The \code{Graph2} type must be a | |
293 | \bglconcept{VertexListGraph} and a | |
294 | \bglconcept{BidirectionalGraph}. The \code{IndexMapping} type that | |
295 | represents the isomorphism $f$ must be a | |
296 | \pmconcept{ReadWritePropertyMap} that maps from vertices in $G_1$ to | |
297 | vertices in $G_2$. The two other index maps are | |
298 | \pmconcept{ReadablePropertyMap}s from vertices in $G_1$ and $G_2$ to | |
299 | unsigned integers. | |
300 | ||
301 | @d Concept checking | |
302 | @{ | |
303 | // Graph requirements | |
304 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph1> )); | |
305 | BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> )); | |
306 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph2> )); | |
307 | BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph2> )); | |
308 | ||
309 | // Property map requirements | |
310 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<IndexMapping, vertex1_t> )); | |
311 | typedef typename property_traits<IndexMapping>::value_type IndexMappingValue; | |
312 | BOOST_STATIC_ASSERT((is_same<IndexMappingValue, vertex2_t>::value)); | |
313 | ||
314 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap1, vertex1_t> )); | |
315 | typedef typename property_traits<IndexMap1>::value_type IndexMap1Value; | |
316 | BOOST_STATIC_ASSERT((is_convertible<IndexMap1Value, size_type>::value)); | |
317 | ||
318 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap2, vertex2_t> )); | |
319 | typedef typename property_traits<IndexMap2>::value_type IndexMap2Value; | |
320 | BOOST_STATIC_ASSERT((is_convertible<IndexMap2Value, size_type>::value)); | |
321 | @} | |
322 | ||
323 | ||
324 | \noindent If there are no vertices in either graph, then they are trivially | |
325 | isomorphic. | |
326 | ||
327 | @d Quick return with false if $|V_1| \neq |V_2|$ | |
328 | @{ | |
329 | if (num_vertices(g1) != num_vertices(g2)) | |
330 | return false; | |
331 | @} | |
332 | ||
333 | ||
334 | \subsection{Ordering by Vertex Invariant Multiplicity} | |
335 | ||
336 | The user can supply the vertex invariant functions as a | |
337 | \stlconcept{AdaptableUnaryFunction} (with the addition of the | |
338 | \code{max} function) in the \code{invariant1} and \code{invariant2} | |
339 | parameters. We also define a default which uses the out-degree and | |
340 | in-degree of a vertex. The following is the definition of the function | |
341 | object for the default vertex invariant. User-defined vertex invariant | |
342 | function objects should follow the same pattern. | |
343 | ||
344 | @d Degree vertex invariant | |
345 | @{ | |
346 | template <typename InDegreeMap, typename Graph> | |
347 | class degree_vertex_invariant | |
348 | { | |
349 | public: | |
350 | typedef typename graph_traits<Graph>::vertex_descriptor argument_type; | |
351 | typedef typename graph_traits<Graph>::degree_size_type result_type; | |
352 | ||
353 | degree_vertex_invariant(const InDegreeMap& in_degree_map, const Graph& g) | |
354 | : m_in_degree_map(in_degree_map), m_g(g) { } | |
355 | ||
356 | result_type operator()(argument_type v) const { | |
357 | return (num_vertices(m_g) + 1) * out_degree(v, m_g) | |
358 | + get(m_in_degree_map, v); | |
359 | } | |
360 | // The largest possible vertex invariant number | |
361 | result_type max() const { | |
362 | return num_vertices(m_g) * num_vertices(m_g) + num_vertices(m_g); | |
363 | } | |
364 | private: | |
365 | InDegreeMap m_in_degree_map; | |
366 | const Graph& m_g; | |
367 | }; | |
368 | @} | |
369 | ||
370 | Since the invariant function may be expensive to compute, we | |
371 | pre-compute the invariant numbers for every vertex in the two | |
372 | graphs. The variables \code{invar1} and \code{invar2} are property | |
373 | maps for accessing the stored invariants, which are described next. | |
374 | ||
375 | @d Compute vertex invariants | |
376 | @{ | |
377 | @<Setup storage for vertex invariants@> | |
378 | for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1) | |
379 | invar1[*i1] = invariant1(*i1); | |
380 | for (tie(i2, i2_end) = vertices(g2); i2 != i2_end; ++i2) | |
381 | invar2[*i2] = invariant2(*i2); | |
382 | @} | |
383 | ||
384 | \noindent We store the invariants in two vectors, indexed by the vertex indices | |
385 | of the two graphs. We then create property maps for accessing these | |
386 | two vectors in a more convenient fashion (they go directly from vertex | |
387 | to invariant, instead of vertex to index to invariant). | |
388 | ||
389 | @d Setup storage for vertex invariants | |
390 | @{ | |
391 | typedef typename VertexInvariant1::result_type InvarValue1; | |
392 | typedef typename VertexInvariant2::result_type InvarValue2; | |
393 | typedef std::vector<InvarValue1> invar_vec1_t; | |
394 | typedef std::vector<InvarValue2> invar_vec2_t; | |
395 | invar_vec1_t invar1_vec(num_vertices(g1)); | |
396 | invar_vec2_t invar2_vec(num_vertices(g2)); | |
397 | typedef typename invar_vec1_t::iterator vec1_iter; | |
398 | typedef typename invar_vec2_t::iterator vec2_iter; | |
399 | iterator_property_map<vec1_iter, IndexMap1, InvarValue1, InvarValue1&> | |
400 | invar1(invar1_vec.begin(), index_map1); | |
401 | iterator_property_map<vec2_iter, IndexMap2, InvarValue2, InvarValue2&> | |
402 | invar2(invar2_vec.begin(), index_map2); | |
403 | @} | |
404 | ||
405 | As discussed in \S\ref{sec:vertex-invariants}, we can quickly rule out | |
406 | the possibility of any isomorphism between two graphs by checking to | |
407 | see if the vertex invariants can match up. We sort both vectors of vertex | |
408 | invariants, and then check to see if they are equal. | |
409 | ||
410 | @d Quick return if the graph's invariants do not match | |
411 | @{ | |
412 | { // check if the graph's invariants do not match | |
413 | invar_vec1_t invar1_tmp(invar1_vec); | |
414 | invar_vec2_t invar2_tmp(invar2_vec); | |
415 | std::sort(invar1_tmp.begin(), invar1_tmp.end()); | |
416 | std::sort(invar2_tmp.begin(), invar2_tmp.end()); | |
417 | if (! std::equal(invar1_tmp.begin(), invar1_tmp.end(), | |
418 | invar2_tmp.begin())) | |
419 | return false; | |
420 | } | |
421 | @} | |
422 | ||
423 | Next we compute the invariant multiplicity, the number of vertices | |
424 | with the same invariant number. The \code{invar\_mult} vector is | |
425 | indexed by invariant number. We loop through all the vertices in the | |
426 | graph to record the multiplicity. | |
427 | ||
428 | @d Compute invariant multiplicity | |
429 | @{ | |
430 | std::vector<std::size_t> invar_mult(invariant1.max(), 0); | |
431 | for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1) | |
432 | ++invar_mult[invar1[*i1]]; | |
433 | @} | |
434 | ||
435 | \noindent We then order the vertices by their invariant multiplicity. | |
436 | This will allow us to search the more constrained vertices first. | |
437 | Since we will need to know the permutation from the original order to | |
438 | the new order, we do not sort the vertices directly. Instead we sort | |
439 | the vertex indices, creating the \code{perm} array. Once sorted, this | |
440 | array provides a mapping from the new index to the old index. | |
441 | We then use the \code{permute} function to sort the vertices of | |
442 | the graph, which we store in the \code{g1\_vertices} vector. | |
443 | ||
444 | @d Sort vertices by invariant multiplicity | |
445 | @{ | |
446 | std::vector<size_type> perm; | |
447 | integer_range<size_type> range(0, num_vertices(g1)); | |
448 | std::copy(range.begin(), range.end(), std::back_inserter(perm)); | |
449 | std::sort(perm.begin(), perm.end(), | |
450 | detail::compare_invariant_multiplicity(invar1_vec.begin(), | |
451 | invar_mult.begin())); | |
452 | ||
453 | std::vector<vertex1_t> g1_vertices; | |
454 | for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1) | |
455 | g1_vertices.push_back(*i1); | |
456 | permute(g1_vertices.begin(), g1_vertices.end(), perm.begin()); | |
457 | @} | |
458 | ||
459 | \noindent The definition of the \code{compare\_multiplicity} predicate | |
460 | is shown below. This predicate provides the glue that binds | |
461 | \code{std::sort} to our current purpose. | |
462 | ||
463 | @d Compare multiplicity predicate | |
464 | @{ | |
465 | namespace detail { | |
466 | template <typename InvarMap, typename MultMap> | |
467 | struct compare_invariant_multiplicity_predicate | |
468 | { | |
469 | compare_invariant_multiplicity_predicate(InvarMap i, MultMap m) | |
470 | : m_invar(i), m_mult(m) { } | |
471 | ||
472 | template <typename Vertex> | |
473 | bool operator()(const Vertex& x, const Vertex& y) const | |
474 | { return m_mult[m_invar[x]] < m_mult[m_invar[y]]; } | |
475 | ||
476 | InvarMap m_invar; | |
477 | MultMap m_mult; | |
478 | }; | |
479 | template <typename InvarMap, typename MultMap> | |
480 | compare_invariant_multiplicity_predicate<InvarMap, MultMap> | |
481 | compare_invariant_multiplicity(InvarMap i, MultMap m) { | |
482 | return compare_invariant_multiplicity_predicate<InvarMap, MultMap>(i,m); | |
483 | } | |
484 | } // namespace detail | |
485 | @} | |
486 | ||
487 | ||
488 | \subsection{Ordering by DFS Discover Time} | |
489 | ||
490 | To implement the ``visit adjacent vertices first'' heuristic, we order | |
491 | the vertices according to DFS discover time. We replace the ordering | |
492 | in \code{perm} with the new DFS ordering. Again, we use \code{permute} | |
493 | to sort the vertices of graph \code{g1}. | |
494 | ||
495 | @d Order the vertices by DFS discover time | |
496 | @{ | |
497 | { | |
498 | perm.clear(); | |
499 | @<Compute DFS discover times@> | |
500 | g1_vertices.clear(); | |
501 | for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1) | |
502 | g1_vertices.push_back(*i1); | |
503 | permute(g1_vertices.begin(), g1_vertices.end(), perm.begin()); | |
504 | } | |
505 | @} | |
506 | ||
507 | We implement the outer-loop of the DFS here, instead of calling the | |
508 | \code{depth\_first\_search} function, because we want the roots of the | |
509 | DFS tree's to be ordered by invariant multiplicity. We call | |
510 | \code{depth\_\-first\_\-visit} to implement the recursive portion of | |
511 | the DFS. The \code{record\_dfs\_order} adapts the DFS to record | |
512 | the order in which DFS discovers the vertices. | |
513 | ||
514 | @d Compute DFS discover times | |
515 | @{ | |
516 | std::vector<default_color_type> color_vec(num_vertices(g1)); | |
517 | for (typename std::vector<vertex1_t>::iterator ui = g1_vertices.begin(); | |
518 | ui != g1_vertices.end(); ++ui) { | |
519 | if (color_vec[get(index_map1, *ui)] | |
520 | == color_traits<default_color_type>::white()) { | |
521 | depth_first_visit | |
522 | (g1, *ui, detail::record_dfs_order<Graph1, IndexMap1>(perm, | |
523 | index_map1), | |
524 | make_iterator_property_map(&color_vec[0], index_map1, | |
525 | color_vec[0])); | |
526 | } | |
527 | } | |
528 | @} | |
529 | ||
530 | \noindent The definition of the \code{record\_dfs\_order} visitor | |
531 | class is as follows. The index of each vertex is recorded in the | |
532 | \code{dfs\_order} vector (which is the \code{perm} vector) in the | |
533 | \code{discover\_vertex} event point. | |
534 | ||
535 | @d Record DFS ordering visitor | |
536 | @{ | |
537 | namespace detail { | |
538 | template <typename Graph1, typename IndexMap1> | |
539 | struct record_dfs_order : public default_dfs_visitor { | |
540 | typedef typename graph_traits<Graph1>::vertices_size_type size_type; | |
541 | typedef typename graph_traits<Graph1>::vertex_descriptor vertex; | |
542 | ||
543 | record_dfs_order(std::vector<size_type>& dfs_order, IndexMap1 index) | |
544 | : dfs_order(dfs_order), index(index) { } | |
545 | ||
546 | void discover_vertex(vertex v, const Graph1& g) const { | |
547 | dfs_order.push_back(get(index, v)); | |
548 | } | |
549 | std::vector<size_type>& dfs_order; | |
550 | IndexMap1 index; | |
551 | }; | |
552 | } // namespace detail | |
553 | @} | |
554 | ||
555 | ||
556 | In the MATCH operation, we need to examine all the edges in the set | |
557 | $E_1[k] - E_1[k-1]$. That is, we need to loop through all the edges of | |
558 | the form $(k,j)$ or $(j,k)$ where $j \leq k$. To do this efficiently, | |
559 | we create an array of all the edges in $G_1$ that has been sorted so | |
560 | that $E_1[k] - E_1[k-1]$ forms a contiguous range. To each edge | |
561 | $e=(u,v)$ we assign the number $\max(u,v)$, and then sort the edges by | |
562 | this number. All the edges $(u,v) \in E_1[k] - E_1[k-1]$ can then be | |
563 | identified because $\max(u,v) = k$. The following code creates an | |
564 | array of edges and then sorts them. The \code{edge\_\-ordering\_\-fun} | |
565 | function object is described next. | |
566 | ||
567 | @d Order the edges by DFS discover time | |
568 | @{ | |
569 | typedef typename graph_traits<Graph1>::edge_descriptor edge1_t; | |
570 | std::vector<edge1_t> edge_set; | |
571 | std::copy(edges(g1).first, edges(g1).second, std::back_inserter(edge_set)); | |
572 | ||
573 | std::sort(edge_set.begin(), edge_set.end(), | |
574 | detail::edge_ordering | |
575 | (make_iterator_property_map(perm.begin(), index_map1, perm[0]), g1)); | |
576 | @} | |
577 | ||
578 | \noindent The \code{edge\_order} function computes the ordering number | |
579 | for an edge, which for edge $e=(u,v)$ is $\max(u,v)$. The | |
580 | \code{edge\_\-ordering\_\-fun} function object simply returns | |
581 | comparison of two edge's ordering numbers. | |
582 | ||
583 | @d Isomorph edge ordering predicate | |
584 | @{ | |
585 | namespace detail { | |
586 | ||
587 | template <typename VertexIndexMap, typename Graph> | |
588 | std::size_t edge_order(const typename graph_traits<Graph>::edge_descriptor e, | |
589 | VertexIndexMap index_map, const Graph& g) { | |
590 | return std::max(get(index_map, source(e, g)), get(index_map, target(e, g))); | |
591 | } | |
592 | ||
593 | template <typename VertexIndexMap, typename Graph> | |
594 | class edge_ordering_fun { | |
595 | public: | |
596 | edge_ordering_fun(VertexIndexMap vip, const Graph& g) | |
597 | : m_index_map(vip), m_g(g) { } | |
598 | template <typename Edge> | |
599 | bool operator()(const Edge& e1, const Edge& e2) const { | |
600 | return edge_order(e1, m_index_map, m_g) < edge_order(e2, m_index_map, m_g); | |
601 | } | |
602 | VertexIndexMap m_index_map; | |
603 | const Graph& m_g; | |
604 | }; | |
605 | template <class VertexIndexMap, class G> | |
606 | inline edge_ordering_fun<VertexIndexMap,G> | |
607 | edge_ordering(VertexIndexMap vip, const G& g) | |
608 | { | |
609 | return edge_ordering_fun<VertexIndexMap,G>(vip, g); | |
610 | } | |
611 | } // namespace detail | |
612 | @} | |
613 | ||
614 | ||
615 | We are now ready to enter the main part of the algorithm, the | |
616 | backtracking search implemented by the \code{isomorph} function (which | |
617 | corresponds to the ISOMORPH algorithm). The set $S$ is not | |
618 | represented directly; instead we represent $V_2 - S$. Initially $S = | |
619 | \emptyset$ so $V_2 - S = V_2$. We use the permuted indices for the | |
620 | vertices of graph \code{g1}. We represent $V_2 - S$ with a bitset. We | |
621 | use \code{std::vector} instead of \code{boost::dyn\_bitset} for speed | |
622 | instead of space. | |
623 | ||
624 | @d Invoke recursive \code{isomorph} function | |
625 | @{ | |
626 | std::vector<char> not_in_S_vec(num_vertices(g2), true); | |
627 | iterator_property_map<char*, IndexMap2, char, char&> | |
628 | not_in_S(¬_in_S_vec[0], index_map2); | |
629 | ||
630 | return detail::isomorph(g1_vertices.begin(), g1_vertices.end(), | |
631 | edge_set.begin(), edge_set.end(), g1, g2, | |
632 | make_iterator_property_map(perm.begin(), index_map1, perm[0]), | |
633 | index_map2, f, invar1, invar2, not_in_S); | |
634 | @} | |
635 | ||
636 | ||
637 | \subsection{Implementation of ISOMORPH} | |
638 | ||
639 | The ISOMORPH algorithm is implemented with the \code{isomorph} | |
640 | function. The vertices of $G_1$ are searched in the order specified by | |
641 | the iterator range \code{[k\_iter,last)}. The function returns true if | |
642 | a isomorphism is found between the vertices of $G_1$ in | |
643 | \code{[k\_iter,last)} and the vertices of $G_2$ in \code{not\_in\_S}. | |
644 | The mapping is recorded in the parameter \code{f}. | |
645 | ||
646 | @d Signature for the recursive isomorph function | |
647 | @{ | |
648 | template <class VertexIter, class EdgeIter, class Graph1, class Graph2, | |
649 | class IndexMap1, class IndexMap2, class IndexMapping, | |
650 | class Invar1, class Invar2, class Set> | |
651 | bool isomorph(VertexIter k_iter, VertexIter last, | |
652 | EdgeIter edge_iter, EdgeIter edge_iter_end, | |
653 | const Graph1& g1, const Graph2& g2, | |
654 | IndexMap1 index_map1, | |
655 | IndexMap2 index_map2, | |
656 | IndexMapping f, Invar1 invar1, Invar2 invar2, | |
657 | const Set& not_in_S) | |
658 | @} | |
659 | ||
660 | \noindent The steps for this function are as follows. | |
661 | ||
662 | @d Body of the isomorph function | |
663 | @{ | |
664 | { | |
665 | @<Some typedefs and variable declarations@> | |
666 | @<Return true if matching is complete@> | |
667 | @<Create a copy of $f_{k-1}$ which will become $f_k$@> | |
668 | @<Compute $M$, the potential matches for $k$@> | |
669 | @<Invoke isomorph for each vertex in $M$@> | |
670 | } | |
671 | @} | |
672 | ||
673 | \noindent Here we create short names for some often-used types | |
674 | and declare some variables. | |
675 | ||
676 | @d Some typedefs and variable declarations | |
677 | @{ | |
678 | typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t; | |
679 | typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t; | |
680 | typedef typename graph_traits<Graph1>::vertices_size_type size_type; | |
681 | ||
682 | vertex1_t k = *k_iter; | |
683 | @} | |
684 | ||
685 | \noindent We have completed creating an isomorphism if \code{k\_iter == last}. | |
686 | ||
687 | @d Return true if matching is complete | |
688 | @{ | |
689 | if (k_iter == last) | |
690 | return true; | |
691 | @} | |
692 | ||
693 | ||
694 | In the pseudo-code for ISOMORPH, we iterate through each vertex in $v | |
695 | \in V_2 - S$ and check if $k$ and $v$ can match. A more efficient | |
696 | approach is to directly iterate through the potential matches for $k$, | |
697 | for this often is many fewer vertices than $V_2 - S$. Let $M$ be the | |
698 | set of potential matches for $k$. $M$ consists of all the vertices $v | |
699 | \in V_2 - S$ such that if $(k,j)$ or $(j,k) \in E_1[k] - E_1[k-1]$ | |
700 | then $(v,f(j)$ or $(f(j),v) \in E_2$ with $i(v) = i(k)$. Note that | |
701 | this means if there are no edges in $E_1[k] - E_1[k-1]$ then $M = V_2 | |
702 | - S$. In the case where there are edges in $E_1[k] - E_1[k-1]$ we | |
703 | break the computation of $M$ into two parts, computing $out$ sets | |
704 | which are vertices that can match according to an out-edge of $k$, and | |
705 | computing $in$ sets which are vertices that can match according to an | |
706 | in-edge of $k$. | |
707 | ||
708 | The implementation consists of a loop through the edges of $E_1[k] - | |
709 | E_1[k-1]$. The straightforward implementation would initialize $M | |
710 | \leftarrow V_2 - S$, and then intersect $M$ with the $out$ or $in$ set | |
711 | for each edge. However, to reduce the cost of the intersection | |
712 | operation, we start with $M \leftarrow \emptyset$, and on the first | |
713 | iteration of the loop we do $M \leftarrow out$ or $M \leftarrow in$ | |
714 | instead of an intersection operation. | |
715 | ||
716 | @d Compute $M$, the potential matches for $k$ | |
717 | @{ | |
718 | std::vector<vertex2_t> potential_matches; | |
719 | bool some_edges = false; | |
720 | ||
721 | for (; edge_iter != edge_iter_end; ++edge_iter) { | |
722 | if (get(index_map1, k) != edge_order(*edge_iter, index_map1, g1)) | |
723 | break; | |
724 | if (k == source(*edge_iter, g1)) { // (k,j) | |
725 | @<Compute the $out$ set@> | |
726 | if (some_edges == false) { | |
727 | @<Perform $M \leftarrow out$@> | |
728 | } else { | |
729 | @<Perform $M \leftarrow M \intersect out$@> | |
730 | } | |
731 | some_edges = true; | |
732 | } else { // (j,k) | |
733 | @<Compute the $in$ set@> | |
734 | if (some_edges == false) { | |
735 | @<Perform $M \leftarrow in$@> | |
736 | } else { | |
737 | @<Perform $M \leftarrow M \intersect in$@> | |
738 | } | |
739 | some_edges = true; | |
740 | } | |
741 | if (potential_matches.empty()) | |
742 | break; | |
743 | } // for edge_iter | |
744 | if (some_edges == false) { | |
745 | @<Perform $M \leftarrow V_2 - S$@> | |
746 | } | |
747 | @} | |
748 | ||
749 | To compute the $out$ set, we iterate through the out-edges $(k,j)$ of | |
750 | $k$, and for each $j$ we iterate through the in-edges $(v,f(j))$ of | |
751 | $f(j)$, putting all of the $v$'s in $out$ that have the same vertex | |
752 | invariant as $k$, and which are in $V_2 - S$. Figure~\ref{fig:out} | |
753 | depicts the computation of the $out$ set. The implementation is as | |
754 | follows. | |
755 | ||
756 | @d Compute the $out$ set | |
757 | @{ | |
758 | vertex1_t j = target(*edge_iter, g1); | |
759 | std::vector<vertex2_t> out; | |
760 | typename graph_traits<Graph2>::in_edge_iterator ei, ei_end; | |
761 | for (tie(ei, ei_end) = in_edges(get(f, j), g2); ei != ei_end; ++ei) { | |
762 | vertex2_t v = source(*ei, g2); // (v,f[j]) | |
763 | if (invar1[k] == invar2[v] && not_in_S[v]) | |
764 | out.push_back(v); | |
765 | } | |
766 | @} | |
767 | ||
768 | \noindent Here initialize $M$ with the $out$ set. Since we are | |
769 | representing sets with sorted vectors, we sort \code{out} before | |
770 | copying to \code{potential\_matches}. | |
771 | ||
772 | @d Perform $M \leftarrow out$ | |
773 | @{ | |
774 | indirect_cmp<IndexMap2,std::less<std::size_t> > cmp(index_map2); | |
775 | std::sort(out.begin(), out.end(), cmp); | |
776 | std::copy(out.begin(), out.end(), std::back_inserter(potential_matches)); | |
777 | @} | |
778 | ||
779 | \noindent We use \code{std::set\_intersection} to implement $M | |
780 | \leftarrow M \intersect out$. Since there is no version of | |
781 | \code{std::set\_intersection} that works in-place, we create a | |
782 | temporary for the result and then swap. | |
783 | ||
784 | @d Perform $M \leftarrow M \intersect out$ | |
785 | @{ | |
786 | indirect_cmp<IndexMap2,std::less<std::size_t> > cmp(index_map2); | |
787 | std::sort(out.begin(), out.end(), cmp); | |
788 | std::vector<vertex2_t> tmp_matches; | |
789 | std::set_intersection(out.begin(), out.end(), | |
790 | potential_matches.begin(), potential_matches.end(), | |
791 | std::back_inserter(tmp_matches), cmp); | |
792 | std::swap(potential_matches, tmp_matches); | |
793 | @} | |
794 | ||
795 | % Shoot, there is some problem with f(j). Could have to do with the | |
796 | % change from the edge set to just using out_edges and in_edges. | |
797 | % Yes, have to visit edges in correct order to we don't hit | |
798 | % part of f that is not yet defined. | |
799 | ||
800 | \vizfig{out}{Computing the $out$ set.} | |
801 | ||
802 | @c out.dot | |
803 | @{ | |
804 | digraph G { | |
805 | node[shape=circle] | |
806 | size="4,2" | |
807 | ratio="fill" | |
808 | ||
809 | subgraph cluster0 { label="G_1" | |
810 | k -> j_1 | |
811 | k -> j_2 | |
812 | k -> j_3 | |
813 | } | |
814 | ||
815 | subgraph cluster1 { label="G_2" | |
816 | ||
817 | subgraph cluster2 { label="out" v_1 v_2 v_3 v_4 v_5 v_6 } | |
818 | ||
819 | v_1 -> fj_1 | |
820 | v_2 -> fj_1 | |
821 | v_3 -> fj_1 | |
822 | ||
823 | v_4 -> fj_2 | |
824 | ||
825 | v_5 -> fj_3 | |
826 | v_6 -> fj_3 | |
827 | ||
828 | fj_1[label="f(j_1)"] | |
829 | fj_2[label="f(j_2)"] | |
830 | fj_3[label="f(j_3)"] | |
831 | } | |
832 | ||
833 | j_1 -> fj_1[style=dotted] | |
834 | j_2 -> fj_2[style=dotted] | |
835 | j_3 -> fj_3[style=dotted] | |
836 | } | |
837 | @} | |
838 | ||
839 | The $in$ set is is constructed by iterating through the in-edges | |
840 | $(j,k)$ of $k$, and for each $j$ we iterate through the out-edges | |
841 | $(f(j),v)$ of $f(j)$. We put all of the $v$'s in $in$ that have the | |
842 | same vertex invariant as $k$, and which are in $V_2 - | |
843 | S$. Figure~\ref{fig:in} depicts the computation of the $in$ set. The | |
844 | following code computes the $in$ set. | |
845 | ||
846 | @d Compute the $in$ set | |
847 | @{ | |
848 | vertex1_t j = source(*edge_iter, g1); | |
849 | std::vector<vertex2_t> in; | |
850 | typename graph_traits<Graph2>::out_edge_iterator ei, ei_end; | |
851 | for (tie(ei, ei_end) = out_edges(get(f, j), g2); ei != ei_end; ++ei) { | |
852 | vertex2_t v = target(*ei, g2); // (f[j],v) | |
853 | if (invar1[k] == invar2[v] && not_in_S[v]) | |
854 | in.push_back(v); | |
855 | } | |
856 | @} | |
857 | ||
858 | \noindent Here initialize $M$ with the $in$ set. Since we are | |
859 | representing sets with sorted vectors, we sort \code{in} before | |
860 | copying to \code{potential\_matches}. | |
861 | ||
862 | @d Perform $M \leftarrow in$ | |
863 | @{ | |
864 | indirect_cmp<IndexMap2,std::less<std::size_t> > cmp(index_map2); | |
865 | std::sort(in.begin(), in.end(), cmp); | |
866 | std::copy(in.begin(), in.end(), std::back_inserter(potential_matches)); | |
867 | @} | |
868 | ||
869 | \noindent Again we use \code{std::set\_intersection} on | |
870 | sorted vectors to implement $M \leftarrow M \intersect in$. | |
871 | ||
872 | @d Perform $M \leftarrow M \intersect in$ | |
873 | @{ | |
874 | indirect_cmp<IndexMap2, std::less<std::size_t> > cmp(index_map2); | |
875 | std::sort(in.begin(), in.end(), cmp); | |
876 | std::vector<vertex2_t> tmp_matches; | |
877 | std::set_intersection(in.begin(), in.end(), | |
878 | potential_matches.begin(), potential_matches.end(), | |
879 | std::back_inserter(tmp_matches), cmp); | |
880 | std::swap(potential_matches, tmp_matches); | |
881 | @} | |
882 | ||
883 | \vizfig{in}{Computing the $in$ set.} | |
884 | ||
885 | @c in.dot | |
886 | @{ | |
887 | digraph G { | |
888 | node[shape=circle] | |
889 | size="3,2" | |
890 | ratio="fill" | |
891 | subgraph cluster0 { label="G1" | |
892 | j_1 -> k | |
893 | j_2 -> k | |
894 | } | |
895 | ||
896 | subgraph cluster1 { label="G2" | |
897 | ||
898 | subgraph cluster2 { label="in" v_1 v_2 v_3 } | |
899 | ||
900 | v_1 -> fj_1 | |
901 | v_2 -> fj_1 | |
902 | ||
903 | v_3 -> fj_2 | |
904 | ||
905 | fj_1[label="f(j_1)"] | |
906 | fj_2[label="f(j_2)"] | |
907 | } | |
908 | ||
909 | j_1 -> fj_1[style=dotted] | |
910 | j_2 -> fj_2[style=dotted] | |
911 | ||
912 | } | |
913 | @} | |
914 | ||
915 | In the case where there were no edges in $E_1[k] - E_1[k-1]$, then $M | |
916 | = V_2 - S$, so here we insert all the vertices from $V_2$ that are not | |
917 | in $S$. | |
918 | ||
919 | @d Perform $M \leftarrow V_2 - S$ | |
920 | @{ | |
921 | typename graph_traits<Graph2>::vertex_iterator vi, vi_end; | |
922 | for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) | |
923 | if (not_in_S[*vi]) | |
924 | potential_matches.push_back(*vi); | |
925 | @} | |
926 | ||
927 | For each vertex $v$ in the potential matches $M$, we will create an | |
928 | extended isomorphism $f_k = f_{k-1} \union \pair{k}{v}$. First | |
929 | we create a local copy of $f_{k-1}$. | |
930 | ||
931 | @d Create a copy of $f_{k-1}$ which will become $f_k$ | |
932 | @{ | |
933 | std::vector<vertex2_t> my_f_vec(num_vertices(g1)); | |
934 | typedef typename std::vector<vertex2_t>::iterator vec_iter; | |
935 | iterator_property_map<vec_iter, IndexMap1, vertex2_t, vertex2_t&> | |
936 | my_f(my_f_vec.begin(), index_map1); | |
937 | ||
938 | typename graph_traits<Graph1>::vertex_iterator i1, i1_end; | |
939 | for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1) | |
940 | my_f[*i1] = get(f, *i1); | |
941 | @} | |
942 | ||
943 | Next we enter the loop through every vertex $v$ in $M$, and extend the | |
944 | isomorphism with $\pair{k}{v}$. We then update the set $S$ (by | |
945 | removing $v$ from $V_2 - S$) and make the recursive call to | |
946 | \code{isomorph}. If \code{isomorph} returns successfully, we have | |
947 | found an isomorphism for the complete graph, so we copy our local | |
948 | mapping into the mapping from the previous calling function. | |
949 | ||
950 | @d Invoke isomorph for each vertex in $M$ | |
951 | @{ | |
952 | for (std::size_t j = 0; j < potential_matches.size(); ++j) { | |
953 | my_f[k] = potential_matches[j]; | |
954 | @<Perform $S' = S - \{ v \}$@> | |
955 | if (isomorph(boost::next(k_iter), last, edge_iter, edge_iter_end, g1, g2, | |
956 | index_map1, index_map2, | |
957 | my_f, invar1, invar2, my_not_in_S)) { | |
958 | for (tie(i1, i1_end) = vertices(g1); i1 != i1_end; ++i1) | |
959 | put(f, *i1, my_f[*i1]); | |
960 | return true; | |
961 | } | |
962 | } | |
963 | return false; | |
964 | @} | |
965 | ||
966 | We need to create the new set $S' = S - \{ v \}$, which will be the | |
967 | $S$ for the next invocation to \code{isomorph}. As before, we | |
968 | represent $V_2 - S'$ instead of $S'$ and use a bitset. | |
969 | ||
970 | @d Perform $S' = S - \{ v \}$ | |
971 | @{ | |
972 | std::vector<char> my_not_in_S_vec(num_vertices(g2)); | |
973 | iterator_property_map<char*, IndexMap2, char, char&> | |
974 | my_not_in_S(&my_not_in_S_vec[0], index_map2); | |
975 | typename graph_traits<Graph2>::vertex_iterator vi, vi_end; | |
976 | for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) | |
977 | my_not_in_S[*vi] = not_in_S[*vi];; | |
978 | my_not_in_S[potential_matches[j]] = false; | |
979 | @} | |
980 | ||
981 | ||
982 | \section{Appendix} | |
983 | ||
984 | Here we output the header file \code{isomorphism.hpp}. We add a | |
985 | copyright statement, include some files, and then pull the top-level | |
986 | code parts into namespace \code{boost}. | |
987 | ||
988 | @o isomorphism.hpp -d | |
989 | @{ | |
990 | ||
991 | // (C) Copyright Jeremy Siek 2001. Permission to copy, use, modify, | |
992 | // sell and distribute this software is granted provided this | |
993 | // copyright notice appears in all copies. This software is provided | |
994 | // "as is" without express or implied warranty, and with no claim as | |
995 | // to its suitability for any purpose. | |
996 | ||
997 | // See http://www.boost.org/libs/graph/doc/isomorphism-impl.pdf | |
998 | // for a description of the implementation of the isomorphism function | |
999 | // defined in this header file. | |
1000 | ||
1001 | #ifndef BOOST_GRAPH_ISOMORPHISM_HPP | |
1002 | #define BOOST_GRAPH_ISOMORPHISM_HPP | |
1003 | ||
1004 | #include <algorithm> | |
1005 | #include <boost/graph/detail/set_adaptor.hpp> | |
1006 | #include <boost/pending/indirect_cmp.hpp> | |
1007 | #include <boost/graph/detail/permutation.hpp> | |
1008 | #include <boost/graph/named_function_params.hpp> | |
1009 | #include <boost/graph/graph_concepts.hpp> | |
1010 | #include <boost/property_map/property_map.hpp> | |
1011 | #include <boost/pending/integer_range.hpp> | |
1012 | #include <boost/limits.hpp> | |
1013 | #include <boost/static_assert.hpp> | |
1014 | #include <boost/graph/depth_first_search.hpp> | |
1015 | ||
1016 | namespace boost { | |
1017 | ||
1018 | @<Degree vertex invariant@> | |
1019 | ||
1020 | namespace detail { | |
1021 | @<Signature for the recursive isomorph function@> | |
1022 | @<Body of the isomorph function@> | |
1023 | } // namespace detail | |
1024 | ||
1025 | @<Record DFS ordering visitor@> | |
1026 | @<Compare multiplicity predicate@> | |
1027 | @<Isomorph edge ordering predicate@> | |
1028 | ||
1029 | @<Isomorphism Function Interface@> | |
1030 | @<Isomorphism Function Body@> | |
1031 | ||
1032 | namespace detail { | |
1033 | // Should move this, make is public | |
1034 | template <typename Graph, typename InDegreeMap, typename Cat> | |
1035 | void compute_in_degree(const Graph& g, const InDegreeMap& in_degree_map, | |
1036 | Cat) | |
1037 | { | |
1038 | typename graph_traits<Graph>::vertex_iterator vi, vi_end; | |
1039 | typename graph_traits<Graph>::out_edge_iterator ei, ei_end; | |
1040 | for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) | |
1041 | for (tie(ei, ei_end) = out_edges(*vi, g); ei != ei_end; ++ei) { | |
1042 | typename graph_traits<Graph>::vertex_descriptor v = target(*ei, g); | |
1043 | put(in_degree_map, v, get(in_degree_map, v) + 1); | |
1044 | } | |
1045 | } | |
1046 | template <typename Graph, typename InDegreeMap> | |
1047 | void compute_in_degree(const Graph& g, const InDegreeMap& in_degree_map, | |
1048 | edge_list_graph_tag) | |
1049 | { | |
1050 | typename graph_traits<Graph>::edge_iterator ei, ei_end; | |
1051 | for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { | |
1052 | typename graph_traits<Graph>::vertex_descriptor v = target(*ei, g); | |
1053 | put(in_degree_map, v, get(in_degree_map, v) + 1); | |
1054 | } | |
1055 | } | |
1056 | template <typename Graph, typename InDegreeMap> | |
1057 | void compute_in_degree(const Graph& g, const InDegreeMap& in_degree_map) | |
1058 | { | |
1059 | typename graph_traits<Graph>::traversal_category cat; | |
1060 | compute_in_degree(g, in_degree_map, cat); | |
1061 | } | |
1062 | ||
1063 | ||
1064 | template <typename Graph1, typename Graph2, | |
1065 | typename IndexMapping, typename IndexMap1, typename IndexMap2, | |
1066 | typename P, typename T, typename R> | |
1067 | bool isomorphism_impl(const Graph1& g1, const Graph2& g2, | |
1068 | IndexMapping f, | |
1069 | IndexMap1 index_map1, IndexMap2 index_map2, | |
1070 | const bgl_named_params<P,T,R>& params) | |
1071 | { | |
1072 | typedef typename graph_traits<Graph1>::vertices_size_type size_type; | |
1073 | ||
1074 | // Compute the in-degrees | |
1075 | std::vector<size_type> in_degree_vec1(num_vertices(g1), 0); | |
1076 | typedef iterator_property_map<size_type*, IndexMap1, | |
1077 | size_type, size_type&> InDegreeMap1; | |
1078 | InDegreeMap1 in_degree_map1(&in_degree_vec1[0], index_map1); | |
1079 | detail::compute_in_degree(g1, in_degree_map1); | |
1080 | degree_vertex_invariant<InDegreeMap1, Graph1> | |
1081 | default_invar1(in_degree_map1, g1); | |
1082 | ||
1083 | std::vector<size_type> in_degree_vec2(num_vertices(g2), 0); | |
1084 | typedef iterator_property_map<size_type*, IndexMap2, | |
1085 | size_type, size_type&> InDegreeMap2; | |
1086 | InDegreeMap2 in_degree_map2(&in_degree_vec2[0], index_map2); | |
1087 | detail::compute_in_degree(g2, in_degree_map2); | |
1088 | degree_vertex_invariant<InDegreeMap2, Graph2> | |
1089 | default_invar2(in_degree_map2, g2); | |
1090 | ||
1091 | return isomorphism(g1, g2, f, | |
1092 | choose_param(get_param(params, vertex_invariant_t()), default_invar1), | |
1093 | choose_param(get_param(params, vertex_invariant_t()), default_invar2), | |
1094 | index_map1, index_map2); | |
1095 | } | |
1096 | ||
1097 | } // namespace detail | |
1098 | ||
1099 | // Named parameter interface | |
1100 | template <typename Graph1, typename Graph2, class P, class T, class R> | |
1101 | bool isomorphism(const Graph1& g1, | |
1102 | const Graph2& g2, | |
1103 | const bgl_named_params<P,T,R>& params) | |
1104 | { | |
1105 | typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t; | |
1106 | typename std::vector<vertex2_t>::size_type | |
1107 | n = is_default_param(get_param(params, vertex_isomorphism_t())) | |
1108 | ? num_vertices(g1) : 1; | |
1109 | std::vector<vertex2_t> f(n); | |
1110 | vertex2_t x; | |
1111 | return detail::isomorphism_impl | |
1112 | (g1, g2, | |
1113 | choose_param(get_param(params, vertex_isomorphism_t()), | |
1114 | make_iterator_property_map(f.begin(), | |
1115 | choose_const_pmap(get_param(params, vertex_index1), | |
1116 | g1, vertex_index), x)), | |
1117 | choose_const_pmap(get_param(params, vertex_index1), | |
1118 | g1, vertex_index), | |
1119 | choose_const_pmap(get_param(params, vertex_index2), | |
1120 | g2, vertex_index), | |
1121 | params); | |
1122 | } | |
1123 | ||
1124 | // All defaults interface | |
1125 | template <typename Graph1, typename Graph2> | |
1126 | bool isomorphism(const Graph1& g1, const Graph2& g2) | |
1127 | { | |
1128 | typedef typename graph_traits<Graph1>::vertices_size_type size_type; | |
1129 | typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t; | |
1130 | std::vector<vertex2_t> f(num_vertices(g1)); | |
1131 | ||
1132 | // Compute the in-degrees | |
1133 | std::vector<size_type> in_degree_vec1(num_vertices(g1), 0); | |
1134 | typedef typename property_map<Graph1,vertex_index_t>::const_type IndexMap1; | |
1135 | typedef iterator_property_map<size_type*, IndexMap1, | |
1136 | size_type, size_type&> InDegreeMap1; | |
1137 | InDegreeMap1 in_degree_map1(&in_degree_vec1[0], get(vertex_index, g1)); | |
1138 | detail::compute_in_degree(g1, in_degree_map1); | |
1139 | degree_vertex_invariant<InDegreeMap1, Graph1> | |
1140 | invariant1(in_degree_map, g1); | |
1141 | ||
1142 | std::vector<size_type> in_degree_vec2(num_vertices(g2), 0); | |
1143 | typedef typename property_map<Graph2,vertex_index_t>::const_type IndexMap2; | |
1144 | typedef iterator_property_map<size_type*, IndexMap2, | |
1145 | size_type, size_type&> InDegreeMap2; | |
1146 | InDegreeMap2 in_degree_map2(&in_degree_vec2[0], get(vertex_index, g2)); | |
1147 | detail::compute_in_degree(g2, in_degree_map2); | |
1148 | degree_vertex_invariant<InDegreeMap2, Graph2> | |
1149 | invariant2(in_degree_map, g2); | |
1150 | ||
1151 | return isomorphism | |
1152 | (g1, g2, make_iterator_property_map(f.begin(), get(vertex_index, g1), vertex2_t()), | |
1153 | invariant1, invariant2, get(vertex_index, g1), get(vertex_index, g2)); | |
1154 | } | |
1155 | ||
1156 | // Verify that the given mapping iso_map from the vertices of g1 to the | |
1157 | // vertices of g2 describes an isomorphism. | |
1158 | // Note: this could be made much faster by specializing based on the graph | |
1159 | // concepts modeled, but since we're verifying an O(n^(lg n)) algorithm, | |
1160 | // O(n^4) won't hurt us. | |
1161 | template<typename Graph1, typename Graph2, typename IsoMap> | |
1162 | inline bool verify_isomorphism(const Graph1& g1, const Graph2& g2, | |
1163 | IsoMap iso_map) | |
1164 | { | |
1165 | if (num_vertices(g1) != num_vertices(g2) || num_edges(g1) != num_edges(g2)) | |
1166 | return false; | |
1167 | ||
1168 | for (typename graph_traits<Graph1>::edge_iterator e1 = edges(g1).first; | |
1169 | e1 != edges(g1).second; ++e1) { | |
1170 | bool found_edge = false; | |
1171 | for (typename graph_traits<Graph2>::edge_iterator e2 = edges(g2).first; | |
1172 | e2 != edges(g2).second && !found_edge; ++e2) { | |
1173 | if (source(*e2, g2) == get(iso_map, source(*e1, g1)) && | |
1174 | target(*e2, g2) == get(iso_map, target(*e1, g1))) { | |
1175 | found_edge = true; | |
1176 | } | |
1177 | } | |
1178 | ||
1179 | if (!found_edge) | |
1180 | return false; | |
1181 | } | |
1182 | ||
1183 | return true; | |
1184 | } | |
1185 | ||
1186 | } // namespace boost | |
1187 | ||
1188 | #endif // BOOST_GRAPH_ISOMORPHISM_HPP | |
1189 | @} | |
1190 | ||
1191 | \bibliographystyle{abbrv} | |
1192 | \bibliography{ggcl} | |
1193 | ||
1194 | \end{document} | |
1195 | % LocalWords: Isomorphism Siek isomorphism adjacency subgraph subgraphs OM DFS | |
1196 | % LocalWords: ISOMORPH Invariants invariants typename IndexMapping bool const | |
1197 | % LocalWords: VertexInvariant VertexIndexMap iterator typedef VertexG Idx num | |
1198 | % LocalWords: InvarValue struct invar vec iter tmp_matches mult inserter permute ui | |
1199 | % LocalWords: dfs cmp isomorph VertexIter EdgeIter IndexMap desc RPH ATCH pre | |
1200 | ||
1201 | % LocalWords: iterators VertexListGraph EdgeListGraph BidirectionalGraph tmp | |
1202 | % LocalWords: ReadWritePropertyMap VertexListGraphConcept EdgeListGraphConcept | |
1203 | % LocalWords: BidirectionalGraphConcept ReadWritePropertyMapConcept indices ei | |
1204 | % LocalWords: IndexMappingValue ReadablePropertyMapConcept namespace InvarMap | |
1205 | % LocalWords: MultMap vip inline bitset typedefs fj hpp ifndef adaptor params | |
1206 | % LocalWords: bgl param pmap endif |