1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek 2000 4 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9<Head> 10<Title>Boost Graph Library: Isomorphism</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18<H1> 19<img src="figs/python.gif" alt="(Python)"/> 20<TT>isomorphism</TT> 21</H1> 22 23 24<PRE> 25<i>// named parameter version</i> 26template <class Graph1, class Graph2, class P, class T, class R> 27bool isomorphism(const Graph1& g1, const Graph2& g2, 28 const bgl_named_params<P,T,R>& params = <i>all defaults</i>) 29 30<i>// non-named parameter version</i> 31template <typename Graph1, typename Graph2, typename IsoMap, 32 typename VertexInvariant1, typename VertexInvariant2, 33 typename V1Map, typename V2Map> 34bool isomorphism(const Graph1& g1, const Graph2& g2, 35 IsoMap f, VertexInvariant1 invariant2, VertexInvariant2 invariant2, 36 std::size_t max_invariant, VertexIndex1Map i1_map, VertexIndex2Map i2_map) 37</pre> 38 39<p> 40An <b><i>isomorphism</i></b> is a 1-to-1 mapping of the vertices in 41one graph to the vertices of another graph such that adjacency is 42preserved. Another words, given graphs <i>G<sub>1</sub> = 43(V<sub>1</sub>,E<sub>1</sub>)</i> and <i>G<sub>2</sub> = 44(V<sub>2</sub>,E<sub>2</sub>)</i> an isomorphism is a function 45<i>f</i> such that for all pairs of vertices <i>a,b</i> in 46<i>V<sub>1</sub></i>, edge <i>(a,b)</i> is in <i>E<sub>1</sub></i> if 47and only if edge <i>(f(a),f(b))</i> is in <i>E<sub>2</sub></i>. 48</p> 49 50<p> 51This function returns <tt>true</tt> if there exists an isomorphism 52between graph 1 and graph 2 and <tt>false</tt> otherwise. Also, if a 53isomorphism map named parameter is provided then an isomorphism is 54recorded in the map. 55</p> 56 57<p> 58The current implementation is based on descriptions of a backtracking 59algorithm in [<a 60href="./bibliography.html#fortin96:_graph_iso_prob">46</a>,<a 61href="./bibliography.html#reingold77:_combin_algo">48</a>]. The file 62<a href="./isomorphism-impl.pdf">isomorphism-impl.pdf</a> contains a (somewhat out-of-date) 63"literate" description of the implementation. The algorithm 64used is simple but slow. A more efficient (and much more complex) 65algorithm is described in [<a 66href="./bibliography.html#mckay81:_pract_graph_iso">47</a>]. When (and 67if) a version of this algorithm is ported to the BGL interface it 68should replace the current algorithm. 69</p> 70 71<H3>Where Defined</H3> 72 73<a href="../../../boost/graph/isomorphism.hpp"><TT>boost/graph/isomorphism.hpp</TT></a> 74 75<h3>Parameters</h3> 76 77IN: <tt>const Graph1& g1</tt> 78<blockquote> 79A directed or undirected graph. The graph type must model of <a 80href="./VertexListGraph.html">Vertex List Graph</a> and <a 81href="./EdgeListGraph.html">Edge List Graph</a>. 82</blockquote> 83 84IN: <tt>const Graph2& g2</tt> 85<blockquote> 86A directed or undirected graph. The graph type must model <a 87href="./BidirectionalGraph.html">Bidirectional Graph</a> and <a 88href="./VertexListGraph.html">Vertex List Graph</a>. 89</blockquote> 90 91<h3>Named Parameters</h3> 92 93OUT: <tt>isomorphism_map(IsoMap f)</tt> 94<blockquote> 95The mapping from vertices in graph 1 to vertices in graph 2. This must 96be a <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 97Property Map</a>.<br> <b>Default:</b> an <a 98href="../../property_map/doc/iterator_property_map.html"><tt>iterator_property_map</tt></a> 99constructed from a <tt>std::vector</tt> of graph 2's vertex 100descriptor type and the vertex index map for graph 1.<br> 101<b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the first graph. 102</blockquote> 103 104IN: <tt>vertex_invariant1(VertexInvariant1 i1)</tt> 105IN: <tt>vertex_invariant2(VertexInvariant2 i2)</tt> 106<blockquote> 107Mappings from vertices to integers which restrict which vertices may be 108considered isomorphic. If a candidate isomorphism maps <i>v1</i> to <i>v2</i> 109but <i>i1</i>(<i>v1</i>) != <i>i2</i>(<i>v2</i>), that candidate is rejected. 110This mapping can be used either to speed up the search (as is done by the 111default value, which requires that the degrees of <i>v1</i> and <i>v2</i> are 112equal) or to impose extra conditions on the result. The 113<tt>VertexInvariant1</tt> and <tt>VertexInvariant2</tt> types must model <a 114href="http://www.boost.org/sgi/stl/UnaryFunction.html">UnaryFunction</a>, with 115the argument type of <tt>vertex_invariant1</tt> being <tt>Graph1</tt>'s vertex 116descriptor type, the argument type of <tt>vertex_invariant2</tt> being 117<tt>Graph2</tt>'s vertex descriptor type, and both functions having integral 118result types. The values returned by these two functions must be in the range 119[0, <tt>vertex_max_invariant</tt>). 120<br> 121<b>Default:</b> <tt>degree_vertex_invariant</tt> for both arguments<br> 122<b>Python</b>: Unsupported parameter. 123</blockquote> 124 125IN: <tt>vertex_max_invariant(std::size_t max_invariant)</tt> 126<blockquote> 127An upper bound on the possible values returned from either 128vertex_invariant1 or vertex_invariant2. 129<br> 130<b>Default:</b> <tt>vertex_invariant2.max()</tt>. The default 131<tt>vertex_invariant2</tt> parameter, an instance of 132<tt>degree_vertex_invariant</tt>, defines this function to 133return <tt>num_vertices(g2) * (num_vertices(g2)+1)</tt>.<br> 134<b>Python</b>: Unsupported parameter. 135</blockquote> 136 137IN: <tt>vertex_index1_map(VertexIndex1Map i1_map)</tt> 138<blockquote> 139This maps each vertex to an integer in the range <tt>[0, 140num_vertices(g))</tt>. This is necessary for efficient updates of the 141heap data structure when an edge is relaxed. The type 142<tt>VertexIndex1Map</tt> must be a model of <a 143href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 144Map</a>. The value type of the map must be an integer type. The vertex 145descriptor type of graph 1 needs to be usable as the key type of the 146map.<br> 147<b>Default:</b> <tt>get(vertex_index, g1)</tt> 148 Note: if you use this default, make sure your graph has 149 an internal <tt>vertex_index</tt> property. For example, 150 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 151 not have an internal <tt>vertex_index</tt> property. 152 <br> 153<b>Python</b>: Unsupported parameter. 154</blockquote> 155 156IN: <tt>vertex_index2_map(VertexIndex2Map i2_map)</tt> 157<blockquote> 158This maps each vertex to an integer in the range <tt>[0, 159num_vertices(g))</tt>. This is necessary for efficient updates of the 160heap data structure when an edge is relaxed. The type 161<tt>VertexIndex2Map</tt> must be a model of <a 162href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 163Map</a>. The value type of the map must be an integer type. The vertex 164descriptor type of graph 2 needs to be usable as the key type of the 165map.<br> 166<b>Default:</b> <tt>get(vertex_index, g2)</tt> 167 Note: if you use this default, make sure your graph has 168 an internal <tt>vertex_index</tt> property. For example, 169 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 170 not have an internal <tt>vertex_index</tt> property. 171 <br> 172<b>Python</b>: Unsupported parameter. 173</blockquote> 174 175 176<h3>Complexity</h3> 177 178The worst-case time complexity is <i>O(|V|!)</i>. 179 180<h3>Example</h3> 181 182See <a href="../example/isomorphism.cpp"><tt>libs/graph/example/isomorphism.cpp</tt></a>. 183 184<br> 185<HR> 186<TABLE> 187<TR valign=top> 188<TD nowrap>Copyright © 2000-2001</TD><TD> 189<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>) 190</TD></TR></TABLE> 191 192</BODY> 193</HTML> 194
