?? page413.html
字號:
<HTML>
<HEAD>
<TITLE>Applications</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html7025" HREF="page414.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page414.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7023" HREF="page387.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page387.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7017" HREF="page412.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page412.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7027" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7028" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H1><A NAME="SECTION0013500000000000000000">Applications</A></H1>
<P>
One of the most important applications of partitions
involves the processing of equivalence relations.
Equivalence relations arise in many interesting contexts.
For example, two nodes in an electric circuit are electrically equivalent
if there is a conducting path (a wire) connecting the two nodes.
In effect, the wires establish an electrical equivalence relation over
the nodes of a circuit.
<P>
A similar relation arises among the user-defined data types in a C++ program.
Consider the following C++ code fragment:
<PRE>class A;
typedef A B;
typedef A C;
typedef B D;</PRE>
The four data types <tt>A</tt>, <tt>B</tt>, <tt>C</tt> and <tt>D</tt>
are equivalent in the sense that values of one type can be assigned directly
to variables of another (without requiring a type conversion).
In effect, the <tt>typedef</tt> declarations establish a
type equivalence relation over the user-defined data types in a C++ program.
<P>
<BLOCKQUOTE> <b>Definition (Equivalence Relation)</b><A NAME="defnsetsequivalence"> </A>
An <em>equivalence relation</em><A NAME=30057> </A><A NAME=30058> </A>
over a universal set <I>U</I> is a relation <IMG WIDTH=10 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline67862" SRC="img1700.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1700.gif" >
with the following properties:
<OL><LI> The relation <IMG WIDTH=10 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline67862" SRC="img1700.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1700.gif" > is <em>reflexive</em><A NAME=30061> </A>.
I.e., for every <IMG WIDTH=40 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67866" SRC="img1701.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1701.gif" >, <IMG WIDTH=37 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline67868" SRC="img1702.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1702.gif" >.<LI> The relation <IMG WIDTH=10 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline67862" SRC="img1700.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1700.gif" > is <em>symmetric</em><A NAME=30063> </A>.
I.e., for every pair <IMG WIDTH=40 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67866" SRC="img1701.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1701.gif" > and <IMG WIDTH=40 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67874" SRC="img1703.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1703.gif" >,
if <IMG WIDTH=37 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline67876" SRC="img1704.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1704.gif" > then <IMG WIDTH=38 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline67878" SRC="img1705.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1705.gif" >.<LI> The relation <IMG WIDTH=10 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline67862" SRC="img1700.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1700.gif" > is <em>transitive</em><A NAME=30065> </A>.
I.e., for every triple <IMG WIDTH=40 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67866" SRC="img1701.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1701.gif" >, <IMG WIDTH=40 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67874" SRC="img1703.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1703.gif" > and <IMG WIDTH=40 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67886" SRC="img1706.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1706.gif" >,
if <IMG WIDTH=37 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline67876" SRC="img1704.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1704.gif" > and <IMG WIDTH=37 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline67890" SRC="img1707.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1707.gif" > then <IMG WIDTH=36 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline67892" SRC="img1708.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1708.gif" >.
</OL></BLOCKQUOTE>
<P>
An important characteristic of an equivalence relation is that it
partitions the elements of the universal set <I>U</I> into
a set of <em>equivalence classes</em><A NAME=30069> </A>.
I.e., <I>U</I> is partitioned into <IMG WIDTH=143 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline67580" SRC="img1647.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1647.gif" >,
such that for every pair <IMG WIDTH=40 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67866" SRC="img1701.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1701.gif" > and <IMG WIDTH=40 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67874" SRC="img1703.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1703.gif" >,
<IMG WIDTH=37 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline67876" SRC="img1704.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1704.gif" > if and only if
<I>x</I> and <I>y</I> are in the same element of the partition.
I.e.,
<P> <IMG WIDTH=391 HEIGHT=15 ALIGN=BOTTOM ALT="displaymath67854" SRC="img1709.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1709.gif" ><P>
<P>
For example, consider the universe <IMG WIDTH=116 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67910" SRC="img1710.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1710.gif" >.
and the equivalence relation <IMG WIDTH=10 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline67862" SRC="img1700.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1700.gif" > defined over <I>U</I> defines as follows:
<P><A NAME="eqnsetsequiv"> </A> <IMG WIDTH=557 HEIGHT=39 ALIGN=BOTTOM ALT="multline30070" SRC="img1711.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1711.gif" ><P>
This relation results in the following partition of <I>U</I>:
<P> <IMG WIDTH=364 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath67855" SRC="img1712.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1712.gif" ><P>
<P>
The list of equivalences in Equation <A HREF="page413.html#eqnsetsequiv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page413.html#eqnsetsequiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> contains many redundancies.
Since we know that the relation <IMG WIDTH=10 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline67862" SRC="img1700.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1700.gif" >
is reflexive, symmetric and transitive,
it is possible to infer the complete relation from the following list
<P> <IMG WIDTH=380 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath67856" SRC="img1713.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1713.gif" ><P>
The problem of finding the set of equivalence classes
from a list of equivalence pairs is easily solved using a partition.
Program <A HREF="page413.html#progapp09ac" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page413.html#progapp09ac"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> shows how it can be done
using the <tt>PartitionAsForest</tt> class defined in Section <A HREF="page406.html#secsetspforest" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page406.html#secsetspforest"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
<P><A NAME="30080"> </A><A NAME="progapp09ac"> </A> <IMG WIDTH=575 HEIGHT=410 ALIGN=BOTTOM ALT="program30077" SRC="img1714.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1714.gif" ><BR>
<STRONG>Program:</STRONG> Application of Disjoint Sets--Finding Equivalence Classes<BR>
<P>
<P>
The algorithm first gets a positive integer <tt>n</tt> from the input
and creates a partition, <tt>p</tt>,
of the universe <IMG WIDTH=140 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67920" SRC="img1715.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1715.gif" > (lines 3-5).
As explained in Section <A HREF="page406.html#secsetspforest" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page406.html#secsetspforest"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
the initial partition comprises <tt>n</tt> disjoint sets of size one.
I.e., each element of the universal set
is in a separate element of the partition.
<P>
Each iteration of the main loop processes one equivalence pair (lines 9-18).
An equivalence pair consists of two numbers, <tt>i</tt> and <tt>j</tt>,
such that <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67922" SRC="img1716.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1716.gif" > and <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67924" SRC="img1717.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1717.gif" >.
The <em>find</em> operation is used to determine the sets <tt>s</tt> and <tt>t</tt>
in partition <tt>p</tt> that contain elements <tt>i</tt> and <tt>j</tt>,
respectively (lines 11-12).
<P>
If <tt>s</tt> and <tt>t</tt> are not the same set,
then the disjoint sets are united
using the <em>join</em> operation (lines 13-14).
Otherwise, <tt>i</tt> and <tt>j</tt> are already in the same set
and the equivalence pair is redundant (lines 15-17).
After all the pairs have been processed,
the final partition is printed (line 19).
<P>
<HR><A NAME="tex2html7025" HREF="page414.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page414.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7023" HREF="page387.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page387.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7017" HREF="page412.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page412.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7027" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7028" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -