Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/isomorphism.html @ 47

Last change on this file since 47 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 6.4 KB
Line 
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 &lt;class Graph1, class Graph2, class P, class T, class R&gt;
27bool 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>
31template &lt;typename Graph1, typename Graph2,
32          typename IndexMapping, typename VertexInvariant,
33          typename V1Map, typename V2Map&gt;
34bool isomorphism(const Graph1&amp; g1, const Graph2&amp; g2,
35                 IsoMap f, VertexInvariant invariant,
36                 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
63&quot;literate&quot; 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&amp; 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&amp; 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/ReadWritePropertyMap.html">Read/Write
97Property Map</a>.<br> <b>Default:</b> an <a
98href="../../property_map/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_invariant(VertexInvariant i)</tt>
105<blockquote>
106A mapping <i>i</i> from vertices to integers such that if there is
107some isomorphism that maps <i>v</i> onto <i>v'</i> then <i>i(v) ==
108i(v')</i>. The <tt>VertexInvariant</tt> type must be a <a
109href="http://www.sgi.com/tech/stl/BinaryFunction.html">BinaryFunction</a>
110where the first argument is a vertex descriptor, the second argument is a
111graph, and the result type is an integer. The vertex invariant must
112work with the types for both graph 1 and graph 2 and therefore may need
113to have a templated <tt>operator()</tt>.
114<br>
115<b>Default:</b> <tt>degree_vertex_invariant</tt><br>
116<b>Python</b>: Any callable Python object will suffice.
117</blockquote>
118
119IN: <tt>vertex_index1_map(VertexIndex1Map i1_map)</tt>
120<blockquote>
121This maps each vertex to an integer in the range <tt>[0,
122num_vertices(g))</tt>. This is necessary for efficient updates of the
123heap data structure when an edge is relaxed. The type
124<tt>VertexIndex1Map</tt> must be a model of <a
125href="../../property_map/ReadablePropertyMap.html">Readable Property
126Map</a>. The value type of the map must be an integer type. The vertex
127descriptor type of graph 1 needs to be usable as the key type of the
128map.<br>
129<b>Default:</b> <tt>get(vertex_index, g1)</tt>
130    Note: if you use this default, make sure your graph has
131    an internal <tt>vertex_index</tt> property. For example,
132    <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
133    not have an internal <tt>vertex_index</tt> property.
134   <br>
135<b>Python</b>: Unsupported parameter.
136</blockquote>
137
138IN: <tt>vertex_index2_map(VertexIndex2Map i2_map)</tt>
139<blockquote>
140This maps each vertex to an integer in the range <tt>[0,
141num_vertices(g))</tt>. This is necessary for efficient updates of the
142heap data structure when an edge is relaxed. The type
143<tt>VertexIndex2Map</tt> must be a model of <a
144href="../../property_map/ReadablePropertyMap.html">Readable Property
145Map</a>. The value type of the map must be an integer type. The vertex
146descriptor type of graph 2 needs to be usable as the key type of the
147map.<br>
148<b>Default:</b> <tt>get(vertex_index, g2)</tt>
149    Note: if you use this default, make sure your graph has
150    an internal <tt>vertex_index</tt> property. For example,
151    <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
152    not have an internal <tt>vertex_index</tt> property.
153   <br>
154<b>Python</b>: Unsupported parameter.
155</blockquote>
156
157
158<h3>Complexity</h3>
159
160The worst-case time complexity is <i>O(|V|!)</i>.
161
162<h3>Example</h3>
163
164See <a href="../example/isomorphism.cpp"><tt>libs/graph/example/isomorphism.cpp</tt></a>.
165
166<br>
167<HR>
168<TABLE>
169<TR valign=top>
170<TD nowrap>Copyright &copy 2000-2001</TD><TD>
171<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
172</TD></TR></TABLE>
173
174</BODY>
175</HTML> 
Note: See TracBrowser for help on using the repository browser.