1 \documentclass[11pt,awpaper]{book}
5 \usepackage[nolineno]{lgrind}
9 \setlength{\evensidemargin}{-0.25in}% was -0.17in
10 \setlength{\oddsidemargin}{0in}%was -0.25in
11 \setlength{\textwidth}{5.625in}%was 5.75in
12 \setlength{\textheight}{7.75in}
13 \setlength{\topmargin}{-0.125in}%was -0.25
14 \addtolength{\topmargin}{-\headheight}
15 \addtolength{\topmargin}{-\headsep}
18 \ifx\pdfoutput\undefined
28 colorlinks=true, %change to true for the electronic version
29 linkcolor=blue,filecolor=blue,pagecolor=blue,urlcolor=blue
34 \newcommand{\stlconcept}[1]{\href{http://www.sgi.com/tech/stl/#1.html}{{\small \textsf{#1}}}}
35 \newcommand{\bglconcept}[1]{\href{http://www.boost.org/libs/graph/doc/#1.html}{{\small \textsf{#1}}}}
36 \newcommand{\pmconcept}[1]{\href{http://www.boost.org/libs/property_map/#1.html}{{\small \textsf{#1}}}}
37 \newcommand{\myhyperref}[2]{\hyperref[#1]{#2}}
38 \newcommand{\vizfig}[2]{\begin{figure}[htbp]\centerline{\includegraphics*{#1.pdf}}\caption{#2}\label{fig:#1}\end{figure}}
40 \newcommand{\myhyperref}[2]{#2}
41 \newcommand{\bglconcept}[1]{{\small \textsf{#1}}}
42 \newcommand{\pmconcept}[1]{{\small \textsf{#1}}}
43 \newcommand{\stlconcept}[1]{{\small \textsf{#1}}}
44 \newcommand{\vizfig}[2]{\begin{figure}[htbp]\centerline{\includegraphics*{#1.eps}}\caption{#2}\label{fig:#1}\end{figure}}
47 \newcommand{\code}[1]{{\small{\em \textbf{#1}}}}
50 \newcommand{\isomorphic}{\cong}
54 \title{An Implementation of Graph Isomorphism Testing}
55 \author{Jeremy G. Siek}
59 % Ideas: use BFS instead of DFS, don't have to sort edges?
60 % No, you would still have to sort the edges.
62 %Figure~\ref{fig:iso-eg2}.
65 %\vizfig{iso-eg2}{Vertices numbered by BFS discover time. The BFS tree
66 %edges are the solid lines. Nodes $0$ and $5$ are BFS tree root nodes.}
68 % You could do a modified Dijkstra, where the priority in the queue
69 % would be the BFS discover time of the target vertex.
71 % Use w(u,v) = |Adj[u] \intersect Adj[v]| as an edge invariant.
72 % Has anyone used edge invariants before?
75 \section{Introduction}
77 This paper documents the implementation of the \code{isomorphism()}
78 function of the Boost Graph Library. The implementation was by Jeremy
79 Siek with algorithmic improvements and test code from Douglas Gregor
80 and Brian Osman. The \code{isomorphism()} function answers the
81 question, ``are these two graphs equal?'' By \emph{equal} we mean
82 the two graphs have the same structure---the vertices and edges are
83 connected in the same way. The mathematical name for this kind of
84 equality is \emph{isomorphism}.
86 More precisely, an \emph{isomorphism} is a one-to-one mapping of the
87 vertices in one graph to the vertices of another graph such that
88 adjacency is preserved. Another words, given graphs $G_{1} =
89 (V_{1},E_{1})$ and $G_{2} = (V_{2},E_{2})$, an isomorphism is a
90 function $f$ such that for all pairs of vertices $a,b$ in $V_{1}$,
91 edge $(a,b)$ is in $E_{1}$ if and only if edge $(f(a),f(b))$ is in
94 The graph $G_1$ is \emph{isomorphic} to $G_2$ if an isomorphism exists
95 between the two graphs, which we denote by $G_1 \isomorphic G_2$.
96 Both graphs must be the same size, so let $N = |V_1| = |V_2|$.
98 In the following discussion we will need to use several more notions
99 from graph theory. The graph $G_s=(V_s,E_s)$ is a \emph{subgraph} of
100 graph $G=(V,E)$ if $V_s \subseteq V$ and $E_s \subseteq E$. An
101 \emph{induced subgraph}, denoted by $G[V_s]$, of a graph $G=(V,E)$
102 consists of the vertices in $V_s$, which is a subset of $V$, and every
103 edge $(u,v)$ in $E$ such that both $u$ and $v$ are in $V_s$. We use
104 the notation $E[V_s]$ to mean the edges in $G[V_s]$.
106 \section{Backtracking Search}
107 \label{sec:backtracking}
109 The algorithm used by the \code{isomorphism()} function is, at first
110 approximation, an exhaustive search implemented via backtracking. The
111 backtracking algorithm is a recursive function. At each stage we will
112 try to extend the match that we have found so far. So suppose that we
113 have already determined that some subgraph of $G_1$ is isomorphic to a
114 subgraph of $G_2$. We then try to add a vertex to each subgraph such
115 that the new subgraphs are still isomorphic to one another. At some
116 point we may hit a dead end---there are no vertices that can be added
117 to extend the isomorphic subgraphs. We then backtrack to previous
118 smaller matching subgraphs, and try extending with a different vertex
119 choice. The process ends by either finding a complete mapping between
120 $G_1$ and $G_2$ and returning true, or by exhausting all possibilities
123 The problem with the exhaustive backtracking algorithm is that there
124 are $N!$ possible vertex mappings, and $N!$ gets very large as $N$
125 increases, so we need to prune the search space. We use the pruning
126 techniques described in
127 \cite{deo77:_new_algo_digraph_isomorph,fortin96:_isomorph,reingold77:_combin_algo},
128 some of which originated in
129 \cite{sussenguth65:_isomorphism,unger64:_isomorphism}. Also, the
130 specific backtracking method we use is the one from
131 \cite{deo77:_new_algo_digraph_isomorph}.
133 We consider the vertices of $G_1$ for addition to the matched subgraph
134 in a specific order, so assume that the vertices of $G_1$ are labeled
135 $1,\ldots,N$ according to that order. As we will see later, a good
136 ordering of the vertices is by DFS discover time. Let $G_1[k]$ denote
137 the subgraph of $G_1$ induced by the first $k$ vertices, with $G_1[0]$
138 being an empty graph. We also consider the edges of $G_1$ in a
139 specific order. We always examine edges in the current subgraph
140 $G_1[k]$ first, that is, edges $(u,v)$ where both $u \leq k$ and $v
141 \leq k$. This ordering of edges can be acheived by sorting each edge
142 $(u,v)$ by lexicographical comparison on the tuple $\langle \max(u,v),
143 u, v \rangle$. Figure~\ref{fig:iso-eg} shows an example of a graph
144 with the vertices labelled by DFS discover time. The edge ordering for
145 this graph is as follows:
147 \begin{tabular}{lccccccccc}
148 source: &0&1&0&1&3&0&5&6&6\\
149 target: &1&2&3&3&2&4&6&4&7
152 \vizfig{iso-eg}{Vertices numbered by DFS discover time. The DFS tree
153 edges are the solid lines. Nodes $0$ and $5$ are DFS tree root nodes.}
155 Each step of the backtracking search moves from left to right though
156 the ordered edges. At each step it examines an edge $(i,j)$ of $G_1$
157 and decides whether to continue to the left or to go back. There are
158 three cases to consider:
161 \item \label{case:1} $i > k$
162 \item \label{case:2} $i \leq k$ and $j > k$.
163 \item \label{case:3} $i \leq k$ and $j \leq k$.
166 \paragraph{Case 1: $i > k$.}
167 $i$ is not in the matched subgraph $G_1[k]$. This situation only
168 happens at the very beginning of the search, or when $i$ is not
169 reachable from any of the vertices in $G_1[k]$. This means that we
170 are finished with $G_1[k]$. We increment $k$ and find a match for it
171 amongst any of the eligible vertices in $V_2 - S$. We then proceed to
172 Case 2. It is usually the case that $i$ is equal to the new $k$, but
173 when there is another DFS root $r$ with no in-edges or out-edges
174 and if $r < i$ then it will be the new $k$.
176 \paragraph{Case 2: $i \leq k$ and $j > k$.}
177 $i$ is in the matched subgraph $G_1[k]$, but $j$ is not. We are about
178 to increment $k$ to try and grow the matched subgraph to include
179 $j$. However, first we need to finish verifying that $G_1[k]
180 \isomorphic G_2[S]$. In previous steps we proved that $G_1[k-1]
181 \isomorphic G_2[S-\{f(k)\}]$, so now we just need to verify the
182 extension of the isomorphism to $k$. At this point we are guaranteed
183 to have seen all the edges to and from vertex $k$ (because the edges
184 are sorted), and in previous steps we have checked that for each edge
185 incident on $k$ in $E_1[k]$ there is a matching edge in
186 $E_2[S]$. However we still need to check the ``only if'' part of the
187 ``if and only if''. So we check that for every edge $(u,v)$ incident
188 on $f(k)$ there is $(f^{-1}(u),f^{-1}(v)) \in E_1[k]$. A quick way to
189 verify this is to make sure that the number of edges incident on $k$
190 in $E_1[k]$ is the same as the number of edges incident on $f(k)$ in
191 $E_2[S]$. We create an edge counter that we increment every time we
192 see an edge incident on $k$ and decrement for each edge incident on
193 $f(k)$. If the counter gets back to zero we know the edges match up.
195 Once we have verified that $G_1[k] \isomorphic G_2[S]$ we add $f(k)$
196 to $S$, increment $k$, and then try assigning $j$ to
197 any of the eligible vertices in $V_2 - S$. More about what
198 ``eligible'' means below.
200 \paragraph{Case 3: $i \leq k$ and $j \leq k$.}
201 Both $i$ and $j$ are in $G_1[k]$. We check to make sure that
202 $(f(i),f(j)) \in E_2[S]$ and then proceed to the next edge.
205 \subsection{Vertex Invariants}
206 \label{sec:vertex-invariants}
208 One way to reduce the search space is through the use of \emph{vertex
209 invariants}. The idea is to compute a number for each vertex $i(v)$
210 such that $i(v) = i(v')$ if there exists some isomorphism $f$ where
211 $f(v) = v'$. Then when we look for a match to some vertex $v$, only
212 those vertices that have the same vertex invariant number are
213 ``eligible''. The number of vertices in a graph with the same vertex
214 invariant number $i$ is called the \emph{invariant multiplicity} for
215 $i$. In this implementation, by default we use the function $i(v) =
216 (|V|+1) \times \outdegree(v) + \indegree(v)$, though the user can also
217 supply there own invariant function. The ability of the invariant
218 function to prune the search space varies widely with the type of
221 The following is the definition of the functor that implements the
222 default vertex invariant. The functor models the
223 \stlconcept{AdaptableUnaryFunction} concept.
225 @d Degree vertex invariant functor
227 template <typename InDegreeMap, typename Graph>
228 class degree_vertex_invariant
230 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
231 typedef typename graph_traits<Graph>::degree_size_type size_type;
233 typedef vertex_t argument_type;
234 typedef size_type result_type;
236 degree_vertex_invariant(const InDegreeMap& in_degree_map, const Graph& g)
237 : m_in_degree_map(in_degree_map), m_g(g) { }
239 size_type operator()(vertex_t v) const {
240 return (num_vertices(m_g) + 1) * out_degree(v, m_g)
241 + get(m_in_degree_map, v);
243 // The largest possible vertex invariant number
244 size_type max() const {
245 return num_vertices(m_g) * num_vertices(m_g) + num_vertices(m_g);
248 InDegreeMap m_in_degree_map;
254 \subsection{Vertex Order}
256 A good choice of the labeling for the vertices (which determines the
257 order in which the subgraph $G_1[k]$ is grown) can also reduce the
258 search space. In the following we discuss two labeling heuristics.
260 \subsubsection{Most Constrained First}
262 Consider the most constrained vertices first. That is, examine
263 lower-degree vertices before higher-degree vertices. This reduces the
264 search space because it chops off a trunk before the trunk has a
265 chance to blossom out. We can generalize this to use vertex
266 invariants. We examine vertices with low invariant multiplicity
267 before examining vertices with high invariant multiplicity.
269 \subsubsection{Adjacent First}
271 It only makes sense to examine an edge if one or more of its vertices
272 has been assigned a mapping. This means that we should visit vertices
273 adjacent to those in the current matched subgraph before proceeding.
275 \subsubsection{DFS Order, Starting with Lowest Multiplicity}
277 For this implementation, we combine the above two heuristics in the
278 following way. To implement the ``adjacent first'' heuristic we apply
279 DFS to the graph, and use the DFS discovery order as our vertex
280 order. To comply with the ``most constrained first'' heuristic we
281 order the roots of our DFS trees by invariant multiplicity.
284 \subsection{Implementation of the \code{match} function}
287 The \code{match} function implements the recursive backtracking,
288 handling the four cases described in \S\ref{sec:backtracking}.
292 bool match(edge_iter iter, int dfs_num_k)
294 if (iter != ordered_edges.end()) {
295 vertex1_t i = source(*iter, G1), j = target(*iter, G2);
296 if (dfs_num[i] > dfs_num_k) {
297 @<Find a match for the DFS tree root $k+1$@>
299 else if (dfs_num[j] > dfs_num_k) {
300 @<Verify $G_1[k] \isomorphic G_2[S]$ and then find match for $j$@>
303 @<Check to see if $(f(i),f(j)) \in E_2[S]$ and continue@>
311 \noindent Now to describe how each of the four cases is implemented.
313 \paragraph{Case 1: $i \not\in G_1[k]$.}
314 We increment $k$ and try to map it to any of the eligible vertices of
315 $V_2 - S$. After matching the new $k$ we proceed by invoking
316 \code{match}. We do not yet move on to the next edge, since we have
317 not yet found a match for edge, or for target $j$. We reset the edge
320 @d Find a match for the DFS tree root $k+1$
322 vertex1_t kp1 = dfs_vertices[dfs_num_k + 1];
323 BGL_FORALL_VERTICES_T(u, G2, Graph2) {
324 if (invariant1(kp1) == invariant2(u) && in_S[u] == false) {
328 if (match(iter, dfs_num_k + 1));
336 \paragraph{Case 2: $i \in G_1[k]$ and $j \not\in G_1[k]$.}
337 Before we extend the subgraph by incrementing $k$, we need to finish
338 verifying that $G_1[k]$ and $G_2[S]$ are isomorphic. We decrement the
339 edge counter for every edge incident to $f(k)$ in $G_2[S]$, which
340 should bring the counter back down to zero. If not we return false.
342 @d Verify $G_1[k] \isomorphic G_2[S]$ and then find match for $j$
344 vertex1_t k = dfs_vertices[dfs_num_k];
345 @<Count out-edges of $f(k)$ in $G_2[S]$@>
346 @<Count in-edges of $f(k)$ in $G_2[S]$@>
347 if (num_edges_on_k != 0)
349 @<Find a match for $j$ and continue@>
352 \noindent We decrement the edge counter for every vertex in
353 $Adj[f(k)]$ that is also in $S$. We call \code{count\_if} to do the
354 counting, using \code{boost::bind} to create the predicate functor.
356 @d Count out-edges of $f(k)$ in $G_2[S]$
359 count_if(adjacent_vertices(f[k], G2), make_indirect_pmap(in_S));
362 \noindent Next we iterate through all the vertices in $S$ and for each
363 we decrement the counter for each edge whose target is $k$.
365 % We could specialize this for the case when G_2 is bidirectional.
367 @d Count in-edges of $f(k)$ in $G_2[S]$
369 for (int jj = 0; jj < dfs_num_k; ++jj) {
370 vertex1_t j = dfs_vertices[jj];
371 num_edges_on_k -= count(adjacent_vertices(f[j], G2), f[k]);
375 Now that we have finished verifying that $G_1[k] \isomorphic G_2[S]$,
376 we can now consider extending the isomorphism. We need to find a match
377 for $j$ in $V_2 - S$. Since $j$ is adjacent to $i$, we can further
378 narrow down the search by only considering vertices adjacent to
379 $f(i)$. Also, the vertex must have the same vertex invariant. Once we
380 have a matching vertex $v$ we extend the matching subgraphs by
381 incrementing $k$ and adding $v$ to $S$, we set $f(j) = v$, and we set
382 the edge counter to $1$ (since $(i,j)$ is the first edge incident on
383 our new $k$). We continue to the next edge by calling \code{match}. If
384 that fails we undo the assignment $f(j) = v$.
386 @d Find a match for $j$ and continue
388 BGL_FORALL_ADJ_T(f[i], v, G2, Graph2)
389 if (invariant2(v) == invariant1(j) && in_S[v] == false) {
393 int next_k = std::max(dfs_num_k, std::max(dfs_num[i], dfs_num[j]));
394 if (match(next(iter), next_k))
400 \paragraph{Case 3: both $i$ and $j$ are in $G_1[k]$.}
401 Our goal is to check whether $(f(i),f(j)) \in E_2[S]$. If $f(j)$ is
402 in $Adj[f(i)]$ then we have a match for the edge $(i,j)$, and can
403 increment the counter for the number of edges incident on $k$ in
404 $E_1[k]$. We continue by calling \code{match} on the next edge.
406 @d Check to see if $(f(i),f(j)) \in E_2[S]$ and continue
409 bool fi_fj_exists = false;
410 typename graph_traits<Graph2>::out_edge_iterator io, io_end;
411 for (tie(io, io_end) = out_edges(f[i], G2); io != io_end; ++io)
412 if (target(*io, G2) == f[j]) {
417 if (fi_fj_exists && edge_compare(e2, *iter)) {
419 if (match(next(iter), dfs_num_k))
424 \section{Public Interface}
426 The following is the public interface for the \code{isomorphism}
427 function. The input to the function is the two graphs $G_1$ and $G_2$,
428 mappings from the vertices in the graphs to integers (in the range
429 $[0,|V|)$), and a vertex invariant function object. The output of the
430 function is an isomorphism $f$ if there is one. The \code{isomorphism}
431 function returns true if the graphs are isomorphic and false
432 otherwise. The invariant parameters are function objects that compute
433 the vertex invariants for vertices of the two graphs. The
434 \code{max\_invariant} parameter is to specify one past the largest
435 integer that a vertex invariant number could be (the invariants
436 numbers are assumed to span from zero to \code{max\_invariant-1}).
437 The requirements on the template parameters are described below in the
438 ``Concept checking'' code part.
441 @d Isomorphism function interface
443 template <typename Graph1, typename Graph2, typename IsoMapping,
444 typename Invariant1, typename Invariant2, typename EdgeCompare,
445 typename IndexMap1, typename IndexMap2>
446 bool isomorphism(const Graph1& G1, const Graph2& G2, IsoMapping f,
447 Invariant1 invariant1, Invariant2 invariant2,
448 std::size_t max_invariant, EdgeCompare edge_compare,
449 IndexMap1 index_map1, IndexMap2 index_map2)
453 The function body consists of the concept checks followed by a quick
454 check for empty graphs or graphs of different size and then constructs
455 an algorithm object. We then call the \code{test\_isomorphism} member
456 function, which runs the algorithm. The reason that we implement the
457 algorithm using a class is that there are a fair number of internal
458 data structures required, and it is easier to make these data members
459 of a class and make each section of the algorithm a member
460 function. This relieves us from the burden of passing lots of
461 arguments to each function, while at the same time avoiding the evils
462 of global variables (non-reentrant, etc.).
465 @d Isomorphism function body
469 @<Quick return based on size@>
470 detail::isomorphism_algo<Graph1, Graph2, IsoMapping, Invariant1,
471 Invariant2, EdgeCompare, IndexMap1, IndexMap2>
472 algo(G1, G2, f, invariant1, invariant2, max_invariant,
474 index_map1, index_map2);
475 return algo.test_isomorphism();
480 \noindent If there are no vertices in either graph, then they are
481 trivially isomorphic. If the graphs have different numbers of vertices
482 then they are not isomorphic. We could also check the number of edges
483 here, but that would introduce the \bglconcept{EdgeListGraph}
484 requirement, which we otherwise do not need.
486 @d Quick return based on size
488 if (num_vertices(G1) != num_vertices(G2))
490 if (num_vertices(G1) == 0 && num_vertices(G2) == 0)
494 We use the Boost Concept Checking Library to make sure that the
495 template arguments fulfill certain requirements. The graph types must
496 model the \bglconcept{VertexListGraph} and \bglconcept{AdjacencyGraph}
497 concepts. The vertex invariants must model the
498 \stlconcept{AdaptableUnaryFunction} concept, with a vertex as their
499 argument and an integer return type. The \code{IsoMapping} type
500 representing the isomorphism $f$ must be a
501 \pmconcept{ReadWritePropertyMap} that maps from vertices in $G_1$ to
502 vertices in $G_2$. The two other index maps are
503 \pmconcept{ReadablePropertyMap}s from vertices in $G_1$ and $G_2$ to
509 // Graph requirements
510 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph1> ));
511 BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> ));
512 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph2> ));
513 BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph2> ));
515 typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t;
516 typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
517 typedef typename graph_traits<Graph1>::vertices_size_type size_type;
519 // Vertex invariant requirement
520 BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Invariant1,
521 size_type, vertex1_t> ));
522 BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Invariant2,
523 size_type, vertex2_t> ));
525 // Property map requirements
526 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<IsoMapping, vertex1_t> ));
527 typedef typename property_traits<IsoMapping>::value_type IsoMappingValue;
528 BOOST_STATIC_ASSERT((is_same<IsoMappingValue, vertex2_t>::value));
530 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap1, vertex1_t> ));
531 typedef typename property_traits<IndexMap1>::value_type IndexMap1Value;
532 BOOST_STATIC_ASSERT((is_convertible<IndexMap1Value, size_type>::value));
534 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap2, vertex2_t> ));
535 typedef typename property_traits<IndexMap2>::value_type IndexMap2Value;
536 BOOST_STATIC_ASSERT((is_convertible<IndexMap2Value, size_type>::value));
540 \section{Data Structure Setup}
542 The following is the outline of the isomorphism algorithm class. The
543 class is templated on all of the same parameters as the
544 \code{isomorphism} function, and all of the parameter values are
545 stored in the class as data members, in addition to the internal data
548 @d Isomorphism algorithm class
550 template <typename Graph1, typename Graph2, typename IsoMapping,
551 typename Invariant1, typename Invariant2, typename EdgeCompare,
552 typename IndexMap1, typename IndexMap2>
553 class isomorphism_algo
555 @<Typedefs for commonly used types@>
556 @<Data members for the parameters@>
557 @<Internal data structures@>
558 friend struct compare_multiplicity;
559 @<Invariant multiplicity comparison functor@>
560 @<DFS visitor to record vertex and edge order@>
561 @<Edge comparison predicate@>
563 @<Isomorphism algorithm constructor@>
564 @<Test isomorphism member function@>
570 The interesting parts of this class are the \code{test\_isomorphism}
571 function and the \code{match} function. We focus on those in the
572 following sections, and leave the other parts of the class to the
575 The \code{test\_isomorphism} function does all of the setup required
576 of the algorithm. This consists of sorting the vertices according to
577 invariant multiplicity, and then by DFS order. The edges are then
578 sorted as previously described. The last step of this function is to
579 begin the backtracking search.
581 @d Test isomorphism member function
583 bool test_isomorphism()
585 @<Quick return if the vertex invariants do not match up@>
586 @<Sort vertices according to invariant multiplicity@>
587 @<Order vertices and edges by DFS@>
588 @<Sort edges according to vertex DFS order@>
591 return this->match(ordered_edges.begin(), dfs_num_k);
595 As a first check to rule out graphs that have no possibility of
596 matching, one can create a list of computed vertex invariant numbers
597 for the vertices in each graph, sort the two lists, and then compare
598 them. If the two lists are different then the two graphs are not
599 isomorphic. If the two lists are the same then the two graphs may be
602 @d Quick return if the vertex invariants do not match up
605 std::vector<invar1_value> invar1_array;
606 BGL_FORALL_VERTICES_T(v, G1, Graph1)
607 invar1_array.push_back(invariant1(v));
610 std::vector<invar2_value> invar2_array;
611 BGL_FORALL_VERTICES_T(v, G2, Graph2)
612 invar2_array.push_back(invariant2(v));
614 if (! equal(invar1_array, invar2_array))
619 Next we compute the invariant multiplicity, the number of vertices
620 with the same invariant number. The \code{invar\_mult} vector is
621 indexed by invariant number. We loop through all the vertices in the
622 graph to record the multiplicity. We then order the vertices by their
623 invariant multiplicity. This will allow us to search the more
624 constrained vertices first.
626 @d Sort vertices according to invariant multiplicity
628 std::vector<vertex1_t> V_mult;
629 BGL_FORALL_VERTICES_T(v, G1, Graph1)
632 std::vector<size_type> multiplicity(max_invariant, 0);
633 BGL_FORALL_VERTICES_T(v, G1, Graph1)
634 ++multiplicity[invariant1(v)];
635 sort(V_mult, compare_multiplicity(invariant1, &multiplicity[0]));
639 \noindent The definition of the \code{compare\_multiplicity} predicate
640 is shown below. This predicate provides the glue that binds
641 \code{std::sort} to our current purpose.
643 @d Invariant multiplicity comparison functor
645 struct compare_multiplicity
647 compare_multiplicity(Invariant1 invariant1, size_type* multiplicity)
648 : invariant1(invariant1), multiplicity(multiplicity) { }
649 bool operator()(const vertex1_t& x, const vertex1_t& y) const {
650 return multiplicity[invariant1(x)] < multiplicity[invariant1(y)];
652 Invariant1 invariant1;
653 size_type* multiplicity;
657 \subsection{Ordering by DFS Discover Time}
659 Next we order the vertices and edges by DFS discover time. We would
660 normally call the BGL \code{depth\_first\_search} function to do this,
661 but we want the roots of the DFS tree's to be ordered by invariant
662 multiplicity. Therefore we implement the outer-loop of the DFS here
663 and then call \code{depth\_\-first\_\-visit} to handle the recursive
664 portion of the DFS. The \code{record\_dfs\_order} adapts the DFS to
665 record the ordering, storing the results in in the
666 \code{dfs\_vertices} and \code{ordered\_edges} arrays. We then create
667 the \code{dfs\_num} array which provides a mapping from vertex to DFS
670 @d Order vertices and edges by DFS
672 std::vector<default_color_type> color_vec(num_vertices(G1));
673 safe_iterator_property_map<std::vector<default_color_type>::iterator, IndexMap1>
674 color_map(color_vec.begin(), color_vec.size(), index_map1);
675 record_dfs_order dfs_visitor(dfs_vertices, ordered_edges);
676 typedef color_traits<default_color_type> Color;
677 for (vertex_iter u = V_mult.begin(); u != V_mult.end(); ++u) {
678 if (color_map[*u] == Color::white()) {
679 dfs_visitor.start_vertex(*u, G1);
680 depth_first_visit(G1, *u, dfs_visitor, color_map);
683 // Create the dfs_num array and dfs_num_map
684 dfs_num_vec.resize(num_vertices(G1));
685 dfs_num = make_safe_iterator_property_map(dfs_num_vec.begin(),
686 dfs_num_vec.size(), index_map1);
688 for (vertex_iter v = dfs_vertices.begin(); v != dfs_vertices.end(); ++v)
692 \noindent The definition of the \code{record\_dfs\_order} visitor
695 @d DFS visitor to record vertex and edge order
697 struct record_dfs_order : default_dfs_visitor
699 record_dfs_order(std::vector<vertex1_t>& v, std::vector<edge1_t>& e)
700 : vertices(v), edges(e) { }
702 void discover_vertex(vertex1_t v, const Graph1&) const {
703 vertices.push_back(v);
705 void examine_edge(edge1_t e, const Graph1& G1) const {
708 std::vector<vertex1_t>& vertices;
709 std::vector<edge1_t>& edges;
713 The final stage of the setup is to reorder the edges so that all edges
714 belonging to $G_1[k]$ appear before any edges not in $G_1[k]$, for
717 @d Sort edges according to vertex DFS order
719 sort(ordered_edges, edge_cmp(G1, dfs_num));
722 \noindent The edge comparison function object is defined as follows.
724 @d Edge comparison predicate
727 edge_cmp(const Graph1& G1, DFSNumMap dfs_num)
728 : G1(G1), dfs_num(dfs_num) { }
729 bool operator()(const edge1_t& e1, const edge1_t& e2) const {
731 vertex1_t u1 = dfs_num[source(e1,G1)], v1 = dfs_num[target(e1,G1)];
732 vertex1_t u2 = dfs_num[source(e2,G1)], v2 = dfs_num[target(e2,G1)];
733 int m1 = max(u1, v1);
734 int m2 = max(u2, v2);
735 // lexicographical comparison
736 return make_pair(m1, make_pair(u1, v1))
737 < make_pair(m2, make_pair(u2, v2));
748 @d Typedefs for commonly used types
750 typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t;
751 typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
752 typedef typename graph_traits<Graph1>::edge_descriptor edge1_t;
753 typedef typename graph_traits<Graph2>::edge_descriptor edge2_t;
754 typedef typename graph_traits<Graph1>::vertices_size_type size_type;
755 typedef typename Invariant1::result_type invar1_value;
756 typedef typename Invariant2::result_type invar2_value;
759 @d Data members for the parameters
764 Invariant1 invariant1;
765 Invariant2 invariant2;
766 std::size_t max_invariant;
767 EdgeCompare edge_compare;
768 IndexMap1 index_map1;
769 IndexMap2 index_map2;
772 @d Internal data structures
774 std::vector<vertex1_t> dfs_vertices;
775 typedef typename std::vector<vertex1_t>::iterator vertex_iter;
776 std::vector<int> dfs_num_vec;
777 typedef safe_iterator_property_map<typename std::vector<int>::iterator,
778 IndexMap1> DFSNumMap;
780 std::vector<edge1_t> ordered_edges;
781 typedef typename std::vector<edge1_t>::iterator edge_iter;
783 std::vector<char> in_S_vec;
784 typedef safe_iterator_property_map<typename std::vector<char>::iterator,
791 @d Isomorphism algorithm constructor
793 isomorphism_algo(const Graph1& G1, const Graph2& G2, IsoMapping f,
794 Invariant1 invariant1, Invariant2 invariant2,
795 std::size_t max_invariant,
796 EdgeCompare edge_compare,
797 IndexMap1 index_map1, IndexMap2 index_map2)
798 : G1(G1), G2(G2), f(f), invariant1(invariant1), invariant2(invariant2),
799 max_invariant(max_invariant), edge_compare(edge_compare),
800 index_map1(index_map1), index_map2(index_map2)
802 in_S_vec.resize(num_vertices(G1));
803 in_S = make_safe_iterator_property_map
804 (in_S_vec.begin(), in_S_vec.size(), index_map2);
811 // Copyright (C) 2001 Jeremy Siek, Douglas Gregor, Brian Osman
813 // Permission to copy, use, sell and distribute this software is granted
814 // provided this copyright notice appears in all copies.
815 // Permission to modify the code and to distribute modified code is granted
816 // provided this copyright notice appears in all copies, and a notice
817 // that the code was modified is included with the copyright notice.
819 // This software is provided "as is" without express or implied warranty,
820 // and with no claim as to its suitability for any purpose.
821 #ifndef BOOST_GRAPH_ISOMORPHISM_HPP
822 #define BOOST_GRAPH_ISOMORPHISM_HPP
828 #include <boost/graph/iteration_macros.hpp>
829 #include <boost/graph/depth_first_search.hpp>
830 #include <boost/utility.hpp>
831 #include <boost/detail/algorithm.hpp>
832 #include <boost/pending/indirect_cmp.hpp> // for make_indirect_pmap
838 @<Isomorphism algorithm class@>
840 template <typename Graph, typename InDegreeMap>
841 void compute_in_degree(const Graph& g, InDegreeMap in_degree_map)
843 BGL_FORALL_VERTICES_T(v, g, Graph)
844 put(in_degree_map, v, 0);
846 BGL_FORALL_VERTICES_T(u, g, Graph)
847 BGL_FORALL_ADJ_T(u, v, g, Graph)
848 put(in_degree_map, v, get(in_degree_map, v) + 1);
851 } // namespace detail
854 @<Degree vertex invariant functor@>
856 @<Isomorphism function interface@>
857 @<Isomorphism function body@>
861 struct default_edge_compare {
862 template <typename Edge1, typename Edge2>
863 bool operator()(Edge1 e1, Edge2 e2) const { return true; }
866 template <typename Graph1, typename Graph2,
868 typename IndexMap1, typename IndexMap2,
869 typename P, typename T, typename R>
870 bool isomorphism_impl(const Graph1& G1, const Graph2& G2,
871 IsoMapping f, IndexMap1 index_map1, IndexMap2 index_map2,
872 const bgl_named_params<P,T,R>& params)
874 std::vector<std::size_t> in_degree1_vec(num_vertices(G1));
875 typedef safe_iterator_property_map<std::vector<std::size_t>::iterator,
877 InDeg1 in_degree1(in_degree1_vec.begin(), in_degree1_vec.size(), index_map1);
878 compute_in_degree(G1, in_degree1);
880 std::vector<std::size_t> in_degree2_vec(num_vertices(G2));
881 typedef safe_iterator_property_map<std::vector<std::size_t>::iterator,
883 InDeg2 in_degree2(in_degree2_vec.begin(), in_degree2_vec.size(), index_map2);
884 compute_in_degree(G2, in_degree2);
886 degree_vertex_invariant<InDeg1, Graph1> invariant1(in_degree1, G1);
887 degree_vertex_invariant<InDeg2, Graph2> invariant2(in_degree2, G2);
888 default_edge_compare edge_cmp;
890 return isomorphism(G1, G2, f,
891 choose_param(get_param(params, vertex_invariant1_t()), invariant1),
892 choose_param(get_param(params, vertex_invariant2_t()), invariant2),
893 choose_param(get_param(params, vertex_max_invariant_t()),
895 choose_param(get_param(params, edge_compare_t()), edge_cmp),
896 index_map1, index_map2
900 } // namespace detail
903 // Named parameter interface
904 template <typename Graph1, typename Graph2, class P, class T, class R>
905 bool isomorphism(const Graph1& g1,
907 const bgl_named_params<P,T,R>& params)
909 typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
910 typename std::vector<vertex2_t>::size_type n = num_vertices(g1);
911 std::vector<vertex2_t> f(n);
912 return detail::isomorphism_impl
914 choose_param(get_param(params, vertex_isomorphism_t()),
915 make_safe_iterator_property_map(f.begin(), f.size(),
916 choose_const_pmap(get_param(params, vertex_index1),
917 g1, vertex_index), vertex2_t())),
918 choose_const_pmap(get_param(params, vertex_index1), g1, vertex_index),
919 choose_const_pmap(get_param(params, vertex_index2), g2, vertex_index),
924 // All defaults interface
925 template <typename Graph1, typename Graph2>
926 bool isomorphism(const Graph1& g1, const Graph2& g2)
928 return isomorphism(g1, g2,
929 bgl_named_params<int, buffer_param_t>(0));// bogus named param
933 // Verify that the given mapping iso_map from the vertices of g1 to the
934 // vertices of g2 describes an isomorphism.
935 // Note: this could be made much faster by specializing based on the graph
936 // concepts modeled, but since we're verifying an O(n^(lg n)) algorithm,
937 // O(n^4) won't hurt us.
938 template<typename Graph1, typename Graph2, typename IsoMap>
939 inline bool verify_isomorphism(const Graph1& g1, const Graph2& g2, IsoMap iso_map)
942 // problematic for filtered_graph!
943 if (num_vertices(g1) != num_vertices(g2) || num_edges(g1) != num_edges(g2))
947 for (typename graph_traits<Graph1>::edge_iterator e1 = edges(g1).first;
948 e1 != edges(g1).second; ++e1) {
949 bool found_edge = false;
950 for (typename graph_traits<Graph2>::edge_iterator e2 = edges(g2).first;
951 e2 != edges(g2).second && !found_edge; ++e2) {
952 if (source(*e2, g2) == get(iso_map, source(*e1, g1)) &&
953 target(*e2, g2) == get(iso_map, target(*e1, g1))) {
967 #include <boost/graph/iteration_macros_undef.hpp>
969 #endif // BOOST_GRAPH_ISOMORPHISM_HPP
972 \bibliographystyle{abbrv}
976 % LocalWords: Isomorphism Siek isomorphism adjacency subgraph subgraphs OM DFS
977 % LocalWords: ISOMORPH Invariants invariants typename IsoMapping bool const
978 % LocalWords: VertexInvariant VertexIndexMap iterator typedef VertexG Idx num
979 % LocalWords: InvarValue struct invar vec iter tmp_matches mult inserter permute ui
980 % LocalWords: dfs cmp isomorph VertexIter edge_iter_t IndexMap desc RPH ATCH pre
982 % LocalWords: iterators VertexListGraph EdgeListGraph BidirectionalGraph tmp
983 % LocalWords: ReadWritePropertyMap VertexListGraphConcept EdgeListGraphConcept
984 % LocalWords: BidirectionalGraphConcept ReadWritePropertyMapConcept indices ei
985 % LocalWords: IsoMappingValue ReadablePropertyMapConcept namespace InvarFun
986 % LocalWords: MultMap vip inline bitset typedefs fj hpp ifndef adaptor params
987 % LocalWords: bgl param pmap endif