1 \documentclass[11pt]{report}
12 \ifx\pdfoutput\undefined
22 colorlinks=true, %change to true for the electronic version
23 linkcolor=blue,filecolor=blue,pagecolor=blue,urlcolor=blue
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}}
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}}
41 \newcommand{\code}[1]{{\small{\em \textbf{#1}}}}
44 \newcommand{\isomorphic}{\cong}
48 \title{An Implementation of Isomorphism Testing}
49 \author{Jeremy G. Siek}
53 \section{Introduction}
55 This paper documents the implementation of the \code{isomorphism()}
56 function of the Boost Graph Library. The implementation was by Jeremy
57 Siek with algorithmic improvements and test code from Douglas Gregor
58 and Brian Osman. The \code{isomorphism()} function answers the
59 question, ``are these two graphs equal?'' By \emph{equal} we mean
60 the two graphs have the same structure---the vertices and edges are
61 connected in the same way. The mathematical name for this kind of
62 equality is \emph{isomorphism}.
64 More precisely, an \emph{isomorphism} is a one-to-one mapping of the
65 vertices in one graph to the vertices of another graph such that
66 adjacency is preserved. Another words, given graphs $G_{1} =
67 (V_{1},E_{1})$ and $G_{2} = (V_{2},E_{2})$, an isomorphism is a
68 function $f$ such that for all pairs of vertices $a,b$ in $V_{1}$,
69 edge $(a,b)$ is in $E_{1}$ if and only if edge $(f(a),f(b))$ is in
72 Both graphs must be the same size, so let $N = |V_1| = |V_2|$. The
73 graph $G_1$ is \emph{isomorphic} to $G_2$ if an isomorphism exists
74 between the two graphs, which we denote by $G_1 \isomorphic G_2$.
76 In the following discussion we will need to use several notions from
77 graph theory. The graph $G_s=(V_s,E_s)$ is a \emph{subgraph} of graph
78 $G=(V,E)$ if $V_s \subseteq V$ and $E_s \subseteq E$. An
79 \emph{induced subgraph}, denoted by $G[V_s]$, of a graph $G=(V,E)$
80 consists of the vertices in $V_s$, which is a subset of $V$, and every
81 edge $(u,v)$ in $E$ such that both $u$ and $v$ are in $V_s$. We use
82 the notation $E[V_s]$ to mean the edges in $G[V_s]$.
84 In some places we express a function as a set of pairs, so the set $f
85 = \{ \pair{a_1}{b_1}, \ldots, \pair{a_n}{b_n} \}$
86 means $f(a_i) = b_i$ for $i=1,\ldots,n$.
88 \section{Exhaustive Backtracking Search}
89 \label{sec:backtracking}
91 The algorithm used by the \code{isomorphism()} function is, at
92 first approximation, an exhaustive search implemented via
93 backtracking. The backtracking algorithm is a recursive function. At
94 each stage we will try to extend the match that we have found so far.
95 So suppose that we have already determined that some subgraph of $G_1$
96 is isomorphic to a subgraph of $G_2$. We then try to add a vertex to
97 each subgraph such that the new subgraphs are still isomorphic to one
98 another. At some point we may hit a dead end---there are no vertices
99 that can be added to extend the isomorphic subgraphs. We then
100 backtrack to previous smaller matching subgraphs, and try extending
101 with a different vertex choice. The process ends by either finding a
102 complete mapping between $G_1$ and $G_2$ and return true, or by
103 exhausting all possibilities and returning false.
105 We consider the vertices of $G_1$ for addition to the matched subgraph
106 in a specific order, so assume that the vertices of $G_1$ are labeled
107 $1,\ldots,N$ according to that order. As we will see later, a good
108 ordering of the vertices is by DFS discover time. Let $G_1[k]$ denote
109 the subgraph of $G_1$ induced by the first $k$ vertices, with $G_1[0]$
110 being an empty graph. We also consider the edges of $G_1$ in a
111 specific order. We always examine edges in the current subgraph
112 $G_1[k]$ first, that is, edges $(u,v)$ where both $u \leq k$ and $v
113 \leq k$. This ordering of edges can be acheived by sorting the edges
114 according to number of the larger of the source and target vertex.
116 Each step of the backtracking search examines an edge $(u,v)$ of $G_1$
117 and decides whether to continue or go back. There are three cases to
122 \item $i \leq k \Land j \leq k$. Both $i$ and $j$ are in $G_1[k]$. We
123 check to make sure the $(f(i),f(j)) \in E_2[S]$.
125 \item $i \leq k \Land j > k$. $i$ is in the matched subgraph $G_1[k]$,
126 but $j$ is not. We are about to increment $k$ try to grow the matched
127 subgraph to include $j$. However, first we need to finalize our check
128 of the isomorphism between subgraphs $G_1[k]$ and $G_2[S]$. At this
129 point we are guaranteed to have seen all the edges to and from vertex $k$
130 (because the edges are sorted), and in previous steps we have checked
131 that for each edge incident on $k$ in $G_1[k]$ there is a matching
132 edge in $G_2[S]$. However we have not checked that for each edge
133 incident on $f(k)$ in $E_2[S]$, there is a matching edge in $E_1[k]$
134 (we need to check the ``only if'' part of the ``if and only if'').
135 Therefore we scan through all the edges $(u,v)$ incident on $f(k)$ and
136 make sure that $(f^{-1}(u),f^{-1}(v)) \in E_1[k]$. Once this check has
137 been performed, we add $f(k)$ to $S$, we increment $k$ (so now $k=j$),
138 and then try assigning the new $k$ to any of the eligible vertices in
139 $V_2 - S$. More about what ``eligible'' means later.
141 \item $i > k \Land j \leq k$. This case will not occur due to the DFS
142 numbering of the vertices. There is an edge $(i,j)$ so $i$ must be
145 \item $i > k \Land j > k$. Neither $i$ or $j$ is in the matched
146 subgraph $G_1[k]$. This situation only happens at the very beginning
147 of the search, or when $i$ and $j$ are not reachable from any of the
148 vertices in $G_1[k]$. This means the smaller of $i$ and $j$ must be
149 the root of a DFS tree. We assign $r$ to any of the eligible vertices
150 in $V_2 - S$, and then proceed as if we were in Case 2.
158 bool match(edge_iter iter)
160 if (iter != ordered_edges.end()) {
161 ordered_edge edge = *iter;
162 size_type k_num = edge.k_num;
163 vertex1_t k = dfs_vertices[k_num];
165 if (edge.source != -1) // might be a ficticious edge
166 u = dfs_vertices[edge.source];
167 vertex1_t v = dfs_vertices[edge.target];
168 if (edge.source == -1) { // root node
169 @<$v$ is a DFS tree root@>
170 } else if (f_assigned[v] == false) {
171 @<$v$ is an unmatched vertex, $(u,v)$ is a tree edge@>
173 @<Check to see if there is an edge in $G_2$ to match $(u,v)$@>
186 The basic idea will be to examine $G_1$ one edge at a time, trying to
187 create a vertex mapping such that each edge matches one in $G_2$. We
188 are going to consider the edges of $G_1$ in a specific order, so we
189 will label the edges $0,\ldots,|E_1|-1$.
191 At each stage of the recursion we
192 start with an isomorphism $f_{k-1}$ between $G_1[k-1]$ and a subgraph
193 of $G_2$, which we denote by $G_2[S]$, so $G_1[k-1] \isomorphic
194 G_2[S]$. The vertex set $S$ is the subset of $V_2$ that corresponds
195 via $f_{k-1}$ to the first $k-1$ vertices in $G_1$.
197 We also order the edges of $G_1$
201 We try to extend the isomorphism by finding a vertex $v \in V_2 - S$
202 that matches with vertex $k$. If a matching vertex is found, we have a
203 new isomorphism $f_k$ with $G_1[k] \isomorphic G_2[S \union \{ v \}]$.
209 IS\=O\=M\=O\=RPH($k$, $S$, $f_{k-1}$) $\equiv$ \\
210 \>\textbf{if} ($k = |V_1|+1$) \\
211 \>\>\textbf{return} true \\
212 \>\textbf{for} each vertex $v \in V_2 - S$ \\
213 \>\>\textbf{if} (MATCH($k$, $v$)) \\
214 \>\>\>$f_k = f_{k-1} \union \pair{k}{v}$ \\
215 \>\>\>ISOMORPH($k+1$, $S \union \{ v \}$, $f_k$)\\
217 \>\>\>\textbf{return} false \\
219 ISOMORPH($0$, $G_1$, $\emptyset$, $G_2$)
222 The basic idea of the match operation is to check whether $G_1[k]$ is
223 isomorphic to $G_2[S \union \{ v \}]$. We already know that $G_1[k-1]
224 \isomorphic G_2[S]$ with the mapping $f_{k-1}$, so all we need to do
225 is verify that the edges in $E_1[k] - E_1[k-1]$ connect vertices that
226 correspond to the vertices connected by the edges in $E_2[S \union \{
227 v \}] - E_2[S]$. The edges in $E_1[k] - E_1[k-1]$ are all the
228 out-edges $(k,j)$ and in-edges $(j,k)$ of $k$ where $j$ is less than
229 or equal to $k$ according to the ordering. The edges in $E_2[S \union
230 \{ v \}] - E_2[S]$ consists of all the out-edges $(v,u)$ and
231 in-edges $(u,v)$ of $v$ where $u \in S$.
234 M\=ATCH($k$, $v$) $\equiv$ \\
235 \>$out_k \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)$ \\
236 \>$in_k \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)$ \\
237 \>$out_v \leftarrow \forall (v,u) \in E_2[S \union \{ v \}] - E_2[S] \Big( (k,f^{-1}(u)) \in E_1[k] - E_1[k-1] \Big)$ \\
238 \>$in_v \leftarrow \forall (u,v) \in E_2[S \union \{ v \}] - E_2[S] \Big( (f^{-1}(u),k) \in E_1[k] - E_1[k-1] \Big)$ \\
239 \>\textbf{return} $out_k \Land in_k \Land out_v \Land in_v$
242 The problem with the exhaustive backtracking algorithm is that there
243 are $N!$ possible vertex mappings, and $N!$ gets very large as $N$
244 increases, so we need to prune the search space. We use the pruning
245 techniques described in
246 \cite{deo77:_new_algo_digraph_isomorph,fortin96:_isomorph,reingold77:_combin_algo}
248 \cite{sussenguth65:_isomorphism,unger64:_isomorphism}.
250 \section{Vertex Invariants}
251 \label{sec:vertex-invariants}
253 One way to reduce the search space is through the use of \emph{vertex
254 invariants}. The idea is to compute a number for each vertex $i(v)$
255 such that $i(v) = i(v')$ if there exists some isomorphism $f$ where
256 $f(v) = v'$. Then when we look for a match to some vertex $v$, we only
257 need to consider those vertices that have the same vertex invariant
258 number. The number of vertices in a graph with the same vertex
259 invariant number $i$ is called the \emph{invariant multiplicity} for
260 $i$. In this implementation, by default we use the out-degree of the
261 vertex as the vertex invariant, though the user can also supply there
262 own invariant function. The ability of the invariant function to prune
263 the search space varies widely with the type of graph.
265 As a first check to rule out graphs that have no possibility of
266 matching, one can create a list of computed vertex invariant numbers
267 for the vertices in each graph, sort the two lists, and then compare
268 them. If the two lists are different then the two graphs are not
269 isomorphic. If the two lists are the same then the two graphs may be
272 Also, we extend the MATCH operation to use the vertex invariants to
273 help rule out vertices.
275 \section{Vertex Order}
277 A good choice of the labeling for the vertices (which determines the
278 order in which the subgraph $G_1[k]$ is grown) can also reduce the
279 search space. In the following we discuss two labeling heuristics.
281 \subsection{Most Constrained First}
283 Consider the most constrained vertices first. That is, examine
284 lower-degree vertices before higher-degree vertices. This reduces the
285 search space because it chops off a trunk before the trunk has a
286 chance to blossom out. We can generalize this to use vertex
287 invariants. We examine vertices with low invariant multiplicity
288 before examining vertices with high invariant multiplicity.
290 \subsection{Adjacent First}
292 The MATCH operation only considers edges when the other vertex already
293 has a mapping defined. This means that the MATCH operation can only
294 weed out vertices that are adjacent to vertices that have already been
295 matched. Therefore, when choosing the next vertex to examine, it is
296 desirable to choose one that is adjacent a vertex already in $S_1$.
298 \subsection{DFS Order, Starting with Lowest Multiplicity}
300 For this implementation, we combine the above two heuristics in the
301 following way. To implement the ``adjacent first'' heuristic we apply
302 DFS to the graph, and use the DFS discovery order as our vertex
303 order. To comply with the ``most constrained first'' heuristic we
304 order the roots of our DFS trees by invariant multiplicity.
308 \section{Implementation}
310 The following is the public interface for the \code{isomorphism}
311 function. The input to the function is the two graphs $G_1$ and $G_2$,
312 mappings from the vertices in the graphs to integers (in the range
313 $[0,|V|)$), and a vertex invariant function object. The output of the
314 function is an isomorphism $f$ if there is one. The \code{isomorphism}
315 function returns true if the graphs are isomorphic and false
316 otherwise. The invariant parameters are function objects that compute
317 the vertex invariants for vertices of the two graphs. The
318 \code{max\_invariant} parameter is to specify one past the largest
319 integer that a vertex invariant number could be (the invariants
320 numbers are assumed to span from zero to the number). The
321 requirements on type template parameters are described below in the
322 ``Concept checking'' part.
325 @d Isomorphism function interface
327 template <typename Graph1, typename Graph2, typename IsoMapping,
328 typename Invariant1, typename Invariant2,
329 typename IndexMap1, typename IndexMap2>
330 bool isomorphism(const Graph1& G1, const Graph2& G2, IsoMapping f,
331 Invariant1 invariant1, Invariant2 invariant2,
332 std::size_t max_invariant,
333 IndexMap1 index_map1, IndexMap2 index_map2)
337 The function body consists of the concept checks followed by a quick
338 check for empty graphs or graphs of different size and then construct
339 an algorithm object. We then call the \code{test\_isomorphism} member
340 function, which runs the algorithm. The reason that we implement the
341 algorithm using a class is that there are a fair number of internal
342 data structures required, and it is easier to make these data members
343 of a class and make each section of the algorithm a member
344 function. This relieves us from the burden of passing lots of
345 arguments to each function, while at the same time avoiding the evils
346 of global variables (non-reentrant, etc.).
349 @d Isomorphism function body
353 @<Quick return based on size@>
354 detail::isomorphism_algo<Graph1, Graph2, IsoMapping, Invariant1, Invariant2,
355 IndexMap1, IndexMap2>
356 algo(G1, G2, f, invariant1, invariant2, max_invariant,
357 index_map1, index_map2);
358 return algo.test_isomorphism();
363 \noindent If there are no vertices in either graph, then they are
364 trivially isomorphic. If the graphs have different numbers of vertices
365 then they are not isomorphic.
367 @d Quick return based on size
369 if (num_vertices(G1) != num_vertices(G2))
371 if (num_vertices(G1) == 0 && num_vertices(G2) == 0)
375 We use the Boost Concept Checking Library to make sure that the type
376 arguments to the function fulfill there requirements. The graph types
377 must model the \bglconcept{VertexListGraph} and
378 \bglconcept{AdjacencyGraph} concepts. The vertex invariants must model
379 the \stlconcept{AdaptableUnaryFunction} concept, with a vertex as
380 their argument and an integer return type. The \code{IsoMapping} type
381 that represents the isomorphism $f$ must be a
382 \pmconcept{ReadWritePropertyMap} that maps from vertices in $G_1$ to
383 vertices in $G_2$. The two other index maps are
384 \pmconcept{ReadablePropertyMap}s from vertices in $G_1$ and $G_2$ to
390 // Graph requirements
391 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph1> ));
392 BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> ));
393 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph2> ));
394 BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph2> ));
396 typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t;
397 typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
398 typedef typename graph_traits<Graph1>::vertices_size_type size_type;
400 // Vertex invariant requirement
401 BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Invariant1,
402 size_type, vertex1_t> ));
403 BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Invariant2,
404 size_type, vertex2_t> ));
406 // Property map requirements
407 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<IsoMapping, vertex1_t> ));
408 typedef typename property_traits<IsoMapping>::value_type IsoMappingValue;
409 BOOST_STATIC_ASSERT((is_same<IsoMappingValue, vertex2_t>::value));
411 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap1, vertex1_t> ));
412 typedef typename property_traits<IndexMap1>::value_type IndexMap1Value;
413 BOOST_STATIC_ASSERT((is_convertible<IndexMap1Value, size_type>::value));
415 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap2, vertex2_t> ));
416 typedef typename property_traits<IndexMap2>::value_type IndexMap2Value;
417 BOOST_STATIC_ASSERT((is_convertible<IndexMap2Value, size_type>::value));
420 The following is the outline of the isomorphism algorithm class. The
421 class is templated on all of the same parameters of the
422 \code{isomorphism} function, and all of the parameter values are
423 stored in the class as data members, in addition to the internal data
426 @d Isomorphism algorithm class
428 template <typename Graph1, typename Graph2, typename IsoMapping,
429 typename Invariant1, typename Invariant2,
430 typename IndexMap1, typename IndexMap2>
431 class isomorphism_algo
433 @<Typedefs for commonly used types@>
434 @<Data members for the parameters@>
435 @<Ordered edge class@>
436 @<Internal data structures@>
437 friend struct compare_multiplicity;
438 @<Invariant multiplicity comparison functor@>
439 @<DFS visitor to record vertex and edge order@>
441 @<Isomorphism algorithm constructor@>
442 @<Test isomorphism member function@>
448 The interesting parts of this class are the \code{test\_isomorphism}
449 function, and the \code{match} function. We focus on those in in the
450 following sections, and mention the other parts of the class when
451 needed (and a few are left to the appendix).
453 The \code{test\_isomorphism} function does all of the setup required
454 of the algorithm. This consists of sorting the vertices according to
455 invariant multiplicity, and then by DFS order. The edges are then
456 sorted by the DFS order of vertices incident on the edges. More
457 details about this to come. The last step of this function is to
458 invoke the recursive \code{match} function which performs the
462 @d Test isomorphism member function
464 bool test_isomorphism()
466 @<Quick return if the vertex invariants do not match up@>
467 @<Sort vertices according to invariant multiplicity@>
468 @<Order vertices and edges by DFS@>
469 @<Sort edges according to vertex DFS order@>
471 return this->match(ordered_edges.begin());
475 As discussed in \S\ref{sec:vertex-invariants}, we can quickly rule out
476 the possibility of any isomorphism between two graphs by checking to
477 see if the vertex invariants can match up. We sort both vectors of vertex
478 invariants, and then check to see if they are equal.
480 @d Quick return if the vertex invariants do not match up
483 std::vector<invar1_value> invar1_array;
484 BGL_FORALL_VERTICES_T(v, G1, Graph1)
485 invar1_array.push_back(invariant1(v));
486 std::sort(invar1_array.begin(), invar1_array.end());
488 std::vector<invar2_value> invar2_array;
489 BGL_FORALL_VERTICES_T(v, G2, Graph2)
490 invar2_array.push_back(invariant2(v));
491 std::sort(invar2_array.begin(), invar2_array.end());
493 if (!std::equal(invar1_array.begin(), invar1_array.end(), invar2_array.begin()))
498 Next we compute the invariant multiplicity, the number of vertices
499 with the same invariant number. The \code{invar\_mult} vector is
500 indexed by invariant number. We loop through all the vertices in the
501 graph to record the multiplicity. We then order the vertices by their
502 invariant multiplicity. This will allow us to search the more
503 constrained vertices first.
505 @d Sort vertices according to invariant multiplicity
507 std::vector<vertex1_t> V_mult;
508 BGL_FORALL_VERTICES_T(v, G1, Graph1)
511 std::vector<size_type> multiplicity(max_invariant, 0);
512 BGL_FORALL_VERTICES_T(v, G1, Graph1)
513 ++multiplicity[invariant1(v)];
515 std::sort(V_mult.begin(), V_mult.end(), compare_multiplicity(*this, &multiplicity[0]));
519 \noindent The definition of the \code{compare\_multiplicity} predicate
520 is shown below. This predicate provides the glue that binds
521 \code{std::sort} to our current purpose.
523 @d Invariant multiplicity comparison functor
525 struct compare_multiplicity
527 compare_multiplicity(isomorphism_algo& algo, size_type* multiplicity)
528 : algo(algo), multiplicity(multiplicity) { }
529 bool operator()(const vertex1_t& x, const vertex1_t& y) const {
530 return multiplicity[algo.invariant1(x)] < multiplicity[algo.invariant1(y)];
532 isomorphism_algo& algo;
533 size_type* multiplicity;
537 \subsection{Backtracking Search and Matching}
544 \subsection{Ordering by DFS Discover Time}
546 To implement the ``visit adjacent vertices first'' heuristic, we order
547 the vertices according to DFS discover time. This will give us the
548 order that the subgraph $G_1[k]$ will be expanded. As described in
549 \S\ref{sec:backtracking}, when trying to match $k$ with some vertex
550 $v$ in $V_2 - S$, we need to examine the edges in $E_1[k] -
551 E_1[k-1]$. It would be nice if we had the edges of $G_1$ arranged so
552 that when we are interested in vertex $k$, the edges in $E_1[k] -
553 E_1[k-1]$ are easy to find. This can be achieved by creating an array
554 of edges sorted by the DFS number of the larger of the source and
555 target vertex. The following array of ordered edges corresponds
556 to the graph in Figure~\ref{fig:edge-order}.
558 \begin{tabular}{cccccccccc}
559 &0&1&2&3&4&5&6&7&8\\ \hline
560 source&0&1&1&3&3&4&4&5&6\\
561 target&1&2&3&1&2&3&5&6&4
564 The backtracking algorithm will scan through the edge array from left
565 to right to extend isomorphic subgraphs, and move back to the right
566 when a match fails. We will want to
577 For example, suppose we have already matched the vertices
582 \vizfig{edge-order}{Vertices with DFS numbering. The DFS trees are the solid edges.}
605 We implement the outer-loop of the DFS here, instead of calling the
606 \code{depth\_first\_search} function, because we want the roots of the
607 DFS tree's to be ordered by invariant multiplicity. We call
608 \code{depth\_\-first\_\-visit} to implement the recursive portion of
609 the DFS. The \code{record\_dfs\_order} adapts the DFS to record the
610 order in which DFS discovers the vertices, storing the results in in
611 the \code{dfs\_vertices} and \code{ordered\_edges} arrays. We then
612 create the \code{dfs\_number} array which provides a mapping from
613 vertex to DFS number, and renumber the edges with the DFS numbers.
615 @d Order vertices and edges by DFS
617 std::vector<default_color_type> color_vec(num_vertices(G1));
618 safe_iterator_property_map<std::vector<default_color_type>::iterator, IndexMap1>
619 color_map(color_vec.begin(), color_vec.size(), index_map1);
620 record_dfs_order dfs_visitor(dfs_vertices, ordered_edges);
621 typedef color_traits<default_color_type> Color;
622 for (vertex_iter u = V_mult.begin(); u != V_mult.end(); ++u) {
623 if (color_map[*u] == Color::white()) {
624 dfs_visitor.start_vertex(*u, G1);
625 depth_first_visit(G1, *u, dfs_visitor, color_map);
628 // Create the dfs_number array and dfs_number_map
629 dfs_number_vec.resize(num_vertices(G1));
630 dfs_number = make_safe_iterator_property_map(dfs_number_vec.begin(),
631 dfs_number_vec.size(), index_map1);
633 for (vertex_iter v = dfs_vertices.begin(); v != dfs_vertices.end(); ++v)
634 dfs_number[*v] = n++;
636 // Renumber ordered_edges array according to DFS number
637 for (edge_iter e = ordered_edges.begin(); e != ordered_edges.end(); ++e) {
639 e->source = dfs_number_vec[e->source];
640 e->target = dfs_number_vec[e->target];
644 \noindent The definition of the \code{record\_dfs\_order} visitor
645 class is as follows. EXPLAIN ficticious edges
647 @d DFS visitor to record vertex and edge order
649 struct record_dfs_order : default_dfs_visitor
651 record_dfs_order(std::vector<vertex1_t>& v, std::vector<ordered_edge>& e)
652 : vertices(v), edges(e) { }
654 void start_vertex(vertex1_t v, const Graph1&) const {
655 edges.push_back(ordered_edge(-1, v));
657 void discover_vertex(vertex1_t v, const Graph1&) const {
658 vertices.push_back(v);
660 void examine_edge(edge1_t e, const Graph1& G1) const {
661 edges.push_back(ordered_edge(source(e, G1), target(e, G1)));
663 std::vector<vertex1_t>& vertices;
664 std::vector<ordered_edge>& edges;
669 Reorder the edges so that all edges belonging to $G_1[k]$
670 appear before any edges not in $G_1[k]$, for $k=1,...,n$.
672 The order field needs a better name. How about k?
674 @d Sort edges according to vertex DFS order
676 std::stable_sort(ordered_edges.begin(), ordered_edges.end());
677 // Fill in i->k_num field
678 if (!ordered_edges.empty()) {
679 ordered_edges[0].k_num = 0;
680 for (edge_iter i = next(ordered_edges.begin()); i != ordered_edges.end(); ++i)
681 i->k_num = std::max(prior(i)->source, prior(i)->target);
690 @d Typedefs for commonly used types
692 typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t;
693 typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
694 typedef typename graph_traits<Graph1>::edge_descriptor edge1_t;
695 typedef typename graph_traits<Graph1>::vertices_size_type size_type;
696 typedef typename Invariant1::result_type invar1_value;
697 typedef typename Invariant2::result_type invar2_value;
700 @d Data members for the parameters
705 Invariant1 invariant1;
706 Invariant2 invariant2;
707 std::size_t max_invariant;
708 IndexMap1 index_map1;
709 IndexMap2 index_map2;
712 @d Internal data structures
714 std::vector<vertex1_t> dfs_vertices;
715 typedef std::vector<vertex1_t>::iterator vertex_iter;
716 std::vector<size_type> dfs_number_vec;
717 safe_iterator_property_map<typename std::vector<size_type>::iterator, IndexMap1>
719 std::vector<ordered_edge> ordered_edges;
720 typedef std::vector<ordered_edge>::iterator edge_iter;
722 std::vector<vertex1_t> f_inv_vec;
723 safe_iterator_property_map<typename std::vector<vertex1_t>::iterator,
726 std::vector<char> f_assigned_vec;
727 safe_iterator_property_map<typename std::vector<char>::iterator,
728 IndexMap1> f_assigned;
730 std::vector<char> f_inv_assigned_vec;
731 safe_iterator_property_map<typename std::vector<char>::iterator,
732 IndexMap2> f_inv_assigned;
734 int num_edges_incident_on_k;
737 @d Isomorphism algorithm constructor
739 isomorphism_algo(const Graph1& G1, const Graph2& G2, IsoMapping f,
740 Invariant1 invariant1, Invariant2 invariant2, std::size_t max_invariant,
741 IndexMap1 index_map1, IndexMap2 index_map2)
742 : G1(G1), G2(G2), f(f), invariant1(invariant1), invariant2(invariant2),
743 max_invariant(max_invariant),
744 index_map1(index_map1), index_map2(index_map2)
746 f_assigned_vec.resize(num_vertices(G1));
747 f_assigned = make_safe_iterator_property_map
748 (f_assigned_vec.begin(), f_assigned_vec.size(), index_map1);
749 f_inv_vec.resize(num_vertices(G1));
750 f_inv = make_safe_iterator_property_map
751 (f_inv_vec.begin(), f_inv_vec.size(), index_map2);
753 f_inv_assigned_vec.resize(num_vertices(G1));
754 f_inv_assigned = make_safe_iterator_property_map
755 (f_inv_assigned_vec.begin(), f_inv_assigned_vec.size(), index_map2);
762 @d Degree vertex invariant functor
764 template <typename InDegreeMap, typename Graph>
765 class degree_vertex_invariant
767 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
768 typedef typename graph_traits<Graph>::degree_size_type size_type;
770 typedef vertex_t argument_type;
771 typedef size_type result_type;
773 degree_vertex_invariant(const InDegreeMap& in_degree_map, const Graph& g)
774 : m_in_degree_map(in_degree_map), m_g(g) { }
776 size_type operator()(vertex_t v) const {
777 return (num_vertices(m_g) + 1) * out_degree(v, m_g)
778 + get(m_in_degree_map, v);
780 // The largest possible vertex invariant number
781 size_type max() const {
782 return num_vertices(m_g) * num_vertices(m_g) + num_vertices(m_g);
785 InDegreeMap m_in_degree_map;
792 ficticiuos edges for the DFS tree roots
793 Use \code{ordered\_edge} instead of \code{edge1\_t} so that we can create ficticious
794 edges for the DFS tree roots.
796 @d Ordered edge class
798 struct ordered_edge {
799 ordered_edge(int s, int t) : source(s), target(t) { }
801 bool operator<(const ordered_edge& e) const {
803 int m1 = max(source, target);
804 int m2 = max(e.source, e.target);
805 // lexicographical comparison of (m1,source,target) and (m2,e.source,e.target)
806 return make_pair(m1, make_pair(source, target)) < make_pair(m2, make_pair(e.source, e.target));
819 \subsection{Recursive Match Function}
825 @d $v$ is a DFS tree root
827 // Try all possible mappings
828 BGL_FORALL_VERTICES_T(y, G2, Graph2) {
829 if (invariant1(v) == invariant2(y) && f_inv_assigned[y] == false) {
830 f[v] = y; f_assigned[v] = true;
831 f_inv[y] = v; f_inv_assigned[y] = true;
832 num_edges_incident_on_k = 0;
833 if (match(next(iter)))
835 f_assigned[v] = false;
836 f_inv_assigned[y] = false;
841 Growing the subgraph.
843 @d $v$ is an unmatched vertex, $(u,v)$ is a tree edge
845 @<Count out-edges of $f(k)$ in $G_2[S]$@>
846 @<Count in-edges of $f(k)$ in $G_2[S]$@>
847 if (num_edges_incident_on_k != 0)
849 @<Assign $v$ to some vertex in $V_2 - S$@>
851 @d Count out-edges of $f(k)$ in $G_2[S]$
853 BGL_FORALL_ADJACENT_T(f[k], w, G2, Graph2)
854 if (f_inv_assigned[w] == true)
855 --num_edges_incident_on_k;
858 @d Count in-edges of $f(k)$ in $G_2[S]$
860 for (std::size_t jj = 0; jj < k_num; ++jj) {
861 vertex1_t j = dfs_vertices[jj];
862 BGL_FORALL_ADJACENT_T(f[j], w, G2, Graph2)
864 --num_edges_incident_on_k;
868 @d Assign $v$ to some vertex in $V_2 - S$
870 BGL_FORALL_ADJACENT_T(f[u], y, G2, Graph2)
871 if (invariant1(v) == invariant2(y) && f_inv_assigned[y] == false) {
872 f[v] = y; f_assigned[v] = true;
873 f_inv[y] = v; f_inv_assigned[y] = true;
874 num_edges_incident_on_k = 1;
875 if (match(next(iter)))
877 f_assigned[v] = false;
878 f_inv_assigned[y] = false;
884 @d Check to see if there is an edge in $G_2$ to match $(u,v)$
887 assert(f_assigned[u] == true);
888 BGL_FORALL_ADJACENT_T(f[u], y, G2, Graph2) {
894 if (verify == true) {
895 ++num_edges_incident_on_k;
896 if (match(next(iter)))
903 @o isomorphism-v2.hpp
905 // Copyright (C) 2001 Jeremy Siek, Douglas Gregor, Brian Osman
907 // Permission to copy, use, sell and distribute this software is granted
908 // provided this copyright notice appears in all copies.
909 // Permission to modify the code and to distribute modified code is granted
910 // provided this copyright notice appears in all copies, and a notice
911 // that the code was modified is included with the copyright notice.
913 // This software is provided "as is" without express or implied warranty,
914 // and with no claim as to its suitability for any purpose.
915 #ifndef BOOST_GRAPH_ISOMORPHISM_HPP
916 #define BOOST_GRAPH_ISOMORPHISM_HPP
922 #include <boost/graph/iteration_macros.hpp>
923 #include <boost/graph/depth_first_search.hpp>
924 #include <boost/utility.hpp>
925 #include <boost/tuple/tuple.hpp>
931 @<Isomorphism algorithm class@>
933 template <typename Graph, typename InDegreeMap>
934 void compute_in_degree(const Graph& g, InDegreeMap in_degree_map)
936 BGL_FORALL_VERTICES_T(v, g, Graph)
937 put(in_degree_map, v, 0);
939 BGL_FORALL_VERTICES_T(u, g, Graph)
940 BGL_FORALL_ADJACENT_T(u, v, g, Graph)
941 put(in_degree_map, v, get(in_degree_map, v) + 1);
944 } // namespace detail
947 @<Degree vertex invariant functor@>
949 @<Isomorphism function interface@>
950 @<Isomorphism function body@>
954 template <typename Graph1, typename Graph2,
956 typename IndexMap1, typename IndexMap2,
957 typename P, typename T, typename R>
958 bool isomorphism_impl(const Graph1& G1, const Graph2& G2,
959 IsoMapping f, IndexMap1 index_map1, IndexMap2 index_map2,
960 const bgl_named_params<P,T,R>& params)
962 std::vector<std::size_t> in_degree1_vec(num_vertices(G1));
963 typedef safe_iterator_property_map<std::vector<std::size_t>::iterator, IndexMap1> InDeg1;
964 InDeg1 in_degree1(in_degree1_vec.begin(), in_degree1_vec.size(), index_map1);
965 compute_in_degree(G1, in_degree1);
967 std::vector<std::size_t> in_degree2_vec(num_vertices(G2));
968 typedef safe_iterator_property_map<std::vector<std::size_t>::iterator, IndexMap2> InDeg2;
969 InDeg2 in_degree2(in_degree2_vec.begin(), in_degree2_vec.size(), index_map2);
970 compute_in_degree(G2, in_degree2);
972 degree_vertex_invariant<InDeg1, Graph1> invariant1(in_degree1, G1);
973 degree_vertex_invariant<InDeg2, Graph2> invariant2(in_degree2, G2);
975 return isomorphism(G1, G2, f,
976 choose_param(get_param(params, vertex_invariant1_t()), invariant1),
977 choose_param(get_param(params, vertex_invariant2_t()), invariant2),
978 choose_param(get_param(params, vertex_max_invariant_t()), invariant2.max()),
979 index_map1, index_map2
983 } // namespace detail
986 // Named parameter interface
987 template <typename Graph1, typename Graph2, class P, class T, class R>
988 bool isomorphism(const Graph1& g1,
990 const bgl_named_params<P,T,R>& params)
992 typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
993 typename std::vector<vertex2_t>::size_type n = num_vertices(g1);
994 std::vector<vertex2_t> f(n);
995 return detail::isomorphism_impl
997 choose_param(get_param(params, vertex_isomorphism_t()),
998 make_safe_iterator_property_map(f.begin(), f.size(),
999 choose_const_pmap(get_param(params, vertex_index1),
1000 g1, vertex_index), vertex2_t())),
1001 choose_const_pmap(get_param(params, vertex_index1), g1, vertex_index),
1002 choose_const_pmap(get_param(params, vertex_index2), g2, vertex_index),
1007 // All defaults interface
1008 template <typename Graph1, typename Graph2>
1009 bool isomorphism(const Graph1& g1, const Graph2& g2)
1011 return isomorphism(g1, g2,
1012 bgl_named_params<int, buffer_param_t>(0));// bogus named param
1016 // Verify that the given mapping iso_map from the vertices of g1 to the
1017 // vertices of g2 describes an isomorphism.
1018 // Note: this could be made much faster by specializing based on the graph
1019 // concepts modeled, but since we're verifying an O(n^(lg n)) algorithm,
1020 // O(n^4) won't hurt us.
1021 template<typename Graph1, typename Graph2, typename IsoMap>
1022 inline bool verify_isomorphism(const Graph1& g1, const Graph2& g2, IsoMap iso_map)
1024 if (num_vertices(g1) != num_vertices(g2) || num_edges(g1) != num_edges(g2))
1027 for (typename graph_traits<Graph1>::edge_iterator e1 = edges(g1).first;
1028 e1 != edges(g1).second; ++e1) {
1029 bool found_edge = false;
1030 for (typename graph_traits<Graph2>::edge_iterator e2 = edges(g2).first;
1031 e2 != edges(g2).second && !found_edge; ++e2) {
1032 if (source(*e2, g2) == get(iso_map, source(*e1, g1)) &&
1033 target(*e2, g2) == get(iso_map, target(*e1, g1))) {
1045 } // namespace boost
1047 #include <boost/graph/iteration_macros_undef.hpp>
1049 #endif // BOOST_GRAPH_ISOMORPHISM_HPP
1052 \bibliographystyle{abbrv}
1056 % LocalWords: Isomorphism Siek isomorphism adjacency subgraph subgraphs OM DFS
1057 % LocalWords: ISOMORPH Invariants invariants typename IsoMapping bool const
1058 % LocalWords: VertexInvariant VertexIndexMap iterator typedef VertexG Idx num
1059 % LocalWords: InvarValue struct invar vec iter tmp_matches mult inserter permute ui
1060 % LocalWords: dfs cmp isomorph VertexIter edge_iter_t IndexMap desc RPH ATCH pre
1062 % LocalWords: iterators VertexListGraph EdgeListGraph BidirectionalGraph tmp
1063 % LocalWords: ReadWritePropertyMap VertexListGraphConcept EdgeListGraphConcept
1064 % LocalWords: BidirectionalGraphConcept ReadWritePropertyMapConcept indices ei
1065 % LocalWords: IsoMappingValue ReadablePropertyMapConcept namespace InvarFun
1066 % LocalWords: MultMap vip inline bitset typedefs fj hpp ifndef adaptor params
1067 % LocalWords: bgl param pmap endif