[ceph.git] / ceph / src / boost / libs / graph / doc / isomorphism.html

<HTML>
<!--
     Copyright (c) Jeremy Siek 2000
    
     Distributed under the Boost Software License, Version 1.0.
     (See accompanying file LICENSE_1_0.txt or copy at
     http://www.boost.org/LICENSE_1_0.txt)
  -->
<Head>
<Title>Boost Graph Library: Isomorphism</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
        ALINK="#ff0000"> 
<IMG SRC="../../../boost.png" 
     ALT="C++ Boost" width="277" height="86"> 

<BR Clear>

<H1>
<img src="figs/python.gif" alt="(Python)"/>
<TT>isomorphism</TT>
</H1>


<PRE>
<i>// named parameter version</i>
template &lt;class Graph1, class Graph2, class P, class T, class R&gt;
bool isomorphism(const Graph1&amp; g1, const Graph2&amp; g2,
                 const bgl_named_params&lt;P,T,R&gt;&amp; params = <i>all defaults</i>)

<i>// non-named parameter version</i>
template &lt;typename Graph1, typename Graph2, typename IsoMap, 
          typename VertexInvariant1, typename VertexInvariant2, 
          typename V1Map, typename V2Map&gt;
bool isomorphism(const Graph1&amp; g1, const Graph2&amp; g2,
		 IsoMap f, VertexInvariant1 invariant2, VertexInvariant2 invariant2,
		 std::size_t max_invariant, VertexIndex1Map i1_map, VertexIndex2Map i2_map)
</pre>

<p>
An <b><i>isomorphism</i></b> is a 1-to-1 mapping of the vertices in
one graph to the vertices of another graph such that adjacency is
preserved. Another words, given graphs <i>G<sub>1</sub> =
(V<sub>1</sub>,E<sub>1</sub>)</i> and <i>G<sub>2</sub> =
(V<sub>2</sub>,E<sub>2</sub>)</i> an isomorphism is a function
<i>f</i> such that for all pairs of vertices <i>a,b</i> in
<i>V<sub>1</sub></i>, edge <i>(a,b)</i> is in <i>E<sub>1</sub></i> if
and only if edge <i>(f(a),f(b))</i> is in <i>E<sub>2</sub></i>.
</p>

<p>
This function returns <tt>true</tt> if there exists an isomorphism
between graph 1 and graph 2 and <tt>false</tt> otherwise. Also, if a
isomorphism map named parameter is provided then an isomorphism is
recorded in the map.
</p>

<p>
The current implementation is based on descriptions of a backtracking
algorithm in [<a
href="./bibliography.html#fortin96:_graph_iso_prob">46</a>,<a
href="./bibliography.html#reingold77:_combin_algo">48</a>].  The file
<a href="./isomorphism-impl.pdf">isomorphism-impl.pdf</a> contains a (somewhat out-of-date)
&quot;literate&quot; description of the implementation.  The algorithm
used is simple but slow. A more efficient (and much more complex)
algorithm is described in [<a
href="./bibliography.html#mckay81:_pract_graph_iso">47</a>]. When (and
if) a version of this algorithm is ported to the BGL interface it
should replace the current algorithm.
</p>

<H3>Where Defined</H3>

<a href="../../../boost/graph/isomorphism.hpp"><TT>boost/graph/isomorphism.hpp</TT></a>

<h3>Parameters</h3>

IN: <tt>const Graph1&amp; g1</tt>
<blockquote>
A directed or undirected graph. The graph type must model of <a
href="./VertexListGraph.html">Vertex List Graph</a> and <a
href="./EdgeListGraph.html">Edge List Graph</a>.
</blockquote>

IN: <tt>const Graph2&amp; g2</tt>
<blockquote>
A directed or undirected graph. The graph type must model <a
href="./BidirectionalGraph.html">Bidirectional Graph</a> and <a
href="./VertexListGraph.html">Vertex List Graph</a>.
</blockquote>

<h3>Named Parameters</h3>

OUT: <tt>isomorphism_map(IsoMap f)</tt>
<blockquote>
The mapping from vertices in graph 1 to vertices in graph 2. This must
be a <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
Property Map</a>.<br> <b>Default:</b> an <a
href="../../property_map/doc/iterator_property_map.html"><tt>iterator_property_map</tt></a>
constructed from a <tt>std::vector</tt> of graph 2's vertex
descriptor type and the vertex index map for graph 1.<br>
<b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the first graph.
</blockquote>

IN: <tt>vertex_invariant1(VertexInvariant1 i1)</tt>
IN: <tt>vertex_invariant2(VertexInvariant2 i2)</tt>
<blockquote>
Mappings from vertices to integers which restrict which vertices may be
considered isomorphic. If a candidate isomorphism maps <i>v1</i> to <i>v2</i>
but <i>i1</i>(<i>v1</i>) != <i>i2</i>(<i>v2</i>), that candidate is rejected.
This mapping can be used either to speed up the search (as is done by the
default value, which requires that the degrees of <i>v1</i> and <i>v2</i> are
equal) or to impose extra conditions on the result.  The
<tt>VertexInvariant1</tt> and <tt>VertexInvariant2</tt> types must model <a
href="http://www.sgi.com/tech/stl/UnaryFunction.html">UnaryFunction</a>, with
the argument type of <tt>vertex_invariant1</tt> being <tt>Graph1</tt>'s vertex
descriptor type, the argument type of <tt>vertex_invariant2</tt> being
<tt>Graph2</tt>'s vertex descriptor type, and both functions having integral
result types.  The values returned by these two functions must be in the range
[0, <tt>vertex_max_invariant</tt>).
<br>
<b>Default:</b> <tt>degree_vertex_invariant</tt> for both arguments<br>
<b>Python</b>: Unsupported parameter.
</blockquote>

IN: <tt>vertex_max_invariant(std::size_t max_invariant)</tt>
<blockquote>
An upper bound on the possible values returned from either 
vertex_invariant1 or vertex_invariant2.
<br>
<b>Default:</b> <tt>vertex_invariant2.max()</tt>. The default
<tt>vertex_invariant2</tt> parameter, an instance of 
<tt>degree_vertex_invariant</tt>, defines this function to
return <tt>num_vertices(g2) * (num_vertices(g2)+1)</tt>.<br> 
<b>Python</b>: Unsupported parameter.
</blockquote>

IN: <tt>vertex_index1_map(VertexIndex1Map i1_map)</tt>
<blockquote>
This maps each vertex to an integer in the range <tt>[0,
num_vertices(g))</tt>. This is necessary for efficient updates of the
heap data structure when an edge is relaxed. The type
<tt>VertexIndex1Map</tt> must be a model of <a
href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
Map</a>. The value type of the map must be an integer type. The vertex
descriptor type of graph 1 needs to be usable as the key type of the
map.<br>
<b>Default:</b> <tt>get(vertex_index, g1)</tt>
    Note: if you use this default, make sure your graph has
    an internal <tt>vertex_index</tt> property. For example,
    <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
    not have an internal <tt>vertex_index</tt> property.
   <br>
<b>Python</b>: Unsupported parameter.
</blockquote>

IN: <tt>vertex_index2_map(VertexIndex2Map i2_map)</tt>
<blockquote>
This maps each vertex to an integer in the range <tt>[0,
num_vertices(g))</tt>. This is necessary for efficient updates of the
heap data structure when an edge is relaxed. The type
<tt>VertexIndex2Map</tt> must be a model of <a
href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
Map</a>. The value type of the map must be an integer type. The vertex
descriptor type of graph 2 needs to be usable as the key type of the
map.<br>
<b>Default:</b> <tt>get(vertex_index, g2)</tt>
    Note: if you use this default, make sure your graph has
    an internal <tt>vertex_index</tt> property. For example,
    <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
    not have an internal <tt>vertex_index</tt> property.
   <br>
<b>Python</b>: Unsupported parameter.
</blockquote>


<h3>Complexity</h3>

The worst-case time complexity is <i>O(|V|!)</i>.

<h3>Example</h3>

See <a href="../example/isomorphism.cpp"><tt>libs/graph/example/isomorphism.cpp</tt></a>.

<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 2000-2001</TD><TD>
<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>)
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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 <class Graph1, class Graph2, class P, class T, class R>
	27	bool 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>
	31	template <typename Graph1, typename Graph2, typename IsoMap,
	32	typename VertexInvariant1, typename VertexInvariant2,
	33	typename V1Map, typename V2Map>
	34	bool 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>
	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	"literate" 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& 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& 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 © 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>