ceph/src/boost/libs/graph/doc/isomorphism.html

   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>
  26 template &lt;class Graph1, class Graph2, class P, class T, class R&gt;
  27 bool isomorphism(const Graph1&amp; g1, const Graph2&amp; g2,
  28                  const bgl_named_params&lt;P,T,R&gt;&amp; params = <i>all defaults</i>)
  29
  30 <i>// non-named parameter version</i>
  31 template &lt;typename Graph1, typename Graph2, typename IsoMap,
  32           typename VertexInvariant1, typename VertexInvariant2,
  33           typename V1Map, typename V2Map&gt;
  34 bool isomorphism(const Graph1&amp; g1, const Graph2&amp; 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>
  40 An <b><i>isomorphism</i></b> is a 1-to-1 mapping of the vertices in
  41 one graph to the vertices of another graph such that adjacency is
  42 preserved. 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
  47 and only if edge <i>(f(a),f(b))</i> is in <i>E<sub>2</sub></i>.
  48 </p>
  49
  50 <p>
  51 This function returns <tt>true</tt> if there exists an isomorphism
  52 between graph 1 and graph 2 and <tt>false</tt> otherwise. Also, if a
  53 isomorphism map named parameter is provided then an isomorphism is
  54 recorded in the map.
  55 </p>
  56
  57 <p>
  58 The current implementation is based on descriptions of a backtracking
  59 algorithm in [<a
  60 href="./bibliography.html#fortin96:_graph_iso_prob">46</a>,<a
  61 href="./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 &quot;literate&quot; description of the implementation.  The algorithm
  64 used is simple but slow. A more efficient (and much more complex)
  65 algorithm is described in [<a
  66 href="./bibliography.html#mckay81:_pract_graph_iso">47</a>]. When (and
  67 if) a version of this algorithm is ported to the BGL interface it
  68 should 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
  77 IN: <tt>const Graph1&amp; g1</tt>
  78 <blockquote>
  79 A directed or undirected graph. The graph type must model of <a
  80 href="./VertexListGraph.html">Vertex List Graph</a> and <a
  81 href="./EdgeListGraph.html">Edge List Graph</a>.
  82 </blockquote>
  83
  84 IN: <tt>const Graph2&amp; g2</tt>
  85 <blockquote>
  86 A directed or undirected graph. The graph type must model <a
  87 href="./BidirectionalGraph.html">Bidirectional Graph</a> and <a
  88 href="./VertexListGraph.html">Vertex List Graph</a>.
  89 </blockquote>
  90
  91 <h3>Named Parameters</h3>
  92
  93 OUT: <tt>isomorphism_map(IsoMap f)</tt>
  94 <blockquote>
  95 The mapping from vertices in graph 1 to vertices in graph 2. This must
  96 be a <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
  97 Property Map</a>.<br> <b>Default:</b> an <a
  98 href="../../property_map/doc/iterator_property_map.html"><tt>iterator_property_map</tt></a>
  99 constructed from a <tt>std::vector</tt> of graph 2's vertex
 100 descriptor 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
 104 IN: <tt>vertex_invariant1(VertexInvariant1 i1)</tt>
 105 IN: <tt>vertex_invariant2(VertexInvariant2 i2)</tt>
 106 <blockquote>
 107 Mappings from vertices to integers which restrict which vertices may be
 108 considered isomorphic. If a candidate isomorphism maps <i>v1</i> to <i>v2</i>
 109 but <i>i1</i>(<i>v1</i>) != <i>i2</i>(<i>v2</i>), that candidate is rejected.
 110 This mapping can be used either to speed up the search (as is done by the
 111 default value, which requires that the degrees of <i>v1</i> and <i>v2</i> are
 112 equal) or to impose extra conditions on the result.  The
 113 <tt>VertexInvariant1</tt> and <tt>VertexInvariant2</tt> types must model <a
 114 href="http://www.sgi.com/tech/stl/UnaryFunction.html">UnaryFunction</a>, with
 115 the argument type of <tt>vertex_invariant1</tt> being <tt>Graph1</tt>'s vertex
 116 descriptor type, the argument type of <tt>vertex_invariant2</tt> being
 117 <tt>Graph2</tt>'s vertex descriptor type, and both functions having integral
 118 result 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
 125 IN: <tt>vertex_max_invariant(std::size_t max_invariant)</tt>
 126 <blockquote>
 127 An upper bound on the possible values returned from either
 128 vertex_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
 133 return <tt>num_vertices(g2) * (num_vertices(g2)+1)</tt>.<br>
 134 <b>Python</b>: Unsupported parameter.
 135 </blockquote>
 136
 137 IN: <tt>vertex_index1_map(VertexIndex1Map i1_map)</tt>
 138 <blockquote>
 139 This maps each vertex to an integer in the range <tt>[0,
 140 num_vertices(g))</tt>. This is necessary for efficient updates of the
 141 heap data structure when an edge is relaxed. The type
 142 <tt>VertexIndex1Map</tt> must be a model of <a
 143 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 144 Map</a>. The value type of the map must be an integer type. The vertex
 145 descriptor type of graph 1 needs to be usable as the key type of the
 146 map.<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
 156 IN: <tt>vertex_index2_map(VertexIndex2Map i2_map)</tt>
 157 <blockquote>
 158 This maps each vertex to an integer in the range <tt>[0,
 159 num_vertices(g))</tt>. This is necessary for efficient updates of the
 160 heap data structure when an edge is relaxed. The type
 161 <tt>VertexIndex2Map</tt> must be a model of <a
 162 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 163 Map</a>. The value type of the map must be an integer type. The vertex
 164 descriptor type of graph 2 needs to be usable as the key type of the
 165 map.<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
 178 The worst-case time complexity is <i>O(|V|!)</i>.
 179
 180 <h3>Example</h3>
 181
 182 See <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 &copy; 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>